haskell - Haskell 中的组织同态示例

Question

我最近阅读了[1]和[2]，其中谈到了组织同质(和动态同质)，它们是可以表达例如的递归方案。动态规划。不幸的是，如果您不了解范畴论，则无法访问这些论文，即使其中的代码看起来像 Haskell。

有人可以用一个使用真实 Haskell 代码的示例来解释组织同态吗？

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

Answer 1

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

data Nat = S Nat | Z

此数据类型以皮亚诺风格对自然数进行编码。这意味着我们有 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

我们可以使用这种变形将 Nat 转换回 Integer，如下所示:

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，我们可以访问直接子项的值。但想象一下，我们也喜欢访问传递子项的值，例如，在定义斐波那契函数时。然后，我们不仅需要访问前一个值，还需要访问第二个前一个值。这就是组织同态发挥作用的地方。

组织同态(histo 听起来很像“历史”)允许我们访问所有以前的值，而不仅仅是最近的值。这意味着我们现在得到一个值列表，而不仅仅是一个值，因此组织同态的类型是:

-- 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 类型只是仿函数 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 来说可能更有意义)。因此，您基本上可以看到已应用的“减少顺序”(=历史记录)。