January 14, 2016

These exercises were part of a LambdaConf Outpost meetup. You may find the instructions here.

Develop a model for boolean values (

`Bool`

), which may be either*true*or*false*.**Think**: Do you need an if-then-else construct? Why or why not?Example JavaScript solution:

`var True = function(ifTrue, ifFalse) { return ifTrue; } var False = function(ifTrue, ifFalse) { return ifFalse; }`

When parameterized, there are only two possible implementations of a function of type

`a -> a -> a`

, so this is a good model for boolean logic.See also Church Booleans

`true :: a -> a -> a true ifTrue ifFalse = ifTrue false :: a -> a -> a false ifTrue ifFalse = ifFalse`

**Bonus**: Develop a model for eithers (`Either`

), whih can be one thing ("left") or another ("right"), and model a boolean as a partitioning of a set into two disjoint sets.Develop a model for optional values (

`Maybe`

/`Option`

), which are containers that are either empty ("nothing" / "none") or hold a single value ("just" / "some").**Think**: If you are wrote a parametric solution in a statically-typed language, can you prove the container holds exactly 0 or 1 element, based solely on its type signature? Why or why not?`just :: a -> (a -> b) -> b -> b just a ifJust ifNothing = ifJust a nothing :: (a -> b) -> b -> b nothing ifJust ifNothing = ifNothing`

**Bonus**: Define a function, called`optionMap`

, which takes an optional value, and a function which can transform the value, and returns another optional value.Develop a model for a singly-linked list (

`List`

), which can be empty, or which can contain a head (the element at the start of the list) and a tail (the remainder of the list).`type List a b = b -> (b -> a -> b) -> b cons :: a -> List a b -> b -> (b -> a -> b) -> b cons head tail z f = tail (f z head) f nil :: b -> (b -> a -> b) -> b nil z f = z`

**Think**: Do you need to define a left fold for this model? Why or why not?**Bonus**: Define a function, called`listMap`

, which takes a list, and a function which can transform an element in the list, and returns another list.Develop a model for a container of exactly two things (

`Tuple`

), which may individually have different structures.**Think**: How can you use only`Tuple`

to define a`Tuple3`

? What are the pros and cons of this approach?**Bonus**: Define`Tuple3`

,`Tuple4`

, and so on, up to`Tuple10`

.Develop a model for a container of either one thing ("left") or another ("right"), typically called

`Either`

.**Think**: What is the relationship of`Either`

to`Tuple`

?**Bonus**: Define`Either3`

,`Either4`

, and so on, up to`Either10`

.Develop a model for natural numbers (which start at 0 and count upwards in increments of 1).

*Hint*: Try repeated application of some function to some initial value.**Think**: With this definition of natural number, how do you repeat something N times? How does this compare with repetition with a "native" natural number type?**Bonus**: Define addition and multiplication for natural numbers.**2x Bonus**: Model integers as a difference between two natural numbers, and define addition, subtraction, and multiplication.Develop a model for a couple "write-only" commands, such as "print this number to the console." This model is purely descriptive, it doesn't need to do anything!

**Think**: Why does the exercise insist these commands be "write-only"?**Bonus**: Think about approaches that might allow you to have "read" commands, that return information (for example, reading a line of input from the console).Cheat and develop an "interpreter" which can take a list of write-only commands, and actually perform their effects!

For solutions, see here.

*Don't cheat!*

```
main = putStrLn . show $
true 42 0 == 42 &&
false 0 42 == 42 &&
just 6 (\x -> x * 7) 0 == 42 &&
nothing (\x -> x * 7) 0 == 0 &&
just 6 (\x -> x * 7) 0 == 42 &&
nothing (\x -> x * 7) 0 == 0 &&
cons 6 nil 7 (\x -> \y -> x * y) == 42 &&
nil 6 (\x -> \y -> x * y) == 6 &&
True
```