This article pre-supposes that you have some basic knowledge of Haskell, Rack/PEP 333, and middleware.

Middleware

Middleware, as a plugin architecture for creating custom web stacks, is an amazing tool (the fact that it makes web servers interchangeable is equally important but not useful for this discussion). By simplifying and standardizing the interface used by middleware to communicate, web developers have been given an easy way to compose and reuse nicely sized chunks of functionality. Interestingly the pattern itself is general enough that it applies just as well to pluggable architectures outside of the web stack as evidenced by recent additions of similar functionality to Vagrant. In fact if you stand back a bit further, just far enough to look past object oriented underpinnings, it starts to look a lot like function composition which many consider to be the pinacle in abstractions for software reuse.

composition

To illustrate the similarities with function composition lets define a simple Rack app with some middleware borrowed from an introductory tutorial on Rack middleware.

# A sample rack app
app = Rack::Builder.new do
  use Rack::Upcase
  use Rack::Reverse

  run lambda { |env| [200, { 'Content-Type' => 'text/html' }, 'Hello World'] }
end

The middleware used here modify the response in the manner you would expect. As long as they both forward the request environment down the stack they are afforded the opportunity to manipulate the response provided, first, by the endpoint and then by any subsequent middleware. Now something similar, though simpler, in Haskell:

import Data.Char
import Prelude hiding (reverse)
import qualified Data.List as List

type Response = (Int, [(String, String)], String)

run = reverse . upcase . \env -> (200, [("Content-Type", "text/html")], "Hello World!")

reverse :: Response -> Response
reverse (s, h, body) = (s, h, (List.reverse body))

upcase :: Response -> Response
upcase (s, h, body) = (s, h, (List.map toUpper body))

-- *Main> run ()
-- (200,[("Content-Type","text/html")],"!DLROW OLLEH")
-- *Main>

There obviously isn’t any environment forwarding performed here, but the response manipulation is virtually the same. Both the Rack middleware and the composed functions form a pipeline of functionality bound by the common expectation of an HTTP response type in the form of a triple. As long as whatever you’re building is able to manipulate that triple it can be used at any stage in the pipeline or in any other pipeline with the same expectation. But this basic composition, a wonderful tool though it is for creating reusable and generic software, still leaves some issues unresolved.

Errors

When building your own Rack middleware there are a couple of ways you can go about handling errors or problematic states. First, you can simply return an error response, thereby alerting the outside world to problems immediately. Alternatively you can attach error information to the environment and allow subsequent middlwares to decide what they would like to do and then possibly modify the response when one is returned. Both options leave something to be desired because there are no guarantees or contracts around error handling. To illustrate lets address the first scenario, see how it maps to function composition and then attempt to improve it.

To do this we’ll add another bit of middleware into our stack, one that has a condition under which it cannot operate and must report a failure. We’ll call it Rack::Head, and it will attempt to trim the response body down to its first character.

module Rack
  class Head
    def initialize app
      @app = app
    end

    def call env
      status, headers, body = @app.call env

      if body.empty?
        [500, headers, "Head cannot operate on an empty string"]
      else
        [status, headers, [body.first]]
      end
    end
  end
end

Now, if the endpoint’s response body is changed to be an empty string this new middleware will have to report its failure to those above it in the stack.

app = Rack::Builder.new do
  use Rack::Upcase
  use Rack::Reverse
  use Rack::Head

  run lambda { |env| [200, { 'Content-Type' => 'text/html' }, ''] }
end

Unfortunately there is no guarantee the middleware above Rack::Head won’t just replace, alter, or in this case reverse the response body making the error response hard to read or non-existent. This, I believe, is an intentionaly flexible design choice leaving what to do with errors in the hands of middleware authors. Looking back to Haskell we get a similarly unfortunate result with pure function composition:

run = reverse . upcase . head . \env -> (200, [("Content-Type", "text/html")], "")

head :: Response -> Response
head (s, h, "") = (s, h, "Head cannot operate on an empty string")
head (s, h, body) = (s, h, [List.head body])

-- *Main> run ()
-- (200,[("Content-Type","text/html")],"GNIRTS YTPME NA NO ETAREPO TONNAC DAEH")
-- *Main>

Here the application accounts for the fact that head is unable to operate on an empty list, an error message replaces the response body, and is subsequently mangled. The application could let head throw its empty list exception, though thats less than optimal as well. It appears that simple composition has reached the limits of its usefulness in error handling and some other tactic is required.

