Operations on Church Lists in Haskell

Question

I am referring to this question

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

In lambda calculus, lists are encoded as following:

[] := λ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

I am thinking about what other list functions I could implement on Churchlists and successfully wrote a conc2 function that concatenates 2 church lists

conc2Church l1 l2 c n = l1 c (l2 c n)

I also tried a zipWithChurch that operates like zipWith on normal lists. But i can not find a solution. Can anyone help me?

Answer 1

Do you want to use real tuples, or church tuples? I'll assume the former.

So, start with the desired type signature. You want it to take in 2 different Churchlists and produce a Churchlist of tuples.

churchZip :: Churchlist a u -> Churchlist b u -> Churchlist (a,b) u

Now how would you implement this? Recall that Churchlists are represented by the function that folds over them. So if our result is a Churchlist (a,b) u, we'll want it to have the form of a function of the type ((a,b) -> u -> u) -> u -> u (this is, after all, the equivalent to the type synonym Churchlist (a,b) u).

churchZip l1 l2 c n = ???

What is the next step? Well, that depends. Is l1 empty? What about l2? If either of them are, then you want the result to be the empty list. Otherwise, you want to pair up the first elements from each list, and then churchZip the rest.

churchZip l1 l2 c n
  | isEmpty l1 || isEmpty l2 = n
  | otherwise                = c (churchHead l1, churchHead l2)
                                 (churchZip (churchTail l1) (churchTail l2) c n

This brings up some questions.

• Are you allowed to write this function recursively? In the pure lambda calculus, you must write recursive functions with the fixpoint operator (aka the y combinator).
• Do you have churchHead, churchTail, and isEmpty available? Are you willing to write them? Can you write them?
• Is there a better way to structure this function? Anything can be done with a fold (remember, l1 and l2 actually are the folding function over themselves), but is that a clean solution to this problem?

Getting up to this point is purely mechanical, assuming a firm understanding of the church encoding of lists. I'll leave the deep thinking up to you, since this is homework.