一旦我有了 F 代数，我可以用它来定义 Foldable 和 Traversable 吗？

Question

我根据 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

这是我专门为这个问题编造的一个人为的例子，但我实际上尝试了一些不那么琐碎的事情（比如评估和简化具有任意数量变量的多项式）并且它非常有效。 One may indeed fold and replace any parts of a structure as one 运行s a catamorphism through, with a suitably chosen algebra.所以，我很确定 F-Algebra 包含 Foldable，它甚至似乎也包含 Traversable。

现在，我可以根据 F 代数定义 Foldable / Traversable 实例吗？

我觉得我做不到。

我只能运行 初始代数 的变质，它是零类型构造函数。而我给它的代数类型是a b -> b而不是a -> b，也就是说，"in"和"in"之间存在函数依赖 "out"类型。
我在类型签名中的任何地方都没有看到 Algebra a => Foldable a。如果不这样做，那肯定是不可能的。

在我看来，我无法根据 F 代数定义 Foldable，因为 Expr 必须是两个变量中的 Functor：一个对于 carrier，另一个对于 values，然后是第二个 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 抽象，也没有办法同时将隐含类型变量放在两个地方。

我不知道该怎么办。

Answer 1

F 代数定义了一个方法，用于在评估完所有子项后评估递归数据结构的单个级别。 Foldable 定义了一种评估（不一定是递归的）数据结构的方法，前提是您知道如何将存储在其中的值转换为幺半群的元素。

要为递归数据结构实现foldMap，您可以从定义一个代数开始，其载体是幺半群。您将定义如何将叶子转换为幺半群值。然后，假设一个节点的所有子节点都被评估为幺半群值，您将定义一种将它们组合在一个节点内的方法。一旦你定义了这样一个代数，你就可以运行一个变形来评估整个树的 foldMap 。

所以你的问题的答案是，要为定点数据结构创建一个 Foldable 实例，你必须定义一个合适的代数，其载体是幺半群。

编辑：这是 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的超类是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 帮我写了这段代码。）

Answer 2

非常好，您使用了 Bifunctor。使用基本函子 (Expr) 的 Bifunctor 在定点 (Fix Expr) 上定义 Functor。这种方法也适用于 Bifoldable 和 Bitraversable（它们现在在 base）。

让我们看看如何使用 recursion-schemes。它看起来有点不同，因为我们定义了普通的递归类型，比如说 Tree e，还有它的基函子：Base (Tree e) = TreeF e a 有两个函数： project :: Tree e -> TreeF e (Tree e) 和 embed :: TreeF e (Tree e) -> Tree e。递归机制可以使用 TemplateHaskell:

请注意，我们有 Base (Fix f) = f（project = unFix、embed = Fix），因此我们可以使用 refix 将 Tree e 转换为 Fix (TreeF e) 并返回。但我们不需要使用 Fix，因为我们可以直接 cata Tree！

首先包括：

{-# LANGUAGE TemplateHaskell, KindSignatures, TypeFamilies, DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
import Data.Functor.Foldable
import Data.Functor.Foldable.TH

import Data.Bifunctor
import Data.Bifoldable
import Data.Bitraversable

然后是数据：

data Tree e = Branch [Tree e] | Leaf e deriving Show

-- data TreeF e r = BranchF [r] | LeafF e
-- instance Traversable (TreeF e)
-- instance Foldable (TreeF e)
-- instance Functor (TreeF e)
makeBaseFunctor ''Tree

现在我们有了机器，我们可以进行变形

cata :: Recursive t => (Base t a -> a) -> t -> a
cata f = c where c = f . fmap c . project

或（我们稍后需要）

cataBi :: (Recursive t, Bifunctor p, Base t ~ p x) => (p x a -> a) -> t -> a
cataBi f = c where c = f . second c . project

首先是一个 Functor 实例。 TreeF 的 Bifunctor 实例如 OP 所写，请注意 Functor 是如何自行脱落的。

instance Bifunctor TreeF where
    bimap f _ (LeafF e)    = LeafF (f e)
    bimap _ g (BranchF xs) = BranchF (fmap g xs)

instance Functor Tree where
    fmap f = cata (embed . bimap f id)

毫不奇怪，可以根据基数的Bifoldable定义固定点的Foldable 仿函数：

instance Bifoldable TreeF where
    bifoldMap f _ (LeafF e)    = f e
    bifoldMap _ g (BranchF xs) = foldMap g xs

instance Foldable Tree where
    foldMap f = cata (bifoldMap f id)

最后 Traversable:

instance Bitraversable TreeF where
    bitraverse f _ (LeafF e)    = LeafF <$> f e
    bitraverse _ g (BranchF xs) = BranchF <$> traverse g xs

instance Traversable Tree where
    traverse f = cata (fmap embed . bitraverse f id)

如您所见，定义非常简单明了并且遵循类似的图案。

事实上我们可以为每个固定点定义类似 traverse 的函数仿函数是 Bitraversable.

traverseRec
    :: ( Recursive t, Corecursive s, Applicative f
       , Base t ~ base a, Base s ~ base b, Bitraversable base)
    => (a -> f b) -> t -> f s
traverseRec f = cataBi (fmap embed . bitraverse f id)

这里我们使用 cataBi 使类型签名更漂亮：没有 Functor (base b) 作为 Bitraversable base "implied"。顺便说一句，这是一个很好的功能，因为它类型签名比实现长三倍）。

总而言之，我必须提到 Haskell 中的 Fix 并不完美：我们使用最后一个参数来修复 base-functor：

Fix :: (* -> *) -> * -- example: Tree e ~ Fix (TreeF e)

因此 Bartosz 需要在他的回答中定义 Ex 以使类型对齐，然而，修复第一个参数会更好：

Fix :: (* -> k) -> k -- example: Tree e = Fix TreeF' e

其中 data TreeF' a e = LeafF' e | BranchF' [a]，即 TreeF 带有索引翻转。这样我们就可以根据 Bifunctor f 得到 Functor (Fix b)， Bifunctor (Fix b)（不存在于公共库中）Trifunctor 等

您可以阅读我失败的尝试以及 Edward Kmett 的评论关于 https://github.com/ekmett/recursion-schemes/pull/23

中的问题

一旦我有了 F 代数，我可以用它来定义 Foldable 和 Traversable 吗？

Once I have an F-Algebra, can I define Foldable and Traversable in terms of it?

haskell

category-theory

recursion-schemes