Maybe

While Rack, in its current form, doesn’t have any alternatives to offer when it comes to error handling, Haskell has some interesting tools that might provide some insight. The first, and most oft cited, is the Maybe monad. When used in conjunction with the monad instance of Maybe, functions can continue to use composition, if in a slightly altered form, without much additional overhead for the developer while the pipeline is imbued with the ability to “short circuit” when something untoward occurs¹.

import Control.Monad

run = reverse <=< upcase <=< head <=< \env -> Just (200, [("Content-Type", "text/html")], "")

reverse :: Response -> Maybe Response
reverse (s, h, body) = Just (s, h, (List.reverse body))

upcase :: Response -> Maybe Response
upcase (s, h, body) = Just (s, h, (List.map toUpper body))

head :: Response -> Maybe Response
head (s, h, "") = Nothing -- (s, h, "Head cannot operate on an empty string")
head (s, h, body) = Just (s, h, [List.head body])

-- *Main> run ()
-- Nothing
-- *Main> 

There are 3 changes to the original. First, an import of Control.Monad makes the Maybe Monad instance available. Second, the dot composition operator has been replaced with the monad composition operator (<=<). Third, the type of (<=<) is

(<=<) :: (Monad m) => (b -> m c) -> (a -> m b) -> a -> m c

so we are required to wrap our Response with one of the two Maybe value constructors (Maybe is the m in the type signature). If this seems convoluted, just remember that the type of the regular composition operator (.) is

(.) :: (b -> c) -> (a -> b) -> a -> c

and the only real difference is that we’re required to wrap the result in the Maybe monad.

The last is the key to how the head function can prevent the other middleware from altering its error response. The monadic composition operator (<=<) is built on the monadic bind operator, (>>=) which is defined in the Monad instance for Maybe:

instance Monad Maybe where
    return         = Just
    fail           = Nothing
    Nothing  >>= f = Nothing
    (Just x) >>= f = f x

The key is that when Nothing is passed as the first argument to (>>=) the result will always be Nothing. Consequently we can say the same about (<=<) as the only extra work that it does on top of the bind operator is some type unwrapping. So! by making sure to wrap the return result in the Maybe monad with the Just data constructor, or Nothing data constructor if there is a failure, the plumbing for managing errors (ie “short circuiting” ) is handled in the (<=<) operator.

run = reverse <=< upcase <=< head <=< \env -> Just (200, [("Content-Type", "text/html")], "")

-- *Main> run ()
-- Nothing
-- *Main>

run2 = reverse <=< upcase <=< head <=< \env -> Just (200, [("Content-Type", "text/html")], "Hello World!")

-- *Main> run2 ()
-- Just (200,[("Content-Type","text/html")],"H")
-- *Main>

Great! We’ve established a way to prevent the other middleware from futzing with the error, but lets make one small change so that our pipeline can report something more useful than Nothing while continuing to short circuit.

import Control.Monad.Error

reverse :: Response -> Either String Response
reverse (s, h, body) = Right (s, h, (List.reverse body))

upcase :: Response -> Either String Response
upcase (s, h, body) = Right (s, h, (List.map toUpper body))

head :: Response -> Either String Response
head (s, h, "") =  Left "Head cannot operate on an empty string"
head (s, h, body) = Right (s, h, [List.head body])

run = reverse <=< upcase <=< head <=< \env -> Right (200, [("Content-Type", "text/html")], "")

-- *Main> run ()
-- Left "Head cannot operate on an empty string"
-- *Main>

run2 = reverse <=< upcase <=< head <=< \env -> Right (200, [("Content-Type", "text/html")], "Hello World!")

-- *Main> run2 ()
-- Right (200,[("Content-Type","text/html")],"H")
-- *Main>

The only thing thats changed here is that Either has replaced Maybe as our Monad of choice. It should come as no surprise that its defined in Control.Monad.Error, and it has two data constructors just like Maybe; Left for signaling failure and Right for signaling success. As a result we can include a message for the operator of the function to give them some helpful debugging information without worrying about another function farther up the line meddling!

Closing

Next time I’d like to take the concepts we’ve applied here to our Haskell “middleware” and show how abstracting the error handling in a Builder class like Rack’s can provide benefits for use in something like Vagrant. Most of all I hope that this might provide some clarity around why function composition, and by extension middleware, is a really nice patterns for creating modular software.

