haskell - 使用递归方案的核心递归斐波那契

Question

斐波那契数列有一个优雅的定义:

fibs :: [Integer]
fibs = fib 1 1 where
  fib a b = a : fib b (a + b)

可以将其转换为使用recursion-schemes库吗？

我能得到的最接近的是以下使用完全不同方法的代码:

fibN' :: Nat -> Integer
fibN' = histo $ \case
  (refix -> x:y:_) -> x + y
  _ -> 1

如果有必要，我可以提供其余的代码，但本质上我是通过使用 Nat = Fix Maybe 的组织同态来获得第 N 个斐波那契数。 Maybe (Cofree Maybe a) 与 [a] 同构，因此 refix 可以被认为是一种 toList 使模式更短。

更新:

我发现了更短的代码，但它仅以非通用方式存储一个值:

fib' :: (Integer, Integer) -> [Integer]
fib' = ana $ \(x, y) -> Cons x (y, x+y)

存储完整历史记录的非通用方法:

fib'' :: [Integer] -> [Integer]
fib'' = ana $ \l@(x:y:_) -> Cons x (x + y : l)

Answer 1

当然。您的谎言很容易被翻译成unfoldr ，这与 ana 的拼写方式略有不同。

fibs = unfoldr (\(a, b) -> Just (a, (b, a + b))) (1,1)