Fun with Functions! - Exercises & Solutions

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?

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.

type Bool = forall a. a -> a -> a

_true :: Bool
_true t _ = t

_false :: Bool
_false _ f = f

-- Bonus	    
type Either a b = forall z. (a -> z) -> (b -> z) -> z
    
left :: forall a b. a -> Either a b
left a = \l _ -> l a

right :: forall a b. b -> Either a b
right b = \_ r -> r b
    
type Bool2 = forall a. a -> Either a a

true2 :: Bool2
true2 = left

right2 :: Bool2
right2 = right

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?

Bonus: Define a function, called optionMap, which takes an optional value, and a function which can transform the value, and returns another optional value.
```
type Maybe a = forall z. z -> (a -> z) -> z

nothing :: forall a. Maybe a
nothing = const

just :: forall a. a -> Maybe a
just a = \_ f -> f a

-- Bonus
optionMap :: forall a b. (a -> b) -> Maybe a -> Maybe b
optionMap f o = o nothing (\a -> just (f a))
```

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).

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.

type List a = forall z. z -> (z -> a -> z) -> z

nil :: forall a. List a
nil = \z _ -> z

cons :: forall a. a -> List a -> List a
cons a as = \z f -> as (f z a) f

-- Bonus
reverse :: forall a. List a -> List a
reverse l = l nil (\as a -> cons a as)

listMap :: forall a b. (a -> b) -> List a -> List b
listMap f as = reverse (as nil (\bs a -> cons (f a) bs))

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.

type Tuple a b = forall z. (a -> b -> z) -> z

tuple2 :: forall a b. a -> b -> Tuple a b
tuple2 a b = \f -> f a b

-- Bonus
type Tuple3 a b c = forall z. (a -> b -> c -> z) -> z

tuple3 :: forall a b c. a -> b -> c -> Tuple3 a b c
tuple3 a b c = \f -> f a b c

-- etc.

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.

type Either a b = forall z. (a -> z) -> (b -> z) -> z

left :: forall a b. a -> Either a b
left a = \l _ -> l a

right :: forall a b. b -> Either a b
right b = \_ r -> r b

type Either3 a b c = forall z. (a -> z) -> (b -> z) -> (c -> z) -> z

either3_1 :: forall a b c. a -> Either3 a b c
either3_1 a = \f _ _ -> f a

either3_2 :: forall a b c. b -> Either3 a b c
either3_2 b = \_ f _ -> f b

either3_3 :: forall a b c. c -> Either3 a b c
either3_3 c = \_ _ f -> f c

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.
```
type Nat = forall z. z -> (z -> z) -> z

_zero :: Nat
_zero = \z s -> z

succ :: Nat -> Nat
succ n = \z s -> s (n z s)

plus :: Nat -> Nat -> Nat
plus n m = \z s -> m (n z s) s
```
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).
```
type WriteError = Nat
type WriteStd   = Nat

type Command = forall z. (WriteError -> z) -> (WriteStd -> z) -> z

writeError :: Nat -> Command
writeError n = \err _ -> err n

writeStandard :: Nat -> Command
writeStandard n = \_ std -> std n
```

Cheat and develop an "interpreter" which can take a list of write-only commands, and actually perform their effects!

interpret l = l (log "") eval
  where
    eval eff command = do 
      eff
      command (\n -> log ("Error: " ++ show (showNat n))) (\n -> log ("Std: " ++ show (showNat n)))

jdegoes/fun-functions.md