Notes

1. Functions composed in the Maybe monad, as in the example, don’t actually short circuit. They have to run through each composition but as you can see from the Maybe Monad instance they don’t execute the function itself.

2. Replacing our Response whole sale with a Left String is really only useful for illustration in this case. It would be better to at least use Either Response Response, and provide an errorResponse function that takes a string and sets the status and headers properly.

Motivation

I’ve been using Monk with the armonk skeleton for the last couple of weeks to build a little app that monitors Craig’s List searches. Bebop aside, I’ve found it to be a really refreshing experience, but I knew when I started building the app that the vanilla routing DSL wasn’t going to meet my needs (it wasn’t built too!). I also knew I would end up missing the path helpers, targeted filters, resource nesting, and printable routing information from Rails. So! after mocking up a simple DSL and consulting some friends I built and tested this little Sinatra routing extension and dubbed it Bebop in honor of Thelonius Monk.

Examples

Once registered Bebop provides the resource class method on Sinatra::Base as the starting point for building your routes.

require 'sinatra'
require 'bebop'

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    # GET /foos/hello
    foos.get '/hello' do
      'hello world'
    end

    # GET '/foos/goodbye'
    foos.get '/goodbye' do
      'goodbye'
    end
  end
end

Routing Helpers

As illustrated, Bebop can be used for nothing more than prefixing the routes generated by the normal dsl methods with a resource name (‘/foos’ in this case). It also provides route helper methods that build RESTful routes for the actions index, new, create, show, edit, update, and destroy.

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    # Get /foos
    foos.index {}

    # GET /foos/:foo_id
    foos.show {}

    # GET /foos/new
    foos.new {}

    # POST /foos
    foos.create {}

    # PUT /foos/:foo_id
    foos.update {}

    # GET /foos/:foo_id/edit
    foos.edit {}

    # DELETE /foos/:foo_id
    foos.destroy {}
  end
end

And if you want to nest your resources bebop handles prepending the routes correctly:

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    foos.resource :bars do |bars|

      # Get /foos/:foos_id/bars
      foos.index {}

      # GET /foos/:foo_id/bars/:bar_id
      foos.show {}
    end
  end
end

Extras

Bebop also extends some of the basic Sinatra functionality like before and after filters and provides new functionality in the form of path helper methods. Filters can target specific routes based on identifier, all routes, or nested resource routes. The only stipulation is that the filters must be defined _before_ the filtered route in the body of the resource block.

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    # To run a filter before all routes
    #
    foos.before :all do
      @all = 'all'
    end

    # To have your filter run before a specific route, the route must be one of the seven helper
    # routes (see example/routes.rb) or specify the :identifier parameter
    #
    foos.before :new do
      @new = 'new'
    end

    foos.new do
      "#{@all} #{@new}" # => 'all new'
    end

    # You can target the vanila methods by providing the :identifier hash option
    #
    # GET /foos/baz
    foos.get '/baz', :identifier => :new do
      @new # => 'new'
    end

    # You can also specify a before filter for nested routes by using the child resource name
    # 
    foos.before :bars do
      @bars = 'some bars'
    end

    foos.resource :bars do |bars|
      bars.get '/some_bars' do
        @bars # => 'some bars'
      end
    end

    foos.get '/bak' do
      @bars # => nil
    end

    # Finally you can specify many different methods in your filters by passing many identifiers
    # 
    foos.before :bak, :baz do
      @bak_baz = "bak 'n' baz"
    end

    foos.get('/something', :identifier => :bak) { @bak_baz }
    foos.get('/anything', :identifier => :baz) { @bak_baz }
  end
end

Path helpers follow a simple naming convention that starts with the original parent resource, all the child resources ordered by nesting, and finishing with the action identifier.

class MyApp < Sinatra::Base
  register Bebop

  resource :foos do |foos|

    foos.resource :bars do |bars|

      # GET /foos/:foo_id/bars/:bar_id/edit
      bars.edit do
        "foo: #{params[:foo_id]} bar: #{params[:bar_id]}"
      end 

      bars.get '/redirect' do

        # Redirects to /foos/1/bars/2/edit
        redirect foos_bars_edit_path(1, 2)
      end
    end
  end
end

Code

