Lab 6: Higher-order operations and Monads

Overview

The goals of this lab are to:

  1. Become more familiar with higher-order operations (e.g., map, point-free style, fmap, etc.).

  2. Practice using the >>= (“bind”) operator.

  3. Work with monads, to see how a monad abstracts away (i.e., hides the unnecessary details related to) the tedious part of describing a sequence of operations.

These tasks will help you understand monads a bit better, in preparation for using them in your future work.

Materials

Use the assignment workflow and the link provided on Piazza to get access to this week’s files.

This lab should work on any computer with subversion and ghci installed; you don’t have to ssh to knuth if you don’t want to.

Part 1: Higher-order operations (25 minutes)

Open the file HigherOrderExercises.lhs. Follow the instructions in the file to review and / or learn about higher-order operations in Haskell, and to complete the exercises.

Part 2: Motivating monads (35 minutes)

In this part of the lab, we will look at an implementation of a calculator. The calculator is stack-based: It saves arguments and results on the stack. It also keeps track of a current result. Given a stack, the calculator can compute an operation (e.g., multiplication) and result in a pair: (result, stack').

Look over the implementation of the stack-based calculator

Open the file Calculator.hs and read over the implementation with your partner. Make sure the implementation makes sense to both of you. The key pieces to understand are how the stack works (which should look familiar from HW 2), the fact that each calculator operation returns a pair, and the details of how binaryOperation works.

Now open the file Program1.hs and carefully read it over with your partner. Make sure to discuss what this program does, and how it does it. What do you like about this implementation? What do you not like?

Is there a better way?

One of the things that is annoying about the current implementation is that it is hard to describe a sequence of calculations. The good news is that there is a better way, but it isn’t as simple as basic function composition.

To learn why, let’s examine the code for binaryOperation:

      binaryOperation f stack = let (right, stack1) = pop stack
                                    (left,  stack2) = pop stack1
                                    result = f left right
                                    (_, stack3) = push result stack2
                                in (result, stack3)

It would be nice if we could instead write something similar to:

  right = pop
  left  = pop
  result = f left right
  push result
  result

If we compare what we want to say against what we currently say, we notice two things:

  1. Our current way forces us to explicitly pass the stack the results from one operation as an input to the next operation. For example, when we call pop with stack1.

  2. Sometimes we want to use the value of the computation (for example, after we pop) and sometimes we don’t (for example, after we push).

Instead, let’s see if we can find a way to sequence operations that lets us:

A. avoid having to describe how to pass the updated stack from one operation to the next, and

B. describe how to take the value from a previous calculator operation and return a new calculator result.

To solve this puzzle, the key insight is to realize that we can

  1. Abstract away the value and the stack from the operations that take these values as arguments.

  2. Create a combinator, which takes two arguments: first, and secondFunction. The combinator

    1. Runs the first operation to produce a calculator result, when given an initial stack.
    2. Feeds the value and stack from the first operation to secondFunction

In other words, the combinator does all the work of feeding the results from one operation to the next.

Your task: To understand the combinators, do the following:

  1. Open the file Combinators.hs and examine how we have implemented these ideas in code. The most important piece is a combinator called followedBy.

  2. Now, open the file Program2.hs and compare it to Program1.hs.

  1. In Program2.hs, implement a new operation called tnpo that triples the value on the top of the stack, adds 1 to the result, then pushes the entire result back on the stack. Update program so that the last operation it performs is tnpo. Challenge yourself to implement tnpo using only existing calculator operations (not Haskell arithmetic operations).

Monadic calculators

The followedBy combinator is actually the monadic “bind” (also known as “and then”) operator >>=, specialized to our calculator.

Open the file MonadicCalculator.hs to see how we can define a calculator step as a monad. There’s nothing extremely new here. We just take most of our previous calculator code and making it monadic, by describing how to use the followedBy implementation to define a calculator Monad.

Look over the file and compare it to the previous definition in Calculator.hs. Here are a few things to note:

  • We define a new type CalcStep. This type will be an instance of the Monad typeclass. Haskell requires any type that is a Monad to take a single type parameter, so CalcStep takes a single type parameter. In practice, we will often parameterize it with Value, but notice a parameterized CalcStep allows us to define monadic Calculators for all kinds of things, such as Strings, Bools, Cows, etc.

  • The code that makes CalcStep an instance of Monad is similar to the code in Combinators.hs, specifically functions makeResult and followedBy.

  • For CalcStep to be a Monad, Haskell requires that it also be a Functor and an Applicative, so you will see those definitions, too. You can largely ignore them for now, if you want.

  • Most of the rest of the code looks a lot like the original code. One nice feature about our monadic calculators is that we get to us do notation. Compare the monadic binaryOperation to the original definition!

Open the file Program3.hs and compare it to the original Program1.hs. Isn’t the function called program much more readable, now that we have monads?

If you have time, transfer your tnpo code from Program2.hs to Program3.hs.