Haskell中组织形态的例子

让我们首先定义一个我们将用作示例的数据类型:

data Nat = S Nat | Z

此数据类型编码Peano风格的自然数字.这意味着我们有0和一种方法来产生任何自然数的后继.

我们可以轻松地从整数构造新的自然数:

-- Allow us to construct Nats
mkNat :: Integer -> Nat
mkNat n | n < 0 = error "cannot construct negative natural number"
mkNat 0 = Z
mkNat n = S $ mkNat (n-1)

现在,我们首先定义这种类型的变形,因为组织形态与它非常相似,并且变形更容易理解.

一种变形可以"折叠"或"拆除"一个结构.它只需要一个知道如何在已经折叠所有递归项时折叠结构的函数.让我们定义这样一个类型,类似于Nat,但是所有的递归实例都被一些类型的值替换a:

data NatF a = SF a | ZF -- Aside: this is just Maybe

现在,我们可以为Nat定义我们的变形类型:

cata :: (NatF a -> a)
     -> (Nat -> a)

由于知道如何折叠的非递归结构的功能NatF a到a,cata原来是到一个函数的整体折叠Nat.

cata的实现非常简单:首先折叠递归子项(如果有的话)并应用我们的函数:

cata f Z = f ZF -- No subterm to fold, base case
cata f (S subterm) = f $ SF $ cata f subterm -- Fold subterm first, recursive case

我们可以使用这个catamorphism将Nats 转换回Integers,如下所示:

natToInteger :: Nat -> Integer
natToInteger = cata phi where
  -- We only need to provide a function to fold
  -- a non-recursive Nat-like structure
  phi :: NatF Integer -> Integer
  phi ZF = 0
  phi (SF x) = x + 1

因此cata,我们可以访问immediate子项的值.但是想象一下,我们也喜欢访问传递子项的值,例如,在定义斐波纳契函数时.然后,我们不仅需要访问先前的值,还需要访问前一个值的第二个值.这就是组织形态发挥作用的地方.

组织形态(histo听起来很像"历史")允许我们访问所有先前的值,而不仅仅是最近的值.这意味着我们现在得到一个值列表,而不仅仅是一个值,因此histomorphism的类型是:

-- We could use the type NatF (NonEmptyList a) here.
-- But because NatF is Maybe, NatF (NonEmptyList a) is equal to [a].
-- Using just [a] is a lot simpler
histo :: ([a] -> a)
      -> Nat -> a
histo f = head . go where
  -- go :: Nat -> [a]  -- This signature would need ScopedTVs
  go Z = [f []]
  go (S x) = let subvalues = go x in f subvalues : subvalues

现在,我们可以定义fibN如下:

-- Example: calculate the n-th fibonacci number
fibN :: Nat -> Integer
fibN = histo $ \x -> case x of
 (x:y:_) -> x + y
 _       -> 1

除此之外:即使它看起来如此,但是histo并不比cata更强大.你可以通过在cata和其他方面实现histo来看到你自己.

我没有在上面的例子显示的是,cata和histo如果你定义类型作为仿函数的固定点可以非常普遍实行.我们的Nat类型只是Functor的固定点NatF.

如果您histo以通用方式定义,那么您还需要提供类似于NonEmptyList我们示例中的类型,但对于任何仿函数.这种类型恰恰是,你在Cofree f哪里f得到了固定点.你可以看到它适用于我们的例子:NonEmptyList只是Cofree Maybe.这是你如何得到通用类型histo:

histo :: Functor f 
      => (f (Cofree f a) -> a)
      -> Fix f  -- ^ This is the fixed point of f
      -> a

您可以将其f (Cofree f a)视为一种堆栈,在每个"层"中,您可以看到折叠较少的结构.在堆栈的顶部,每个直接的子项都被折叠.然后,如果你深入一层,直接的子项不再折叠,但子子项已经全部折叠(或评估,这在AST的情况下更有意义).所以你基本上可以看到已经应用的"减少序列"(=历史).

我们可以把那里作为从一个概括连续cata给histo到dyna.在术语中recursion-schemes:

