编译器如何计算出仿函数的不动点以及 cata 如何在叶级别工作？

Question

我想理解函子不动点的抽象概念，但是，我仍在努力弄清楚它的确切实现及其在 Haskell 中的变形。

例如，如果我定义，按照"Category Theory for Programers"的书——第359页，下面的代数

-- (Int, LiftF e Int -> Int)

data ListF e a = NilF | ConsF e a

lenAlg :: ListF e Int -> Int
lenAlg (ConsF e n) -> n + 1
lenAlg NilF = 0

根据变形的定义，可以将以下函数应用于 ListF 的不动点（即 List）以计算其长度。

cata lenAlg :: [e] -> Int
cata lenAlg = lenAlg . fmap (cata lenAlg) . unFix

我有两个困惑。首先，Haskell 编译器如何知道 List 是 ListF 的 THE 不动点？我在概念上知道它是，但编译器怎么知道，即，如果我们定义另一个与 List 完全相同的 List'，我敢打赌编译器不会自动推断 List' 也是 ListF 的固定点，或者它？（我会很惊讶）。

其次，由于cata lenAlg的递归特性，它总是试图unFix数据构造函数的外层以暴露仿函数的内层（顺便说一句，我的这种解释是否正确？）。但是，如果我们已经在叶子节点，我们如何调用这个函数呢？

fmap (cata lenAlg) Nil

例如，有人可以帮助为以下函数调用编写执行跟踪以澄清吗？

cata lenAlg Cons 1 (Cons 2 Nil)

我可能遗漏了一些明显的东西，但我希望这个问题对其他有类似困惑的人仍然有意义。

答案摘要

@n.m。通过指出为了 Haskell 编译器找出 Functor A 是 Functor B 的不动点来回答我的第一个问题，我们需要明确。在这种情况下，它是

type List e = Fix (ListF e)

@luqui 和@Will Ness 指出，由于 fmap 的定义，在叶子上调用 fmap (cata lenAlg)，在这种情况下是 NilF，将 return NilF 返回。

-- f :: a -> b
fmap f (ConsF e a) = ConsF e (f b)
fmap f NilF        = NilF

我会接受@n.m. 的回答，因为它直接解决了我的第一个（更大的）问题，但我确实喜欢所有三个答案。非常感谢您的帮助！

Answer 1

不，unFix 暴露结构，然后 fmap f 在其上应用函数 f。如果它是一片叶子，fmap f 将执行它为叶子定义的事情——即什么都不做。 fmap 即 "knows" 被定义为处理每种情况，就像 Haskell 的基于案例的定义一样。

Fix (ListF e) = ListF e (Fix (ListF e)) 
              = NilF | ConsF e (Fix (ListF e))

所以将 Fix (ListF e) 重命名为 Listof e 我们得到

Listof     e  = NilF | ConsF e (Listof e)

Listof e是递归类型。 ListF e r 是一种非递归类型。 Fix 从中生成递归类型。 ListF e 作为一个 Functor 意味着 fmap 在 r "meat" 上工作，ListF e 是这个 "fruit" 的 "hard outer shell"。

data ListF e a = NilF | ConsF e a

newtype Fix f = X { unFix    :: (f       (Fix f)) }

-- unFix ::    Fix f          -> f       (Fix f        )
-- unFix (_ :: Fix (ListF e)) :: ListF e (Fix (ListF e))

lenAlg :: ListF e Int -> Int
lenAlg (ConsF e n) = n + 1
lenAlg NilF        = 0

instance Functor (ListF e) where
    -- fmap :: (a -> b) -> (ListF e a) -> (ListF e b)
    fmap f NilF        = NilF
    fmap f (ConsF e r) = ConsF e (f r)

cata :: (ListF e Int -> Int) -> Fix (ListF e) -> Int
cata lenAlg x = (lenAlg . fmap (cata lenAlg) . unFix) x
              =  lenAlg ( fmap (cata lenAlg) ( unFix  x ))
--------
        x       ::       Fix (ListF e)
        unFix x ::            ListF e (Fix (ListF e))
        fmap (cata lenAlg) :: ListF e (Fix (ListF e)) -> ListF e (Int)
              cata lenAlg  ::          Fix (ListF e)  ->          Int

        fmap (cata lenAlg)   (unFix  x              ) :: ListF e  Int 
 lenAlg (_                                            :: ListF e  Int ) :: Int

看到了吗？所有的电线都到它们正确的位置。 fmap 递归地变换内部 r，然后 lenAlg algebra 应用 one 最后一个变换，one 最后 step 折叠结构，其中所有内部部分都已经折叠成 r递归 r 结果。从而产生最终的r结果。

作为一个具体的例子，对于两个数字 1 和 2 的列表，我们有

