哈斯克尔的教堂名单

我必须实现 haskell 地图函数来处理教堂列表，其定义如下：

type Churchlist t u = (t->u->u)->u->u

在 lambda 演算中，列表的编码如下：

[] := λc. λn. n
[1,2,3] := λc. λn. c 1 (c 2 (c 3 n))

本练习的示例解决方案是：

mapChurch :: (t->s) -> (Churchlist t u) -> (Churchlist s u)
mapChurch f l = \c n -> l (c.f) n

我不知道这个解决方案是如何工作的，也不知道如何创建这样的函数。我已经有了 lambda 演算和教会数字的经验，但是这个练习对我来说是一个很大的头痛，我必须能够理解并解决这些问题，以便下周的考试。有人可以给我一个好的资源，让我可以学习解决此类问题，或者给我一些关于它如何工作的指导吗？

所有 lambda 演算数据结构都是函数，因为这就是 lambda 演算中的全部内容。这意味着布尔值、元组、列表、数字或任何东西的表示必须是表示该事物的活动行为的函数。

对于列表来说，它是一个“折叠”。通常定义不可变的单链表List a = Cons a (List a) | Nil，这意味着构建列表的唯一方法是Nil or Cons anElement anotherList。如果你用 lisp 风格写出来，其中c is Cons and n is Nil，然后是列表[1,2,3]看起来像这样：

(c 1 (c 2 (c 3 n)))

当您对列表执行折叠时，您只需提供自己的“Cons" and "Nil" 来替换列表中的。在 Haskell 中，用于此目的的库函数是foldr

foldr :: (a -> b -> b) -> b -> [a] -> b

看起来熟悉？取出[a]并且你的类型完全相同Churchlist a b。就像我说的，教会编码将列表表示为它们的折叠函数。

所以这个例子定义了map。注意如何l用作函数：毕竟，它是折叠某些列表的函数。\c n -> l (c.f) n基本上是说“替换每个c with c . f和每一个n with n".

(c 1 (c 2 (c 3 n)))
-- replace `c` with `(c . f)`, and `n` with `n`
((c . f) 1 ((c . f) 2) ((c . f) 3 n)))
-- simplify `(foo . bar) baz` to `foo (bar baz)`
(c (f 1) (c (f 2) (c (f 3) n))

现在应该很明显，这确实是一个映射函数，因为它看起来和原来的一样，除了1转换成(f 1), 2 to (f 2), and 3 to (f 3).