Most of the above examples are borrowed from the examples directory in the gem if you are interested. The repo can be found at github, and you can install the gem right now as long as gemcutter.org is one of your sources. As suggested by Damian Janowski I’ll be adding some template helpers and some other goodies soon.

As always feedback and suggestions are welcome!

A friend of mine recently covered deterministic and non-deterministic finite state machines (automata for the cool kids) in one of his classes and passed along a sample problem for me to figure out. Informally, build a dfa that will match a given string against another string in the provided alphabet. An example of this class of problem would be to build one that matches ‘aab’ in any string for the alphabet [ab] (‘aaba’ would match, ‘aba’ would not).

To help with visualizing the answer for this example I’ve built a graph of the states and edges that make up our dfa (yay graphviz):

At each state the machine follows the edge that matches the next input from a given string. If it ever hits the fourth state, it’s found a match. Checking the string “baab” for “aab” (for which our machine is built), starting at state one it would take the path 1 -b-> 1 -a-> 2 -a-> 3 -b-> 4, and conclude that “aab” was in fact contained within “baab”.

After doing this on paper I thought it might be fun to use haskell and put together a function that took a dfa, a string to match, and produced a boolean result. The first step I took was to define a data type that represented the dfa.

type Dfa = [State]
data State =  State { identifier :: Int , edges :: [Edge] }
           | FinalState { identifier :: Int, edges :: [Edge] }
data Edge = Edge { action :: (Char -> Bool), edge_identifier :: Int }

This is an informal representation (you can find the formal one here) but here, a dfa is a set of States, a State is an identifier and a set of Edges, and an Edge is a function to determine if it is the edge to follow for a given input and its target state. If this looks a bit clunky at first a cleaned up version is further down.

With my types in place I went ahead with building the functions to traverse a DFA for a given input:

match :: State -> Dfa -> String -> Bool
match current_state _ [] = is_final current_state
match current_state dfa (x:xs) = match next_state dfa xs
                           where next_state = traverse dfa current_state x

traverse :: Dfa -> State -> Char -> State
traverse dfa state = (find_state dfa) . (next_id $ edges state)

is_final (FinalState x y) = True
is_final (State x y) = False

find_state :: Dfa -> Int -> State
find_state (st:sts) state_id  | identifier st == state_id = st
                              | otherwise = find_state sts state_id

next_id :: [Edge] -> Char -> Int
next_id (e:es) input | (action e) input = edge_identifier e
                     | otherwise = next_id es input

The short explanation is that for each input it checks the current state for where it should go next, having determined the destination state’s id it finds that state in the dfa and then proceeds with the rest of the input.

Now, to test a sample graph:

state1 = State 1 [ Edge is_a 2, Edge is_b 1]
state2 = State 2 [ Edge is_a 3, Edge is_b 1]
state3 = State 3 [ Edge is_a 3, Edge is_b 4]
state4 = FinalState 4 [ Edge is_a 4, Edge is_b 4]

graph = [state1, state2, state3, state4]

is_a = (== 'a') 

is_b = (== 'b') 

You’ll note that state4 refers to itself no matter the input so that the match function can operate exhaustively on the input string.

And it works! But the best part of this whole exercise (for me at least) was yet to be realized because this whole first definition has been done in a very inelegant manner by failing to make use of haskell’s lazy nature and recursive data types.

Improved

The first, and easiest, thing to improve is how the Edges reference their destination states. Before, an integer was defined corresponding the identifier of the target state, but in haskell types can be defined recursively:

type Dfa = [State]
data State =  State { edges :: [Edge] }
           | FinalState
data Edge = Edge { condition :: (Char -> Bool), destination :: State }

For reference:

type Dfa = [State]
data State =  State { identifier :: Int , edges :: [Edge] }
           | FinalState { identifier :: Int, edges :: [Edge] }
data Edge = Edge { action :: (Char -> Bool), edge_identifier :: Int }

Not only is the new definition much cleaner, but its also more intuitive. An edge simply hands off the _actual_ state its pointing at. No need to go find it. As a result the code necessary to operate the state machine is also significantly simplified:

match :: State -> String -> Bool
match FinalState _ = True
match (State _) [] = False
match current_state (x:xs) = match next_state xs
    where next_state = traverse (edges current_state) x

traverse :: [Edge] -> Char -> State
traverse (e:es) input | (condition e) input = destination e
                      | otherwise = traverse es input

