Haskell Language
재귀 스키마

비고

고정 점수

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 에 듀얼이며, 구현은 서로 대칭 이미지입니다.