Haskell 斐波那契函数的良好风格

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

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

检索列表中的 "last" 两项并添加它们的概念非常合理 - 您只需处理列表的前面，并在末尾反转它。所以 "last" 变成 "first" 而你只是模式匹配。

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 3

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

> let x = 3 in x + 2
5

这里 x 在计算 x + 2 之前绑定到 3，给出 5。

你可以用你的例子做类似的事情：

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]

好的，这里肯定有改进的余地。关于如何处理我们的某些功能，我们仍然没有 "thinking with portals"。特别是，addLastTwo 可以通过模式匹配得到显着改善：

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

这将列表的迭代次数从三个减少到一个（[=21= 一次，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

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

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

这为您提供了一对 "previous" 和 "current" 值：

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 5

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

否则，生成第一个 n 斐波那契数列的反向序列看起来也不错。这允许通过简单地添加一个新元素来添加 "a number at the end of the list"。

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

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]

Haskell 斐波那契函数的良好风格

Good Style of Haskell Fibonacci Function

haskell

anonymous-function

fibonacci