Assignment #6: Lazy Evaluation and Logic Programming in ML
$10-30 USD
Concluído
Publicado há aproximadamente 9 anos
$10-30 USD
Pago na entrega
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.