Data Types Homework

The Lambda Calculus in Haskell

Haskell itself is a direct mapping to the Lambda Calculus, as taught previously. However, the Lambda Calculus can also be represented and β-reduced in Haskell.

data LambdaCalc = Var String | Lambda String LambdaCalc | App LambdaCalc LambdaCalc

βReduce :: LambdaCalc -> LambdaCalc
βReduce l@(Lambda _ _) = l
βReduce (App (Lambda id exp1) exp2) = βReduce (subst id exp1 exp2)

subst :: String -> LambdaCalc -> LambdaCalc
subst id x@(Var z) exp
  | z == id = exp
  | otherwise = x
subst id (Lambda x exp1) exp
  | id == x = exp1
  | otherwise = subst id exp1 exp
subst id (App exp1 exp2) exp = App (subst id exp1 exp) (subst id exp2 exp)

It should be noted that pattern-matching using an @ labels the whole expression as that variable. For example,

foo b@(Bar x y) = ...

Allows foo to use x and y as variables representing parts of Bar, but also can use b as a variable representing all of (Bar x y).

Homework

1. Write a data definition for XML. If you are afraid of XML but know HTML, write a generalized data definition for HTML instead.
2. Write the function removeAttribs :: XML -> XML that takes an XML data type, x, as defined in part one and returns x with all attributes removed.
3. Write the function xmlToString :: XML -> String that takes an XML data type, x, as defined in part one and returns actual XML in string form. This is a challenging problem.