不使用 zipWith 的斐波那契数列

Question

我一直在尝试在不使用惰性zipwith方法的情况下实现从0到n的斐波那契数列列表。到目前为止，我所拥有的代码是 return 是一个从 n 到 1 的列表。有什么办法可以更改此代码，使其 return 是从 0-[=13= 的列表] 有吗？

示例：

fib_seq 4 = [3,2,1,1] 
-- output wanted: [1,1,2,3]

如果没有办法做我想让代码做的事，有没有办法只 return 斐波那契数列再说一遍 4 会 return [0, 1, 1, 2].

fib_seq :: Int -> [Int]
fib_seq 0 = [0]
fib_seq 1 = [1]
fib_seq n = sum (take 2 (fib_seq (n-1))) : fib_seq (n-1)

Answer 1

通常情况下，您可以通过考虑问题的更一般版本来解决问题。

假设我们想要从两个规定的初始值 a 和 b 开始的无限斐波那契列表。有一个明显的递归解决方案：

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 ...
 λ> 
 λ> aux_fib a b = a : (aux_fib b (a+b))
 λ> 
 λ> take 4 (aux_fib 1 1)
 [1,1,2,3]
 λ>

等等：

 λ> 
 λ> fib_seq n = take n (aux_fib 1 1)
 λ> 
 λ> fib_seq 4
 [1,1,2,3]
 λ>

注意: 驼峰式大小写在Haskell中被认为更惯用，所以更像[=12] =] 和 fibSeq.

Answer 2

如果你想让列表从 0 开始，你可以使用一个辅助函数，然后在你的 fib_seq 中使用这个辅助函数（我建议你改为 Camel 大小写，比如 fibSeq，标准 haskell符号)

好的，下面的函数 fibSeq 7 会 return [0,1,1,2,3,5,8]:

fibHelp :: Int -> Int -> [Int]
fibHelp x y = x : (fibHelp y (x+y))

fibSeq :: Int -> [Int]
fibSeq n = take n (fibHelp 0 1)

Answer 3

感觉有点像作弊，但你可以像这样使用 closed formula 作为斐波那契数列：

fib n = (phi^n - psi^n) / sqrt 5
  where
    phi = (1 + sqrt 5) / 2
    psi = (1 - sqrt 5) / 2

fibSeq n = fib <$> [1 .. n]

否则 Haskell Wiki 还有更多 implementation variants 可供选择。比如很简洁

fibs = 0 : 1 : next fibs
  where
    next (a : t@(b:_)) = (a+b) : next t

Answer 4

您可以选择实现 fib 数字的另一种方法是使用辅助函数，然后使用它自己的函数来生成无限的 fib 数字列表，或者您可以使用 take 10 fibs 和输出将是前 10 个 fib 数字。我的函数绝对不是用 zipWith 函数无限计算 fib 数的最快方法，但你在这里没有使用它，所以这是我在没有 zipWith 的情况下实现它的方法。

例如 take 10 fibs 会 return: [0,1,1,2,3,5,8,13,21,34]

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)   

fibs :: [Int]
fibs = (map fib [0..])

不使用 zipWith 的斐波那契数列

Fibonacci numbers without using zipWith

haskell

fibonacci