{# —— Umami 统计(Cloud 版)—— #}

5.2.8

 

题目

A list can be represented in the lambda-calculus by its fold function. (OCaml’s name for this function is fold_left; it is also sometimes called reduce .) For example, the list [x,y,z]becomes a function that takes two arguments c and n and returns c x (c y (c z n))).What would the representation of nil be? Write a function cons that takes an element h and a list (that is, a fold function) t and returns a similar representation of the list formed by prepending h to t. Write isnil and head functions, each taking a list parameter. Finally, write a tail function for this representation of lists (this is quite a bit harder and requires a trick analogous to the one used to define prd for numbers).

解答

nil=flscons=λh. λt. λc. λn. c. h. (t c n)isnil=λt. t (λh. λb. fls) truhead=λt. (λh. λn. h) flshh=pair nil nilcc=λh. λn. pair (snd n) (cons h (snd n))tail=λt. fst (t cc hh)

额外写一个取尾部元素的函数 end

d=λh. λn. (isnil (snd n)) (pair h tru)) nend=λt. fst (t d hh)