Fun with functions

January 14, 2016

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

  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?

    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.

  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?

    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.

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

    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.

  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.

  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.

  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.

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

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