Foldable t => (Base t a -> a)                                  -> (t -> a) -- (1)
Foldable t => (Base t (Cofree (Base t) a) -> a)                -> (t -> a) -- (2)
Functor  f => (f      (Cofree f        a) -> a) ->  (t -> f t) -> (t -> a) -- (3)

其中(1)是cata,(2)是histo,和(3)是dyna.这一概括的高度概括的是,histo提高cata通过维修器材都偏"右褶皱"的历史,dyna提高了histo通过让任何类型的操作t,只要我们能够做出f-coalgebra它,而不仅仅是Foldable那些(具有普遍性Base t-gegebras作为Foldable数据类型是最终余代数的见证人.

我们几乎可以通过简单地查看完成其类型所需的内容来读取它们的属性.

例如,经典的用途cata是定义foldr

data instance Prim [a] x = Nil | Cons a x
type instance Base [a] = Prim [a]

instance Foldable [a] where
  project []     = Nil
  project (a:as) = Cons a as

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = cata $ \case
  Nil      -> nil
  Cons a b -> cons a b

重要的是,我们注意到,foldr通过仅使用"先前"右折叠值来生成"下一个"部分右折叠值.这就是为什么它可以使用cata:它只需要最前面的部分折叠结果.

作为histo概括,cata我们应该能够做同样的事情.这是一个histo基于foldr

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = histo $ \case
  Nil             -> nil
  Cons a (b :< _) -> cons a b

我们可以看到,我们不再立即获得前一个折叠结果,而是必须到达第一层Cofree才能找到它.但是Cofree是一个流并且包含可能无限多的"先前折叠值",我们可以深入挖掘它.这就是赋予histo其"历史"力量的原因.例如,我们可以编写一个相当直接的tail使用histo,cata单独使用更难:

tail :: [a] -> Maybe [a]
tail = histo $ \case
  Nil             -> Nothing -- empty list
  Cons _ (b :< x) -> case x of
    Nil       -> Just [] -- length 1 list
    Cons a _ -> fmap (a:) b

样式有点间接,但主要是因为我们可以回顾过去的两个步骤,我们可以响应长度为1的列表,而不是长度为0的列表或长度n列表.

为了推广histo到最后一步,dyna我们只需用任何代数来代替自然投影.因此histo,我们可以dyna非常容易地实施

histo phi = dyna phi project -- project is from the Foldable class

所以现在我们可以将histo折叠应用于任何甚至可以部分被视为列表的类型(好吧,只要我们保持运行的示例并Prim [a]用作Functor,f).

(理论上,有一个限制,这个代数最终会停止,例如我们不能处理无限的流,但这更多地与理论和优化有关而不是使用.在使用中,这样的事情只需要是懒惰的并且足够小以终止.)

(这反映了通过他们的能力来表示初始代数的想法project :: t -> Base t t.如果这真的是一个完全归纳类型,那么你只能在结束前投射这么多次.)

要从链接的纸张复制加泰罗尼亚数字实例,我们可以创建非空列表

data NEL  a   = Some  a | More  a (NEL a)
data NELf a x = Somef a | Moref a x deriving Functor

并在自然数字上创建代数,称为natural适当展开,产生倒计时NEL

natural :: Int -> NELf Int Int
natural 0 = Somef 0
natural n = Moref n (n-1)

然后我们将histo-style折叠应用于NELf自然数的-view以产生n第 - 加泰罗尼亚数.

-- here's a quick implementation of `dyna` using `recursion-schemes`

zcata
  :: (Comonad w, Functor f) =>
     (a -> f a) -> (f (w (w c)) -> w b) -> (b -> c) -> a -> c
zcata z k g = g . extract . c where
  c = k . fmap (duplicate . fmap g . c) . z

dyna :: Functor f => (f (Cofree f c) -> c) -> (a -> f a) -> a -> c
dyna phi z = zcata z distHisto phi

takeC :: Int -> Cofree (NELf a) a -> [a]
takeC 0 _                 = []
takeC n (a :< Somef v)    = [a]
takeC n (a :< Moref v as) = a : takeC (n-1) as

catalan :: Int -> Int
catalan = dyna phi natural where
  phi :: NELf Int (Cofree (NELf Int) Int) -> Int
  phi (Somef 0) = 1
  phi (Moref n table) = sum (zipWith (*) xs (reverse xs))
    where xs = takeC n table