Corecursiveフィボナッチ使用して再帰スキーム

Question

フィボナッチ数のリストのエレガントな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番目のフィボナッチ数を取得しますNat = Fix May。 Maybe (Cofree Maybe a)は、[a]と同型であることが判明しているので、refixは、toListのように考えると、パターンを短くすることができます。

UPD：

私は短いコードを見つけたが、それだけで店つの値と非汎用的な方法で：

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

fibsはunfoldrに簡単に翻訳されています。これはanaを綴る方法とは少し異なります。ここで

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

Answer 2

は、私が何を望むか（一種の）です：種子、

1つのだけのレベルや種子を生産するよう

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、
• 新しい種が追加されます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ファンクタをそれぞれ使用されるべきで）実施することができます。バイナリツリーの場合も機能しますが、それが何らかの目的で使用されているかどうかは不明です。我々はリストをCofreeを置き換えることによって、何かを失うどうかは明らかではありません

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 

：

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 

をここでは「歴史はちょうどなったここで私はちょうど型チェッカーを満たすために盲目的に書いた縮退ケースがあります種子で満たされた木のルートへのパス。Cofreeと元のコードがあまりにも単純化することができる

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) 

：

リストバージョンを簡単一箇所で達成することができるレベルをので、異なるファンクタを用いて播種し、充填することによって簡略化することが判明します

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)