Fun with Functions! - Exercises & Solutions

fun-functions.md

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

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

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

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

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

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

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

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