Haskell中的组织形式实例

Question

我最近读到了1和2，它们谈到了组织同构(和动态同构)，这是一种递归方案，可以表示动态规划。不幸的是，如果你不懂分类理论的话，论文是无法访问的，尽管里面有看起来像Haskell的代码。

有人能用一个使用真正Haskell代码的例子来解释组织形式吗？

1. Histo- and Dynamorphisms Revisited
2. Recursion Schemes for Dynamic Programming

Answer 1

让我们首先定义一个数据类型，我们将使用它作为一个示例：

data Nat = S Nat | Z

此数据类型以Peano样式编码自然数。这意味着我们有一种方法来产生任意自然数的继承者。

我们可以很容易地从整数构造新的自然数：

-- 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

我们可以使用这种变质作用将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，我们可以访问直接子项的值。但是，假设我们也喜欢访问传递子项的值，例如，在定义fibonacci函数时。然后，我们不仅需要访问前一个值，还需要访问第二个前一个值.这就是组织形式发挥作用的地方。

一个组织孤儿(他的声音听起来很像“历史”)允许我们访问所有以前的价值观，而不仅仅是最近的价值观。这意味着我们现在得到了一个值的列表，而不仅仅是一个值，所以组织形式的类型是：

-- 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

旁白:即使看起来是这样，他也不会比猫更强大。你可以通过从cata和相反的角度实现他的目标来看到你自己。

我在上面的示例中没有显示的是，如果将类型定义为函子的不动点，cata和histo通常可以实现。我们的Nat类型就是函子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)看作一种堆栈，在每个“层”中，您可以看到一个折叠较少的结构。在堆栈的顶部，每个直接子项都折叠起来。然后，如果您深入一层，直接子项不再折叠，但子项都已折叠(或评估，这在ASTs的情况下可能更有意义)。因此，您基本上可以看到已经应用的“削减顺序”(=历史)。

Answer 2

我们可以认为这是一个从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通过允许对任何类型的t进行操作来改进histo，只要我们可以为其制作一个f-coalgebra，而不仅仅是Foldable (作为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只使用“先前”右折叠值来生成"next“部分右折叠值。这就是为什么可以使用cata实现它:它只需要前面最直接的部分折叠结果。

随着histo对cata的推广，我们应该能够对它做同样的事情。这里是histo-based 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

这种方式有点间接，但本质上是因为我们可以回顾过去的两个步骤，我们可以对length-1列表的响应与Leng-0列表或length-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-th加泰罗尼亚数。

-- 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