Haskell - 对列表的前n个元素求和

6

我是Haskell的新手。

假设我想使用自己生成的函数来求一个列表中前n个元素的总和。我不知道如何在Haskell中实现这一点。我只知道如何对给定的列表求和,例如:

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

为了总结列表的前n个元素,例如:
从[1..10]中取出前5个数字,即1 + 2 + 3 + 4 + 5 = 15
我认为可以这样做:
sumList :: Int -> [Int] -> Int
sumList take [] = 0
sumList take (x:xs) = x + take $ sumList xs

但它不能工作...出了什么问题?

2
你认为在这里 take $ sumList xs 会做什么? - Willem Van Onsem
4个回答

13

那么你知道如何对列表中的数字求和,

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

如果列表中的元素不超过5个,那么即使您确实想在参数列表中求和的元素不超过5个,该函数也会返回正确的结果。让我们通过重命名该函数来明确我们的期望:

sumUpToFiveElements :: [Int] -> Int
sumUpToFiveElements [] = 0
sumUpToFiveElements (x:xs) = x + sumUpToFiveElements xs

这个函数在处理超过五个元素的列表时将无法返回正确结果,但至少名称是正确的。

我们能不能修复它?我们能否在计数的同时沿着输入列表前进并计算前5项?

sumUpToFiveElements :: Int -> [Int] -> Int
sumUpToFiveElements counter [] = 0
sumUpToFiveElements counter (x:xs) = x + sumUpToFiveElements (counter + 1) xs

当然,现在这还不对。我们现在进行了计数,但出于某种原因,我们忽略了计数器。如果我们想要不超过5个元素,什么是正确的时机来反应计数器?让我们尝试 counter == 5:

sumUpToFiveElements :: Int -> [Int] -> Int
sumUpToFiveElements 5       [] = 0
sumUpToFiveElements counter [] = 0
sumUpToFiveElements counter (x:xs) = x + sumUpToFiveElements (counter + 1) xs

但是为什么当达到5时我们要求列表也为空呢?让我们不这样做:

sumUpToFiveElements :: Int -> [Int] -> Int
sumUpToFiveElements 5       _  = 0        -- the wildcard `_` matches *anything*
sumUpToFiveElements counter [] = 0
sumUpToFiveElements counter (x:xs) = x + sumUpToFiveElements (counter + 1) xs

成功!当计数器达到5时,我们现在停止计数!更重要的是,我们还停止了求和!

等等,但是counter的初始值是多少?我们没有指定它,因此对于我们函数的用户(也就是我们自己)来说很容易犯错并使用不正确的初始值。顺便问一下,正确的初始值是什么?

好的,那么让我们这样做:

sumUpToFiveElements :: [Int] -> Int
sumUpToFiveElements xs = go 1 xs     -- is 1 the correct value here?
  where
    go counter  _ | counter == 5 = 0  
    go counter [] = 0
    go counter (x:xs) = x + go (counter + 1) xs

现在,我们没有那个多余的参数来使我们的定义变得脆弱,容易出现用户错误。

现在,听好了:

泛化! (通过使用符号值替换示例值;将5更改为n)。

sumUpToNElements :: Int -> [Int] -> Int
sumUpToNElements n xs = .......
   ........

完成。


另外一个建议:在学习 Haskell 的初期不要使用 $,请使用明确的括号

sumList take (x:xs) = x + take $ sumList xs 

被解析为

sumList take (x:xs) = (x + take) (sumList xs)

这将两个不相关的数字相加,然后使用结果作为一个函数,并用(sumList xs)作为参数调用该函数(换句话说,这是一个错误)。

如果您使用显式括号,您可能不会这样写。


谢谢您提供这么详细的解释。这让我更好地理解了如何解决这类问题 :) 目前,我更多地像“试错法”一样工作... 对于初学者来说,使用显式括号可能会更好。 - Slifer
不客气。随着时间的推移,当你对此有了感觉后,你将学会如何避免这种显式编程,并更直接地遵循归纳定义的数据类型,或使用内置的高阶函数、折叠等等。但是首先你必须获得感觉! :) - Will Ness
解释从 n 倒数比从 0 到 n 顺数更简单,因为你根本不需要使用 go - amalloy
@amalloy 我考虑了一下,选择了顺序递增。我认为这种方式更简单。如果采用倒序计数,那么所有数字必须完美对齐。而采用递增计数方式,我们可以自由地选择其他数字。 - Will Ness
@amalloy计数也将两个不同的方面分开(而倒数则混淆了它们)--一个是计数本身(遵循自然数归纳数据类型定义),另一个是测试目标值。因此,从概念上讲,我认为这更清晰。 (代码经济性不是我的目标 :))。 - Will Ness

