haskell - Haskell：如何对函数列表求和？

Question

我想在 Haskell 中使用递归。我定义：

pf:: Int -> Int
pf 1 = 1
pf n = pf 1 + sum[pf 1..pf n-1]

但总和不正确！总结函数列表的正确方法是什么？

Answer 1

[pf 1..pf (n-1)]不一样[pf 1, pf 2, pf 3, ..., pf (n-1)]。

> let f x = 2^x
> [f 1 .. f 4]
[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
> [f 1, f 2, f 3, f 4]
[2,4,8,16]

你可能想要map：

pf n = pf 1 + sum (map pf [1..n-1])

而且，正如一句话，pf x = 2^(x-1)。

Answer 2

从接受的答案开始，我们可以做以下细化

pf n = pf 1 + sum (map pf [1..n-1])

我们将 pf 1 与一个总和相加，然后它只是一个总和
通常的总和可以使用 fold 表示如下

sum = fold (+) 0

这里 0 可以被视为总和的种子，以说服您在 ghci 中输入以下两个表达式

foldl (+) 10 [1..10] -- return 65
10 + sum [1..10]    -- return 65 too

在我们的示例中，种子等于pf 1，这导致我们

pf n = foldl (+) (pf 1) (map pf [1..n-1])

再次我们可以重写一个术语，这次我将重点关注列表范围 [1..n-1]

enumFromTo 1 (n-1) = [1..n-1]

或者 n-1 可以（再次）重写为 pred n，那么我们有

enumFromTo 1 (pred n) = [1..n-1]

代入主表达式，我们得到

pf n = foldl (+) (pf 1) (map pf (enumFromTo 1 (pred n)))

现在我们可以用无点风格表达主要表达方式

pf = foldl (+) (pf 1) . map pf . enumFromTo 1 . pred 

我们可以做更多的考虑，而不是 map 可以用折叠来表达，但肯定我们会失去可读性，请注意

map f = foldl (\x xs -> f x : xs) []