logo标签列表

Haskell中组织形态映射的例子

haskell
26

我最近阅读了 [1] 和 [2]，这两篇论文讲述的是histomorphism（以及dynamorphisms），它们是一种递归方案，可以表达动态规划等。不幸的是，如果您不懂范畴论，则无法访问这些论文，尽管其中有类似Haskell的代码。

请问有人可以用一个使用真实的Haskell代码示例来解释histomorphisms吗？

  1. Histo- and Dynamorphisms Revisited
  2. Recursion Schemes for Dynamic Programming
你看过pointless-haskell吗？它有histomorphisms和dynamorphisms的示例，尽管histomorphism的唯一示例是斐波那契数列。也许有人可以使用这些示例来解释-morphisms。 - Zeta
3
@Zeta 我已经这么做了，但是它所传达的思想与论文中大致相同：histo :: (Mu a,Functor (PF a)) => Ann a -> (F a (Histo a c) -> c) -> a -> c。 - tibbe
1
recursion-schemes有histo和dyna，而dyna只是在任何余代数上工作的histo。我能想到的最简单有趣的例子是一个相当直接的tail，它是基于广义foldr :: (a -> b -> b -> b) -> (a -> b -> b) -> b -> [a] -> b构建的。 - J. Abrahamson
2个回答
21

我们先定义一个数据类型作为示例：

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)

现在，我们首先为这种类型定义一个折叠函数(catamorphism)，因为它与历史记忆函数(histomorphism)非常相似，而折叠函数更容易理解。
折叠函数(catamorphism)允许“折叠”或“拆除”一个结构。它只需要一个函数，该函数知道如何在所有递归项都已经被折叠的情况下折叠结构。让我们定义这样一个类型，类似于Nat，但是用类型a中的某个值替换了所有递归实例：
data NatF a = SF a | ZF -- Aside: this is just Maybe

现在，我们可以为自然数的catamorphism定义类型：

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，我们可以访问直接子项的值。但是，想象一下，如果我们想要访问传递性子项的值，例如在定义斐波那契函数时。那么，我们不仅需要访问前一个值，还需要访问前两个值。这就是histomorphism发挥作用的地方。

histomorphism（histo听起来很像“history”）允许我们访问所有先前的值，而不仅仅是最近的一个值。这意味着我们现在得到了一个值列表，而不仅仅是单个值，因此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 更强大。你可以通过将 histo 和 cata 相互实现来证明这一点。

上述示例中未展示的是，如果将类型定义为一个函子的不动点，则非常通用地可以实现 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-, ana-, apo- 和 hylomorphisms 已经在 recursion-schemes 包中实现。虽然文档不够完善，但是通过将你的 functor 定义为一个 fixed point (Mu 类型、Nu 类型或直接定义)，或者提供一个 Base functor 并使用 project/embed，你可以得到一个包含许多所需 morphisms 的 Foldable/Unfoldable 实例。 - Boyd Stephen Smith Jr.
然后，您只需在选择余代数时放松一些限制，就可以通过以下方式获得dyna形态：dyna :: Functor f => (f (Cofree f a) -> a) -> (c -> f c) -> (c -> a)。这里的c替换了Fix f，(c -> f c)是recursion-schemes中project的一个不那么严格的形式。 - J. Abrahamson
我没想到 cata 和 histo 会一样强大。那么 dyna 是不是更强大呢？ - tibbe
@J.Abrahamson，dyna只是手动传递Foldable字典吗？所以dyna就像histo对应于sortBy对应于sort一样？ - bennofs
@tibbe 我的猜想是，在更弱/更大的范畴设置中，histo和cata的能力不相等。我尚未尝试使用cata实现histo，但我猜想它需要strength。 - J. Abrahamson
@bennofs 这就是我所理解的，同时还有一个限制，即你传递给 sortBy 的内容应该“有意义”; 你不能只是传递任何旧的余代数到 dyna。唯一的区别在于，在 Haskell 中，对于任何代数数据类型来说都存在一种正确的余代数，这就是 Foldable 所捕获的。 - J. Abrahamson
13
我们可以将其思考为从分类到历史再到动态的一般化连续体。以递归方案术语来说：
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上运行，只要我们可以为其创建一个f-coalgebra，而不仅仅是Foldable（它具有通用的Base t-coalgebras作为Foldable证明数据类型是最终coalgebras）来改进histo。

我们几乎可以通过简单地观察满足它们的类型所需的条件来读取它们的属性。

例如，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赋予其“历史”力量的原因。例如，我们可以使用histo编写一个相当直接的tail，而仅使用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的列表和长度为n的列表做出不同的响应。

要将histo推广到dyna，我们只需用任何余代数替换自然投影。因此，我们可以很容易地用dyna实现histo。

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

所以现在我们可以将histo折叠应用于任何类型，即使它部分地被视为列表（只要我们继续使用Prim [a]作为Functor，f）。 （理论上，有一个限制，即这个coalgebra最终会停止，例如我们不能处理无限流，但这更多涉及理论和优化而不是使用。在使用中，这样的事情只需要是懒惰的并且足够小才能终止。）（这反映了通过其能力来表示初始代数的想法project :: t -> Base t t。如果这真的是一个完全归纳类型，那么您只能投影很多次才能到达末尾。）
为了复制链接论文中的Catalan数字实例，我们可以创建非空列表。
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)

然后，我们对自然数的NELf视图应用histo风格的折叠，以产生第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
Base和Prim的目的是什么？我看到它们在递归方案中被定义，但是它们所在的模块缺乏任何文档。为什么递归方案定义了一个不同于通常使用的Foldable类？该类中的project函数是什么意思？ - tibbe
Base 是一个类型族，其中 Base t 是类型 t 的签名函子，即 t 是 f-代数的最终/初始共代数。这里的 Foldable 是 Data.Foldable 的一般形式——你可以将 Data.Foldable 视为 Data.Functor.Foldable 的特化版本，使得 Base (t a) = Base [a]。最后，project 基本上是 uncons :: [a] -> Maybe (a, [a])，但是再次推广到任意的 Base 函子。 - J. Abrahamson
哦！由于 Base 只是一种类型族，因此 Prim 是一种数据族，可以避免为像 ListSignature、MaybeSignature、BoolSignature、NatSignature 这样的数据类型制作新名称。同时拥有 Base 和 Prim 可以提高方便性。 - J. Abrahamson
使用动态规划求解卡特兰数的意义是什么，而不是直接使用历史记录算法呢？ - Liarokapis Alexandros
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接