Haskell Language
재귀 스키마
수색…
비고
예제에서 언급 된 함수는 여러 패키지에서 다양한 수준의 추상화로 정의됩니다 (예 : data-fix
및 recursion-schemes
(여기에서는 더 많은 함수)). Hayoo에서 검색 하여 더 완전한 목록을 볼 수 있습니다.
고정 점수
Fix
은 "템플릿"유형을 취하고 반복적 인 매듭을 묶어서 라자 냐처럼 템플릿을 쌓습니다.
newtype Fix f = Fix { unFix :: f (Fix f) }
Fix f
안에서 템플릿 f
의 레이어를 찾습니다. f
의 매개 변수를 채우려면 Fix f
플러그 자체를 Fix f
. 그래서 템플릿 f
를 들여다 보면 Fix f
가 재귀 적으로 발견됩니다.
다음은 전형적인 재귀 적 데이터 유형이 템플릿 및 고정 소수점 프레임 워크로 어떻게 변환 될 수 있는지입니다. 우리는 유형의 재귀 적 발생을 제거하고 r
매개 변수를 사용하여 위치를 표시합니다.
{-# LANGUAGE DeriveFunctor #-}
-- natural numbers
-- data Nat = Zero | Suc Nat
data NatF r = Zero_ | Suc_ r deriving Functor
type Nat = Fix NatF
zero :: Nat
zero = Fix Zero_
suc :: Nat -> Nat
suc n = Fix (Suc_ n)
-- lists: note the additional type parameter a
-- data List a = Nil | Cons a (List a)
data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)
nil :: List a
nil = Fix Nil_
cons :: a -> List a -> List a
cons x xs = Fix (Cons_ x xs)
-- binary trees: note two recursive occurrences
-- data Tree a = Leaf | Node (Tree a) a (Tree a)
data TreeF a r = Leaf_ | Node_ r a r deriving Functor
type Tree a = Fix (TreeF a)
leaf :: Tree a
leaf = Fix Leaf_
node :: Tree a -> a -> Tree a -> Tree a
node l x r = Fix (Node_ l x r)
한 번에 한 레이어 씩 구조 접기
Catamorphisms 또는 주름 , 모델 원시 재귀. cata
각 층을 처리하는 대수 함수 (또는 폴딩 기능)을 이용하여 층 fixpoint 층을 찢는다. cata
에는 템플릿 유형 f
대한 Functor
인스턴스가 필요합니다.
cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix
-- list example
foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z = cata alg
where alg Nil_ = z
alg (Cons_ x acc) = f x acc
한 번에 한 레이어 씩 구조 펼치기
아나 모피즘 (anamorphisms), 또는 펼쳐진 , 원시적 인 코어 커션을 모델링합니다. ana
각각의 새로운 층을 생성 (혹은 전개 기능)을 coalgebra 함수를 사용하여 계층 fixpoint 층을 만든다. ana
에는 템플릿 유형 f
대한 Functor
인스턴스가 필요합니다.
ana :: Functor f => (a -> f a) -> a -> Fix f
ana f = Fix . fmap (ana f) . f
-- list example
unfoldr :: (b -> Maybe (a, b)) -> b -> List a
unfoldr f = ana coalg
where coalg x = case f x of
Nothing -> Nil_
Just (x, y) -> Cons_ x y
ana
와 cata
는 이중 입니다. 유형과 구현은 서로 대칭 이미지입니다.
펼친 후 접기, 융합
일반적으로 프로그램을 데이터 구조를 구축 한 다음 단일 값으로 축소하는 방식으로 구성합니다. 이것을 하이 몰 형태 또는 리 폴드 라고합니다. 효율성을 높이기 위해 중간 구조를 모두 없앨 수 있습니다.
hylo :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f -- no mention of Fix!
유도:
hylo f g = cata g . ana f
= g . fmap (cata g) . unFix . Fix . fmap (ana f) . f -- definition of cata and ana
= g . fmap (cata g) . fmap (ana f) . f -- unfix . Fix = id
= g . fmap (cata g . ana f) . f -- Functor law
= g . fmap (hylo f g) . f -- definition of hylo
원시 재귀
Paramorphisms는 원시 재귀를 모델링합니다. 폴드의 각 반복에서 폴딩 함수는 추가 처리를 위해 서브 트리를 수신합니다.
para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = f . fmap (\x -> (x, para f x)) . unFix
Prelude의 tails
는 paramorphism으로 모델링 할 수 있습니다.
tails :: List a -> List (List a)
tails = para alg
where alg Nil_ = cons nil nil -- [[]]
alg (Cons_ x (xs, xss)) = cons (cons x xs) xss -- (x:xs):xss
원시적 인 핵심 사건
Apomorphisms 모델 원시적 corecursion. 펼쳐지는 각 반복에서 전개 함수는 새로운 시드 또는 전체 하위 트리를 반환 할 수 있습니다.
apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = Fix . fmap (either id (apo f)) . f
apo
와 para
는 dual 입니다. 유형의 화살표가 뒤집 힙니다. para
의 튜플은 apo
의 Either
에 듀얼이며, 구현은 서로 대칭 이미지입니다.