编译器了解
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
,因此cata lenAlg实际上没有起到任何作用。
让我们看一下
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))
这里似乎出了些问题。麻烦在将 ListF
回滚到常规列表时,我们忘记执行与 unFix
相反的操作。我将称此函数为
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
也就是说,在 ListF
上的 fmap
只是将函数应用于类型的“递归部分”。
我将切换 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
请参见有关Haskell中的catamorphisms的我的其他答案。
X
作为数据构造函数,以避免混淆。Fix
是类型构造函数。因此,类型Fix(ListF e)
符合定义newtype Fix f = X(f(Fix f))
,其中类型参数f
变为(ListF e)
。因此,通过替换,我们得到类型f(Fix f)
为ListF e(Fix(ListF e))
。而ListF
有两个数据构造函数情况。这就是我所说的那两个非正式的“方程式”的意思。 - Will NessFix f
是类型f
的类型级不动点。一个Haskell实现只是遵循定义,就像我在我的回答中展示的那样。对于它来说,类型Fix(ListF e)
或ListF e(Fix(ListF e))
只是另一种类型。 - Will NessFix
" 只是另一种类型名称。它可以被命名为 "T
",对它来说都无所谓。 :) 数据构造函数也是如此,这就是我在那里使用 "X
" 的原因。 - Will Ness