-- newtype Fix f  = X { unFix :: (f      (Fix f         )) }
--             _\_______       ____\____      _\________
onetwo :: Fix (ListF Int) -- ~ ListF Int (Fix (ListF Int))
onetwo = X (ConsF 1
                  (X (ConsF 2
                            (X NilF))))

cata lenAlg :: Fix (ListF e) -> Int
cata lenAlg    onetwo
  = {- definition of cata   -}
    lenAlg . fmap (cata lenAlg) . unFix  $ onetwo
  = {- definition of onetwo -}
    lenAlg . fmap (cata lenAlg) . unFix  $ 
                           X (ConsF 1 (X (ConsF 2 (X NilF))))
  = {- definition of unFix  -}
    lenAlg . fmap (cata lenAlg) $ 
                              ConsF 1 (X (ConsF 2 (X NilF)))
  = {- definition of fmap   -}
    lenAlg $ ConsF 1 (cata lenAlg     (X (ConsF 2 (X NilF))))
  = {- definition of lenAlg -}
    (+ 1)  $          cata lenAlg     (X (ConsF 2 (X NilF)))
  = {- definition of cata   -}
    (+ 1)  $ lenAlg . fmap (cata lenAlg) . unFix $ 
                                       X (ConsF 2 (X NilF))
  = {- definition of unFix  -}
    (+ 1) $ lenAlg . fmap (cata lenAlg) $ ConsF 2 (X NilF)
  = {- definition of fmap   -}
    (+ 1) $ lenAlg $ ConsF 2 $ cata lenAlg        (X NilF)
  = {- definition of lenAlg -}
    (+ 1) $ (+ 1)  $           cata lenAlg        (X NilF)
  = {- definition of cata   -}
    (+ 1) $ (+ 1)  $ lenAlg . fmap (cata lenAlg) . unFix $ 
                                                  (X NilF)
  = {- definition of unFix  -}
    (+ 1) $ (+ 1)  $ lenAlg . fmap (cata lenAlg) $   NilF
  = {- definition of fmap   -}
    (+ 1) $ (+ 1)  $ lenAlg $                        NilF
  = {- definition of lenAlg -}
    (+ 1) $ (+ 1)  $ 0
  = (+ 1) $ 1
  = 2

此外，

squaringAlg :: ListF Int [Int] -> [Int]
squaringAlg (ConsF e r) = e*e : r
squaringAlg NilF        = []

filteringAlg :: (e -> Bool) -> ListF e [e] -> [e]
filteringAlg p (ConsF e r) | p e       = e : r
                           | otherwise = r
filteringAlg _ NilF                    = []

等等

Answer 2

编译器知道 ListF e 和 [e] 之间关系的唯一方法是告诉它。您没有提供足够的上下文来准确回答如何，但我可以推断 unFix 具有类型

unFix :: [e] -> ListF e [e]

也就是展开顶层。 unFix 可能更通用，例如在 recursion-schemes 中，类型族用于将数据类型与其底层函子相关联。但这就是这两种类型的联系所在。

关于你的第二个问题，你需要更清楚什么时候有列表，什么时候有ListF。他们是完全不同的。

fmap (cata lenAlg) Nil

在这里，您要映射的仿函数是 ListF e，您可以随意使用 e。也就是这个fmap:

fmap :: (a -> b) -> ListF e a -> ListF e b

