哈斯克尔斐波那契函数的良好风格

Question

我只是在学习Haskell，并尝试实现一个函数来获取包含前N个斐波那契数的列表：

fibonacci :: Integer -> [Integer]
fibonacci 1 = [0]
fibonacci 2 = fibonacci 1 ++ [1]
fibonacci n = appendSumOfLastTwo (fibonacci (n - 1))
appendSumOfLastTwo :: (Num a) => [a] -> [a]
appendSumOfLastTwo xs = xs ++ [addLastTwo xs]
addLastTwo :: (Num a) => [a] -> a
addLastTwo xs = last xs + (xs !! ((length xs) - 2))

这有效，但不是很漂亮，因为它需要两个名称奇怪的辅助函数。在Haskell中，拥有这种单一使用的功能是否常见？

为了摆脱这些功能，我尝试了匿名函数：

fibonacci :: Integer -> [Integer]
fibonacci 1 = [0]
fibonacci 2 = fibonacci 1 ++ [1]
fibonacci n = (xs -> xs ++ [(xs -> last xs + (xs !! ((length xs) - 2))) xs]) (fibonacci ( n - 1))

但这并没有好多少，因为它几乎完全不可读。

你们会怎么看？如何以最佳方式构建代码？

Answer 1

没有比这更漂亮的了

fibs = 1:1:zipWith (+) fibs (tail fibs)

并用于任何 n

take n fibs

或者，如果你想从基础开始实现，也许最好先定义第 n 个斐波那契数

fib 1 = 1
fib 2 = 1                                      
fib n = fib (n-1) + fib (n-2)

这个系列将很简单

map fib [1..n]

请注意，对于任何大 N 来说，性能都会很糟糕。

Answer 2

也许最接近您的原始设计，但具有线性性能，是使用带有一对数字的iterate作为状态：

almostFibs :: [(Integer, Integer)]
almostFibs = iterate ((x, y) -> (y, x + y)) (0, 1)

这为您提供了一对"以前"和"当前"值：

Prelude> take 10 almostFibs
[(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55)]

要真正获得fibs，您只需删除"previous"值：

fibs :: [Integer]
fibs = map snd almostFibs

Answer 3

也许使用 let 关键字。它允许您绑定仅在表达式范围内的变量(包括函数(：

> let x = 3 in x + 2
5

在这里，x在评估之前绑定到x + 2，给出五。

您可以对示例执行类似操作：

fibonacci :: Integer -> [Integer]
fibonacci 1 = [0]
fibonacci 2 = fibonacci 1 ++ [1]
fibonacci n = let
  addLastTwo :: (Num a) => [a] -> a
  addLastTwo xs = last xs + (xs !! ((length xs) - 2))
  appendSumOfLastTwo :: (Num a) => [a] -> [a]
  appendSumOfLastTwo xs = xs ++ [addLastTwo xs]
 in appendSumOfLastTwo (fibonacci (n - 1))

让我们看看我们是否可以做得更好。我们还可以使用where作为语法糖来提高可读性。此关键字的行为与let ... in ...完全相同，除非有很多要绑定的变量和一个相对较短的表达式，它可能更具可读性：

fibonacci :: Integer -> [Integer]
fibonacci 1 = [0]
fibonacci 2 = fibonacci 1 ++ [1]
fibonacci n = appendSumOfLastTwo (fibonacci (n - 1))
  where
    addLastTwo :: (Num a) => [a] -> a
    addLastTwo xs = last xs + (xs !! ((length xs) - 2))
    appendSumOfLastTwo :: (Num a) => [a] -> [a]
    appendSumOfLastTwo xs = xs ++ [addLastTwo xs]

好的，这里肯定有改进的余地。我们仍然没有"用门户思考"如何处理我们的某些功能。特别是，通过模式匹配可以显著改善addLastTwo：

addLastTwo :: (Num a) => [a] -> a
addLastTwo (x:y:[]) = x + y
addLastTwo (_:rest) = addLastTwo rest
addLastTwo _ = error "List has less than two elements!"

这会将列表的迭代次数从三次减少到一次(一次用于last次，一次用于length次，最多一次用于!!次(。

此外，附加到列表的头部比附加到列表的末尾要容易得多。如有必要，您可以随时reverse列表。每当你写作时list ++ [elem]想想你是否真的是elem : list的意思。

考虑到这一点，以及更多的模式匹配，一个相对干净的算法版本将如下所示：

fibonacci :: Integer -> [Integer]
fibonacci 1 = [0]
fibonacci 2 = [0, 1]
fibonacci n = reverse $ (x + y) : upToN
  where
    upToN@(x:y:_) = reverse $ fibonacci (n - 1)

在这里，@字符将变量绑定到模式。在上面的示例中，upToN将绑定到列表[x, y, ...]，但也x和y将在范围内。

我建议你也花点时间看看为什么@karakfa的答案有效，以及为什么它会比你采取的方法更快。

Answer 4

问题不在于帮助程序函数，它们是完全有效的。拥有这样的功能当然是很常见的，尤其是只是在本地定义它们。这是列表索引，并且必须处理问题所在列表的末尾。如果你真的需要这些操作，那么列表就是错误的数据结构。

检索列表中"最后"两个项目并添加它们的概念是完全合理的 - 您只需要处理列表的前面，并在最后反转它。所以"最后"变成了"第一"，你只是模式匹配。

fibonacci :: Integer -> [Integer]
fibonacci = reverse . fib where
  fib n | n < 1 = [] 
  fib 1 = [0]
  fib 2 = [1,0] 
  fib n = case fib (n-1) of 
            r@(a:b:_) -> a+b:r

Answer 5

我认为最惯用的方法是生成无限列表，然后按照其他人的建议获取前n元素。

否则，生成前n斐波那契数的反向序列看起来也很好。这允许通过简单地在新元素前面加上前缀来添加"列表末尾的数字"。

相反，如果我们更喜欢按直接顺序生成列表，则可以使用递归，如下所示：

fibonacci :: Int -> [Int]
fibonacci n = fib 0 1 n
   where fib _ _ 0 = []
         fib a b n = a : fib b (a+b) (n-1)

Answer 6

一个好方法是使用 Haskell 的惰性求值并生成一个无限列表。然后，您可以take您想要从该列表中获得的每多个数字。

fibonacci :: [Integer]
fibonacci = 1 : scanl (+) 1 fibonacci

拥有此功能后，您可以检索所需的元素n数量。

> take 7 fibonacci
[1,1,2,3,5,8,13]