Assignment #6: Lazy Evaluation and Logic Programming in ML

Problem 1. Consider the following representation of a polymorphically typed infinite list in ML: datatype 'a inf_list = lcons of 'a * (unit -> 'a inf_list) The above datatype assumes the use of a ‘thunk’ as part of the infinite list representation – hence the presence of the type (unit -> 'a inf_list) in the representation. Consider strings of the form: “Lf.Lx.(f x)” “Lf.Lx.(f (f x))” “Lf.Lx.(f (f (f x)))” “Lf.Lx.(f (f (f (f x))))” “Lf.Lx.(f (f (f (f (f x)))))” … These strings represent the numbers 1, 2, 3, 4, 5, … in the pure lambda-calculus. Here, L stands for λ. Each string is called a Church numeral – in honor of Alonzo Church who invented the λ-calculus. a. Define a function church: string -> string inf_list which generates an infinite list of Church numerals starting from 1. The input to the function church is a string “x”. b. Define a function zip: 'a inf_list * 'b inf_list -> ('a * 'b) inf_list which takes two infinite lists, pairs up the corresponding elements, and produces an output infinite list. Test out church and zip by executing the following “main” program: fun nums(n) = let fun thk() = nums(n+1) in lcons(n, thk) end; fun take(0, _) = [] | take(n, lcons(h, thk)) = h :: take(n-1, thk()); let val l1 = nums(1); val l2 = church("x") in take(5, zip(ll,l2)) end; Submit one file called [login to view URL] with the datatype inf_list and all relevant definitions.