如果你自己实现 instance Functor (ListF e)（总是一个很好的练习）并让它编译，你会发现 Nil 必须映射到 Nil，所以 [=30= 】一点都不重要。

我们来看看Cons 1 (Cons 2 Nil)的类型：

Nil                 :: ListF e a
Cons 2 Nil          :: ListF Int (ListF e a)
Cons 1 (Cons 2 Nil) :: ListF Int (ListF Int (ListF e a))

这里出了点问题。问题在于我们忘记执行 unFix 的相反操作，将 ListF 回滚到常规列表中。我会调用这个函数

roll :: ListF e [e] -> [e]

现在我们有

Nil                                      :: ListF e a
roll Nil                                 :: [e]
Cons 2 (roll Nil)                        :: ListF Int [Int]
roll (Cons 2 (roll Nil))                 :: [Int]
Cons 1 (roll (Cons 2 (roll Nil)))        :: ListF Int [Int]
roll (Cons 1 (roll (Cons 2 (roll Nil)))) :: [Int]

类型现在保持美观和小巧，这是一个好兆头。对于执行跟踪，我们只需要注意 unFix . roll = id，无论它们如何工作。重要的是要注意

fmap f (Cons a b) = Cons a (f b)
fmap f Nil        = Nil

也就是说，fmap on ListF 只是将函数应用于类型的 "recursive part"。

我打算将 Cons 的情况切换为 lenAlg (ConsF e n) = 1 + n 以使跟踪更易读。还是有点乱，祝你好运。

cata lenAlg (roll (Cons 1 (roll (Cons 2 (roll Nil)))))
(lenAlg . fmap (cata lenAlg) . unFix) (roll (Cons 1 (roll (Cons 2 (roll Nil)))))
lenAlg (fmap (cata lenAlg) (unFix (roll (Cons 1 (roll (Cons 2 (roll Nil)))))))
lenAlg (fmap (cata lenAlg) (Cons 1 (roll (Cons 2 (roll Nil)))))
lenAlg (Cons 1 (cata lenAlg (roll (Cons 2 (roll Nil)))))
1 + cata lenAlg (roll (Cons 2 (roll Nil)))
1 + (lenAlg . fmap (cata lenAlg) . unFix) (roll (Cons 2 (roll Nil)))
1 + lenAlg (fmap (cata lenAlg) (unFix (roll (Cons 2 (roll Nil)))))
1 + lenAlg (fmap (cata lenAlg) (Cons 2 (roll Nil)))
1 + lenAlg (Cons 2 (cata lenAlg (roll Nil)))
1 + 1 + cata lenAlg (roll Nil)
1 + 1 + (lenAlg . fmap (cata lenAlg) . unFix) (roll Nil)
1 + 1 + lenAlg (fmap (cata lenAlg) (unFix (roll Nil)))
1 + 1 + lenAlg (fmap (cata lenAlg Nil))
1 + 1 + lenAlg Nil
1 + 1 + 0
2

另见 my other answer 关于变形。

Answer 3

"List is the fixed point of ListF"是一个快活的修辞格。而fast and loose reasoning is morally correct，你总是需要牢记无聊正确的事情。具体如下：

ListF e 的任何最小不动点同构于 [e].

现在 "the compiler"（顺便说一句，这是 "the Haskell language" 的一个简单的词）不知道这种同构。你可以整天写同构类型

data []    x = []   | (:)   x ([]    x)    -- the imaginary built-in definition of []
data ListA x = NilA | ConsA x (ListA x)
data ListB x = NilB | ConsB x (ListB x)
data ListC x = NilC | ConsC x (ListC x)

并且编译器永远不会将它们视为 "the same type"。它也不会知道 ListF e 的固定点与 [e] 相同，或者实际上什么是固定点。如果你想使用这些同构，你需要通过编写一些代码（例如通过定义 Data.Types.Isomorphic 的实例）来告诉编译器它们，然后每次你想使用它时明确指定同构！

说到这里，再看看cata你定义的。首先映入眼帘的是定义类型签名的尝试是一个语法错误。让我们删除它，只在 GHCi 中定义函数（我将参数名称更改为 f 以避免混淆，并修复了 ListF 定义中的一些错别字）

Main> data ListF e a = NilF | ConsF e a
Main> let lenAlg :: ListF e Int -> Int
Main|     lenAlg (ConsF e n) = n + 1
Main|     lenAlg NilF = 0
Main|
Main>
Main> :m + Data.Fix
Main Data.Fix> cata f = f . fmap (cata f) . unFix
Main Data.Fix> :t cata
cata :: Functor f => (f b -> b) -> Fix f -> b
Main Data.Fix> :t cata lenAlg
cata lenAlg :: Functor (ListF e) => Fix (ListF e) -> Int

这表示要使用 lenAlg，您需要：

为 ListF e

Functor

明确使用Fix (ListF e)（即ListF 的a 定点）。希望 "the fixpoint of ListF" 存在是行不通的。没有魔法。

所以让我们这样做：

Main Data.Fix> instance Functor (ListF e) where
Main Data.Fix|     fmap f NilF = NilF
Main Data.Fix|     fmap f (ConsF e a) = ConsF e (f a)
Main Data.Fix>
Main Data.Fix> :t cata lenAlg
cata lenAlg :: Fix (ListF e) -> Int

太好了，现在我们可以计算基于 ListF 的 Fix-wrapped 列表的长度了。但是让我们先定义一些辅助定义。

Main Data.Fix> type List e = Fix (ListF e)
Main Data.Fix> nil = Fix (NilF)
Main Data.Fix> let infixr 7 ~~                   -- using an infix operator for cons
Main Data.Fix|     h ~~ t = Fix (ConsF h t)
Main Data.Fix|
Main Data.Fix>
Main Data.Fix> myList = (1::Int) ~~ 2 ~~ 3 ~~ 4 ~~ nil
Main Data.Fix> :t myList
myList :: Fix (ListF Int)

这是我们的 "list"（准确地说是 [Int] 同构类型的成员）。让我们 cata lenAlg 它：

Main Data.Fix> cata lenAlg myList
4

成功！

底线：编译器什么都不知道，你需要解释一切。

编译器如何计算出仿函数的不动点以及 cata 如何在叶级别工作？

How does compiler figure out fixed point of a functor and how cata work at leaf level?

haskell

category-theory

recursion-schemes

fixpoint-combinators

catamorphism