2

你应该使用一个参数来限制值的数量(最好不要使用Prelude中的函数take),从而限制数字。

在你的代码中,这个限制显然是take $ sumList xs,这非常奇怪:在你的函数中,take是一个Int,而$会将你的语句写成(x + take) (sumList xs)。因此,你显然想要执行一个函数应用,其中(x + take)(一个Int)作为函数,sumList xs作为参数。但是,Int不是一个函数,因此它无法通过类型检查,也没有包含任何限制数字的逻辑。

因此,基本上我们应该考虑三种情况:

  1. 空列表的情况下,总和为0
  2. 要取的元素数量小于等于零,则总和为0;以及
  3. 要取的元素数量大于0,则我们将头部添加到从尾部少取一个元素的总和中。

因此,一个直接的映射是:

sumTakeList :: (Integral i, Num n) => i -> [n] -> n
sumTakeList _ [] = 0
sumTakeList t (x:xs) | t <= 0 = 0
                     | otherwise = x + sumTakeList (t-1) xs

但是您不需要自己编写这样的逻辑,可以将内置的take :: Int -> [a] -> [a]函数与sum :: Num a => [a] -> a函数结合使用:

sumTakeList  :: Num n => Int -> [n] -> n
sumTakeList t = sum . take t

现在如果你需要对前五个元素求和,我们可以将其作为一个特殊情况处理:
subList5 :: Num n => [n] -> n
sumList5 = sumTakeList 5

1
这是一个简短但有用的回答。你非常接近了。请考虑以下内容:
  • The take parameter tells you how many elements you need to sum up, so if you do sumList 0 anything you should always get 0 since you take no elements.
  • If you want the first n elements, you add the first element to your total and compute the sum of the next n-1 elements.

    sumList 0 anything = 0
    sumList n []       = 0
    sumList n (e:es)   = e + sumList (n-1) e
    

1
一个很好的资源,可以查看可用的函数及其工作原理,这是 Hoogle。以下是 take 的页面和所需功能的文档
如您所见,名称take已被使用,但这是一个可以用来实现此功能的函数。
请注意,您的sumList需要另一个参数,即要相加的元素数。您需要的语法类似于:
sumList :: Int -> [Int] -> Int
sumList n xs = _ $ take n xs

在下划线处您可以填写自己的内容。这是一个Prelude中的函数,但类型签名有点复杂,现在不方便讲解。

或者您可以递归地编写它,使用两个基本案例和第三个累积参数(通过辅助函数实现):

sumList :: Int -> [Int] -> Int
sumList n xs = sumList' n xs 0 where
  sumList' :: Int -> [Int] -> Int -> Int
  sumList' 0 _ a = _ -- A base case.
  sumList' _ [] a = _ -- The other base case.
  sumList' m (y:ys) a = sumList' _ _ _ -- The recursive case.

这里,等号左边的_符号应该保留在那里,并表示模式匹配忽略该参数,但右边的_符号是留给你自己填充的空白。同样,GHC会告诉你需要用哪种类型来填充这些空白。

这种尾递归函数是Haskell中非常常见的模式;你要确保每次递归调用都让你离基本情况更近一步。通常,这意味着将自身调用时从计数参数减去1,或者将列表参数的尾部作为新的列表参数调用自身。在这里,你需要同时做到两者。不要忘记在函数递归调用时更新运行总和a


1
在所发布的问题中,take 是一个 Int,而不是来自 Prelude 的 take 函数。 - amalloy
啊,你可以使用 Prelude 中的 take 函数来编写它,但是重新使用 Prelude 中的名称是一个不好的主意。 :) - Davislor
1
替换 _ . take 中的 _ 对于初学者来说并不容易。 - Will Ness
1
不客气。 :) 这个简单的规则很有帮助:一次只删除 一个 参数。 - Will Ness
1
标准的写法(我认为)是 (_ .) . take - Will Ness
显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接