Notice the type signature of traverse is very intuitive:

traverse :: [Edge] -> Char -> State 

Given a list of edges and an input it will give you the resulting state. Not the id, which would then be used to search for its corresponding state. Finally, the actual graph:

state1 = State [ Edge is_a state2, Edge is_b state1]
state2 = State [ Edge is_a state3, Edge is_b state1]
state3 = State [ Edge is_a state3, Edge is_b state4]
state4 = FinalState 

is_a = (== 'a') 

is_b = (== 'b')

Simplified

By leveraging the recursive reference to another state in the destination field of the Edge type the code shrinks by 3 functions and an enormous amount of complexity. In addition the ability to exhaust the input string or return early on a match with the FinalState constructor allows for a much more readable definition of the match function and the graph itself (no more self referencing weirdness).

I had a lot of fun thinking this through and I would be excited to see some further refinements in the comments from those who know haskell!

I think technically this counts as an application of my readings from Algebra of Programming. Satisfied.

class Cons
  include Enumerable
  attr_accessor :child, :value

  def self.[](value, child=:empty)
    new(value, child)
  end

  def initialize(value, child)
    @value, @child = value, child
  end

  def each
    x = self
    while( x != :empty)
      yield x
      x = x.child
    end
  end
end

x = Cons['MWA', Cons['HAHA', Cons['HAHA']]]
puts x.inject(''){ |acc, x| acc+=x.value  }

As a side note, I hope that someone finds this page looking for a list of negative things about ruby. Maybe if you run the code you’ll find something >:]

[Update: Nick Quaranto was kind enough to respond to my twitter message, and the issue has been resolved. Many thanks Nick!]

So I went to publish RQuery to gem cutter but I got this lovely tidbit:

Pushing gem to Gemcutter...
You do not have permission to push to this gem.

I figured someone had clearly come up with a similar name and applied it to their gem so I went and searched and found:

http://gemcutter.org/gems/rquery

Needless to say I was a little bit bummed, but I thought it odd that its was just a dot one version higher than my last release, and then I noticed that the homepage link points back to none other than my page about the darn gem!

What that hell man, gimme my gem name back!

Inverses are (horrible)^-1

This section gives an introduction to the extremely interesting concept of implementing a function as the inverse of another with zip and unzip as the examples. First, the goal is to build out our zip and unzip functions to satisfy the equation

zip . unzip = id

A couple of notes here. Previously everything has been defined in terms of Haskell, but this is simply an equation. Also, if you’re coming from a non-functional background, id is a function that gives you back the same thing you pass to it. No matter what.

In this case the equation is meant to point out that, if you give unzip a list of pairs (two element tuples) and give that result, a tuple of two lists, to zip, in the end you’ll get back the original list of pairs. So zip compose unzip is equivalent to the id function. You get back just what you gave it.

zip $ unzip [(1,2), (3,4)] = [(1,2), (3,4)]

Before we get into why this is immediately useful lets define the two functions as the book does, but with Haskell.

data Listr a = Empty | Cons (a, Listr a) deriving Show 

foldr' c h Empty = c
foldr' c h (Cons (a, x)) = h a $ foldr' c h x

Our old friends the Cons list and foldr here. If you’re new to these you can check out more information on them here.

unzip' :: Listr (a, b) -> (Listr a, Listr b)
unzip' = foldr' emptys conss
        where emptys = (Empty, Empty)
              conss (a, b) (x, y) = (Cons (a, x) , Cons (b, y))

unzip_' :: Listr (a, b) -> (Listr a, Listr b)
unzip_' Empty = (Empty, Empty)
unzip_' (Cons ((a,b), x)) = (Cons (a, left $ unzip_' x), Cons (b, right $ unzip_' x))
                           where left (x, y) = x
                                 right (x, y) = y

unzip’ and unzip_’ represent two possible ways of unzipping a list of pairs. Of interest here is the fact that my own, much less efficient, implementation involves two “folds” over the data structure, and the one implemented in the book only requires one. Apparently, any and all functions defined by a pair of folds can be defined in terms of a single fold (to be demonstrated later in the book).

zip' :: (Listr a, Listr b) -> Listr (a, b)
zip' (Empty, _) = Empty
zip' (_, Empty) = Empty
zip' (Cons (a, x), Cons (b, y)) = Cons ( (a, b) , zip' (x, y) )

