一旦我有了一个F-代数，我能用它来定义可折叠和可遍历吗？

Question

根据Bartosz Milewski的文章（一、二），我定义了一个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

null

在我看来，我不能用F-代数定义foldable，因为expr必须是两个变量中的functor:一个表示载体，另一个表示值，然后是foldable。因此，可能双截断子更合适。我们也可以构造一个具有双截子的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 ...

Answer 1

F代数定义了在计算完所有子级之后计算递归数据结构的单个级别的方法。Foldable定义了一种计算（不一定是递归的）数据结构的方法，只要您知道如何将存储在其中的值转换为一个半群的元素。

为了实现递归数据结构的foldmap，您可以从定义一个代数开始，它的载体是一个半群。您将定义如何将叶转换为单相值。然后，假设一个节点的所有子节点都被计算为单相值，您将定义一种在一个节点中组合它们的方法。一旦定义了这样一个代数，就可以运行一个catamorphism来计算整个树的foldmap。

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

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实现为catamorphism要复杂一些，因为您希望结果不仅仅是一个摘要--它必须包含完整的重新构造的数据结构。因此，代数的载体必须是遍历的最终结果的类型，即(f(Fix(Expr b)))，其中f是application。

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

这就是如何实现遍历:

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

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