Chapter 1: All You Need is Lambda

This note captures my solutions to exercises in Chapter 1: All You Need is Lambda of the book Haskell programming from first principles

Intermission: Equivalence Exercises

1. $\lambda x y . x z$ is equivalent to (b) $\lambda m n . m z.$

2. $\lambda x y . x x y$ is equivalent to (c) $\lambda a . (\lambda b . a a b).$

3. $\lambda x y z . z x$ is equivalent to (b) $\lambda t o s . s t.$

Combinators Exercise

1. $\lambda x.xxx$ is a combinator.

2. $\lambda xy.zx$ is not a combinator because $z$ is a free variable.

3. $\lambda xyz.xy(zx)$ is a combinator.

4. $\lambda xyz.xy(zxy)$ is a combinator.

5. $\lambda xy.xy(zxy)$ is not a combinator because $z$ is a free variable.

Normal form or diverge

1. $\lambda x.xxx$ is a normal form.

2. $(\lambda z.zz)(\lambda y.yy)$ diverges.

3. $(\lambda x.xxx)z$ can be reduced to the normal form, $zzz$.

Beta reduce

1. $(\lambda abc.cba)zz(\lambda wv.w)$ reduces to $z$.

2. $(\lambda x . \lambda y .xyy)(\lambda a.a)b$ reduces to $bb$.

3. $(\lambda y .y)(\lambda x.xx)(\lambda z.zq)$ reduces to $qq$.

4. $(\lambda z.z)(\lambda z.zz)(\lambda z.zy)$ reduces to $yy$.

5. $(\lambda x. \lambda y.xyy)(\lambda y.y)y$ reduces to $yy$.

6. $(\lambda a.aa)(\lambda b.ba)c$ reduces to $aac$.

7. $(\lambda xyz.xz(yz))(\lambda x.z)(\lambda x.a)$ reduces to $(\lambda z1.za)$.

Since the book has solutions for the chapter exercises, refer to Haskell programming from first principles for detailed solutions.