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] 
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,
• 새 시드가 추가됩니다. "오래된 역사"에 에드는, 그래서 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)