Corecursive使用遞歸斐波納契方案

Question

有Fibonacci數列表的優雅derinition：

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 

我可以提供的代碼，如果必要的休息，但實際上我用histomorphism獲取第n個斐波納契數納特=修復也許。 Maybe (Cofree Maybe a)原來與[a]同構，所以refix可以被認爲只是一種toList使模式更短。

UPD：

我發現了更短的代碼，但它只能存儲一個值和非通用方式：

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

：

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

保存完整的歷史記錄的非通用的方法

Answer 1

當然。您的fibs很容易翻譯成unfoldr，這與拼寫ana的方式略有不同。

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

Answer 2

這裏是（在某種程度上）我想要的東西：

type L f a = f (Cofree f a) 

histAna 
    :: (Functor f, Corecursive t) => 
    (f (Cofree g a) -> Base t (L g a)) 
    -> (L g a -> f a) 
    -> L g a -> t 
histAna unlift psi = ana (unlift . lift) where 
    lift oldHist = (:< oldHist) <$> psi oldHist 

psi

• 接受一個 「老史」 作爲一個種子，
• 產生一個水平和種子剛像正常ana,
• 然後新的種子被追加ED「老史」，所以newHistory變得newSeed :< oldHistory

unlift生產從種子和歷史目前的水平。

fibsListAna :: Num a => L Maybe a -> [a] 
fibsListAna = histAna unlift psi where 
    psi (Just (x :< Just (y :< _))) = Just $ x + y 
    unlift x = case x of 
     Nothing -> Nil 
     h@(Just (v :< _)) -> Cons v h 

r1 :: [Integer] 
r1 = take 10 $ toList $ fibsListAna $ Just (0 :< Just (1 :< Nothing)) 

流版本也可以被實現（分別Identity和(,) a仿函數應使用）。二叉樹的情況也起作用，但不清楚它是否有用。這是我寫的一味只是爲了滿足類型檢查退化的情況：

fibsTreeAna :: Num a => L Fork a -> Tree a 
fibsTreeAna = histAna unlift psi where 
    psi (Fork (a :< _) (b :< _)) = Fork a b 
    unlift x = case x of 
     h@(Fork (a :< _) (b :< _)) -> NodeF (a + b) h h 

目前尚不清楚，如果我們用列表替換Cofree失去什麼：

histAna 
    :: (Functor f, Corecursive t) => 
     (f [a] -> Base t [a]) 
     -> ([a] -> f a) 
     -> [a] -> t 
    histAna unlift psi = ana (unlift . lift) where 
     lift oldHist = (: oldHist) <$> psi oldHist 

在這種情況下，「歷史」變成只是種子填充樹根的路徑。

列表版本原來是通過使用不同的算符所以播種和填充水平可以在一個地方來實現能夠容易地簡化爲：

histAna psi = ana lift where 
     lift oldHist = (: oldHist) <$> psi oldHist 

fibsListAna :: Num a => [a] 
fibsListAna = histAna psi [0,1] where 
    psi (x : y : _) = Cons (x + y) (x + y) 

原代碼與Cofree可以過於簡化：

histAna :: (Functor f, Corecursive t) => (L f a -> Base t (f a)) -> L f a -> t 
histAna psi = ana $ \oldHist -> fmap (:< oldHist) <$> psi oldHist 

fibsListAna :: Num a => L Maybe a -> [a] 
fibsListAna = histAna $ \case 
    Just (x :< Just (y :< _)) -> Cons (x + y) (Just (x + y)) 

fibsStreamAna :: Num a => L Identity a -> Stream a 
fibsStreamAna = histAna $ \case 
    Identity (x :< Identity (y :< _)) -> (x + y, Identity $ x + y) 

fibsTreeAna :: Num a => L Fork a -> Tree a 
fibsTreeAna = histAna $ \case 
    Fork (a :< _) (b :< _) -> NodeF (a + b) (Fork a a) (Fork b b)