我需要实现Haskell的map函数，使其能够与Church列表一起使用。Church列表定义如下：
type Churchlist t u = (t->u->u)->u->u
[] := λ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 演算和 Church 数字的经验，但这个练习让我头痛不已。下周的考试中我必须能够理解并解决这些问题。请问是否能提供一个好的资源，在那里我可以学习解决这些问题，或者给我一些关于它如何工作的指导？
所有的lambda演算数据结构都是函数，因为在lambda演算中只有函数。这意味着布尔值、元组、列表、数字或其他任何东西的表示必须是代表该物体的活动行为的某些函数。
对于列表来说，它是一种“折叠”操作。不可变的单向链表通常定义为List a = Cons a (List a) | Nil，这意味着你可以构建一个列表的唯一方法就是使用Nil或Cons anElement anotherList。如果按照lisp风格书写，其中c为Cons而n为Nil，那么列表[1,2,3]看起来像这样：
(c 1 (c 2 (c 3 n)))
当你对列表进行fold操作时，你只需提供自己的"Cons"和"Nil"来替换列表中的那些。在Haskell中，这个库函数的名称是foldr。
foldr :: (a -> b -> b) -> b -> [a] -> b
看起来很熟悉？去掉 [a]，你就得到与 Churchlist a b 完全相同的类型。正如我所说，Church编码表示列表为它们的折叠函数。
因此，这个例子定义了 map。注意到 l 被用作函数：毕竟它是某个列表上进行折叠的函数。 \c n -> l (c.f) n 基本上是在说“用 c . f 替换每一个 c 并将每一个 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变成了(f 2)，把3变成了(f 3)。
那么让我们从编码两个列表构造器开始，以您的示例为参考:
[] := λc. λn. n
[1,2,3] := λc. λn. c 1 (c 2 (c 3 n))
[] 是列表构造函数的结尾，我们可以直接从示例中使用它。由于 [] 在 Haskell 中已经有了意义，因此让我们把它称为 nil：
nil = \c n -> n
cons。定义如下：cons x xs = \c n -> c x (xs c n)
cons 1 (cons 2 (cons 3 nil))) =
cons 1 (cons 2 (cons 3 (\c n -> n)) =
cons 1 (cons 2 (\c n -> c 3 ((\c' n' -> n') c n))) =
cons 1 (cons 2 (\c n -> c 3 n)) =
cons 1 (\c n -> c 2 ((\c' n' -> c' 3 n') c n) ) =
cons 1 (\c n -> c 2 (c 3 n)) =
\c n -> c 1 ((\c' n' -> c' 2 (c' 3 n')) c n) =
\c n -> c 1 (c 2 (c 3 n)) =
mapChurch f nil
= \c n -> nil (c.f) n
= \c n -> (\c' n' -> n') (c.f) n
= \c n -> n
= nil
cons 包含一个元素和一个列表的剩余部分，因此为了使 mapChurch f 正常工作，必须将 f 应用于该元素，并将 mapChurch f 应用于列表的其余部分。也就是说，mapChurch f (cons x xs) 应该与 cons (f x) (mapChurch f xs) 相同。
mapChurch f (cons x xs)
= \c n -> (cons x xs) (c.f) n
= \c n -> (\c' n' -> c' x (xs c' n')) (c.f) n
= \c n -> (c.f) x (xs (c.f) n)
-- (c.f) x = c (f x) by definition of (.)
= \c n -> c (f x) (xs (c.f) n)
= \c n -> c (f x) ((\c' n' -> xs (c'.f) n') c n)
= \c n -> c (f x) ((mapChurch f xs) c n)
= cons (f x) (mapChurch f xs)
因此，由于所有列表都是由这两个构造函数创建的，并且 mapChurch 在它们两者上按预期工作，mapChurch 必须在所有列表上按预期工作。
-- Tell me...
type Churchlist t u = (t -> u -> u) -- ...how to handle a pair
-> u -- ...and how to handle an empty list
-> u -- ...and then I'll transform a list into
-- the type you want
foldr函数密切相关：foldr :: (t -> u -> u) -> u -> [t] -> u
foldr k z [] = z
foldr k z (x:xs) = k x (foldr k z xs)
foldr是一个非常通用的函数，可以实现各种其他列表函数。一个简单的例子是使用foldr实现列表复制：
copyList :: [t] -> [t]
copyList xs = foldr (:) [] xs
foldr (:) [] 的意思是：“如果你看到一个空列表，返回一个空列表；如果你看到一对，返回 head:tailResult。”Churchlist，你可以轻松地这样编写对应代码：-- Note that the definitions of nil and cons mirror the two foldr equations!
nil :: Churchlist t u
nil = \k z -> z
cons :: t -> Churchlist t u -> Churchlist t u
cons x xs = \k z -> k x (xs k z)
copyChurchlist :: ChurchList t u -> Churchlist t u
copyChurchlist xs = xs cons nil
现在，要实现map，您只需要用适当的函数替换cons，就像这样：
map :: (a -> b) -> [a] -> [b]
map f xs = foldr (\x xs' -> f x:xs') [] xs
映射类似于复制列表，但不仅是逐字复制元素，而是将f应用于每个元素。
仔细研究这些内容，您应该能够自己编写mapChurchlist ::(t -> t') -> Churchlist t u -> Churchlist t' u 。
额外练习（简单）：使用foldr编写这些列表函数，并编写相应的Churchlist函数：
filter :: (a -> Bool) -> [a] -> [a]
append :: [a] -> [a] -> [a]
-- Return first element of list that satisfies predicate, or Nothing
find :: (a -> Bool) -> [a] -> Maybe a
如果你感觉可以尝试一些更难的事情，可以尝试为Churchlist编写tail函数。(先使用foldr为[a]编写tail函数)