haskell - 一旦有了F代数，是否可以根据它定义可折叠和可遍历？

根据Bartosz Milewski的文章(one，two)，我已经定义了F代数:

(这并不是说我的代码是Bartosz想法的确切体现，这仅仅是我对它们的有限理解，任何错误都是我自己的。)

module Algebra where

data Expr a = Branch [a] | Leaf Int

instance Functor Expr where
    fmap f (Branch xs) = Branch (fmap f xs)
    fmap _ (Leaf   i ) = Leaf    i

newtype Fix a = Fix { unFix :: a (Fix a) }

branch = Fix . Branch
leaf   = Fix . Leaf

-- | This is an example algebra.
evalSum (Branch xs) = sum xs
evalSum (Leaf   i ) =     i

cata f = f . fmap (cata f) . unFix

现在，我几乎可以做任何我想做的事，例如，对叶子求和:

λ cata evalSum $ branch [branch [leaf 1, leaf 2], leaf 3]
6

这是我专门为这个问题准备的一个人为的示例，但实际上我尝试了一些不太琐碎的事情(例如使用任意数量的变量来评估和简化多项式)，并且它就像一个魅力。一个可能确实折叠并且作为一个贯穿一个catamorphism，与适当选择的代数替换的结构的任何部分。因此，我很确定F代数包含一个Foldable，甚至它似乎也包含Traversable。

现在，我可以根据F代数定义可折叠/可遍历实例吗？

在我看来，我做不到。

我只能对初始代数(它是无效类型的构造函数)运行分解。我提供的代数的类型为a b -> b而不是a -> b，也就是说，“输入”和“输出”类型之间存在功能依赖关系。

我在类型签名中的任何地方都看不到Algebra a => Foldable a。如果不这样做，那一定是不可能的。

在我看来，我无法用F代数来定义Foldable，原因是Expr必须为此两个变量中的Functor:一个用于载体，另一个用于值，然后在第二个中使用Foldable。因此，可能是bifunctor更合适。我们还可以构造带有双功能的F代数:

module Algebra2 where

import Data.Bifunctor

data Expr a i = Branch [a] | Leaf i

instance Bifunctor Expr where
    bimap f _ (Branch xs) = Branch (fmap f xs)
    bimap _ g (Leaf   i ) = Leaf   (g i)

newtype Fix2 a i = Fix2 { unFix2 :: a (Fix2 a i) i }

branch = Fix2 . Branch
leaf   = Fix2 . Leaf

evalSum (Branch xs) = sum xs
evalSum (Leaf   i ) =     i

cata2 f g = f . bimap (cata2 f g) g . unFix2

它像这样运行:

λ cata2 evalSum (+1) $ branch [branch [leaf 1, leaf 2], leaf 3]
9

但是我仍然不能定义一个可折叠的。它将具有以下类型:

instance Foldable \i -> Expr (Fix2 Expr i) i where ...

不幸的是，没有一个关于类型的lambda抽象，也没有办法一次将隐式类型变量放在两个地方。

我不知道该怎么办。

最佳答案

F代数定义了一个配方，用于在评估所有子代之后评估递归数据结构的单个级别。 Foldable定义了一种评估(不一定是递归)数据结构的方法，只要您知道如何将存储在其中的值转换为monoid的元素即可。

要为递归数据结构实现foldMap，您可以先定义一个代数，其载体是一个单面体。您将定义如何将叶子转换为单调值。然后，假设将节点的所有子级都评估为单调值，则可以定义一种在节点内组合它们的方法。定义了这样的代数后，就可以运行同构函数来评估整个树的foldMap。

因此，您的问题的答案是，要为定点数据结构创建Foldable实例，您必须定义一个适当的代数，其载体是一个类半体。

编辑:这是可折叠的实现:

data Expr e a = Branch [a] | Leaf e

newtype Ex e = Ex { unEx :: Fix (Expr e) }

evalM :: Monoid m => (e -> m) -> Algebra (Expr e) m
evalM _ (Branch xs) = mconcat xs
evalM f (Leaf   i ) = f i

instance Foldable (Ex) where
  foldMap f = cata (evalM f) . unEx

tree :: Ex Int
tree = Ex $ branch [branch [leaf 1, leaf 2], leaf 3]

x = foldMap Sum tree

将Traversable实现为同构关系要复杂得多，因为您希望结果不只是一个摘要-它必须包含完整的重构数据结构。因此，代数的载体必须是traverse的最终结果的类型，即(f (Fix (Expr b)))，其中f是Applicative。

tAlg :: Applicative f => (e -> f b) -> Algebra (Expr e) (f (Fix (Expr b)))

这是代数:

tAlg g (Leaf e)    = leaf   <$> g e
tAlg _ (Branch xs) = branch <$> sequenceA xs

这就是实现traverse的方式:

instance Traversable Ex where
  traverse g = fmap Ex . cata (tAlg g) . unEx

Traversable的父类(super class)是Functor，因此您需要证明定点数据结构是仿函数。您可以通过实现一个简单的代数并对其进行分类处理来实现:

fAlg :: (a -> b) -> Algebra (Expr a) (Fix (Expr b))
fAlg g (Leaf e) = leaf (g e)
fAlg _ (Branch es) = branch es

instance Functor Ex where
  fmap g = Ex . cata (fAlg g) . unEx

(Michael Sloan帮助我编写了此代码。)

关于haskell - 一旦有了F代数，是否可以根据它定义可折叠和可遍历？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48488021/