Projects‎ > ‎

Project2

Lambda Calculus and Haskell


Due Wed, April 24th at 11:59pm in your git repo.

Part A - Encoding Lambda Calculus in Haskell

Recall from the Wikipedia article on Church Encoding (http://en.wikipedia.org/wiki/Church_encoding) that it is possible to encode numbers, mathematical operations, and other data types and operations directly in Lambda Calculus.  For this problem you are going to encode the church numerals and mathematical operations in Haskell.

For example, you can represent 0, 1, 2, and 3 as:

let zero = (\f x -> x)
let one = (\f x -> f x)
let two = (\f x -> f (f x))
let three = (\f x -> f (f (f x)))

You can represent succ as:

let succ = (\n f x -> f (n f x))

In order to print a church numeral as a normal integer you can use the following code from the Wikipedia page:

type Church a = (a -> a) -> (a -> a)

church :: Integer -> Church Integer
church 0 = \f -> \x -> x
church n = \f -> \x -> f (church (n-1) f x)
 
unchurch :: Church Integer -> Integer
unchurch n = n (\x -> x + 1) 0

church_succ :: Church Integer -> Church Integer
church_succ = \n f x -> f (n f x)

Represent the following operations in Haskell:

plus
mult
exp
pred
sub
zerop

Represent factorial using this lambda notation and a Y-Combinator.

Provide tests that all your new functions work.

Part B - Implement a set type in Haskell

For this problem you need to implement sets using Haskell lists.

You will implement the following functions:

new
add e s
remove e s
union s1 s2
intersect s1 s2
equal s1 s2

Provide test cases that demonstrate your functions work properly.

You can implement sets using any internal representation: lists, trees, other.  You can assume sorted lists if this helps with your implementation.


Comments