-- > let x = zip' . unzip'
-- > x  $ Cons ((1, 'a'), Cons ((2, 'b'), Empty))

-- Cons ((1,'a'),Cons ((2,'b'),Empty))

-- > let y = zip' . unzip_'
-- > y  $ Cons ((1, 'a'), Cons ((2, 'b'), Empty))

-- Cons ((1,'a'),Cons ((2,'b'),Empty))

Finally we have an exhaustive (can handle lists of different lengths) definition of zip’ and the results of composing zip’ with unzip’ and unzip_’ using ghci.

Testing with maths

If you know how zip and unzip work its not imperative (though it is fun) to walk yourself through how each of them operates as defined here. What is important is the result we’ve gotten out of ghci. We’ve composed our two functions, and as stated above in our original equation we’ve gotten back the very same thing we put in. Just as though it were the id function.

I had originally wanted to build my own “foldrless” version of unzip_ in the hopes that it would be easier to see the “inversity” in the code itself. Unfortunately its not incredibly clear, and whats worse the implementation isn’t extremely efficient. BUT! Its not a total loss, because in order to satisfy myself that my hack was working properly, all I had to do was run the results BACK through zip and see if I got the original Cons list out the other side to satisfy our original assertion.

And that’s really the sweet spot here. While its not a formal proof of the functionality, it provides us with a lot of confidence that our functions are working properly. By defining the function as the inverse of another function we get a way to build it and test it. Incredible.

Lists

The third section of chapter one covered some basic functional programming concepts. Namely Cons lists, their mirror Snoc lists, and the functions built to operate on them. Particularly the adaptations of the foldn function from the previous section which operated over Nat.

data Listl a = Nil | Snoc (Listl a, a) deriving Show
data Listr a = Empty | Cons (a, Listr a) deriving Show 

foldl' c h Nil = c
foldl' c h (Snoc (x, a)) = h (foldl' c h x) a

foldr' c h Empty = c
foldr' c h (Cons (a, x)) = h a $ foldr' c h x

As you can see in the definition of both Cons and Snoc they are identical to the previous sections definition of natural numbers save for an addition bit of information, whatever you are storing in your list. Also, Cons and Snoc are only different in the position of their recursive self reference. It’s only the general understanding of the position by those using the type and the functions created for them ( : as an example ) that makes it behave the way it does. If you were, without prior knowledge, to examine the types by themselves it wouldn’t be clear that they were operated upon in significantly different ways when adding new elements (other than the difference in the names of the data constructor). As an example we could redefine the haskell infix cons operator to work with Snoc lists just as it would a Cons list (Note: I’ve been informed that in practice this isn’t possible, but the purpose of the example still holds).

data Listl a = Nil | Snoc (Listl a, a) deriving Show

(:) :: a -> Listl a -> Listl a
x : y = Snoc (y, x) 

example = 1 : Snoc(Snoc(Nil, 3), 2)
          --  Cons(2, Cons(1, Nil)) would be the norm

Also of interest in this chapter is the myriad of operations that can be defined in terms of foldr for Cons lists and foldl for Snoc lists, much as with Nat. From two of the excercises:

--Excercise 1.7
convert :: Listl a -> Listr a
convert = foldl' Empty h
    where h x y = Cons(y, x)

--Excercise 1.8
catconv :: Listl a -> Listr a -> Listr a
catconv m n = foldl' n h m
    where h x y = Cons(y, x)

Or a quick implementation of map’ for Cons lists built atop our extremely reusable foldr’

map' f = foldr' Empty h
    where h x y = Cons (f x, y)

-- > map' (+2) $ Cons (1, Cons(2, Empty))
-- Cons (3,Cons (4,Empty))

Further Work

I’m getting a lot of joy from rehashing these basic data structures and the implications of understanding them at a relatively low level are obvious. Lists make up such a huge portion of the programming that we do and understanding the types of lists that make the most sense for use within code for both comprehension and performance can provide real value. Also, in fooling around with some little coding challenges on the side (examples to be posted soon I hope) in haskell I’ve noticed my ease with maps and folds becoming greater.

One bit that I have to revisit is the proof from the middle of the section that the ++ operation is associative and that nil is the left and right unit. I was never very good with proofs, I’ve long since lost the terminology, and I would like to complete the exercise that requires that knowledge.