matchingSub is Comonadic (obviously!)

So!

Today’s 1HaskellADay problem was an interesting NP-hard problem ... until I reread the problem statement carefully, then it became trivial. ‘Consecutive’ is the keyword here that unlocked the puzzle for me, eventually.

The heart of the algorithm here is simple enough. It says, in words, ‘are these next n numbers in the list the sum specified?’ If they are, return them as a solution, if they are greater, return nothing, if they are less than the sum, keep trying.

Those are the words, here is the implementation:

inquiry :: Int -> Int -> DList Int -> [Int] -> [Int]

inquiry _ _ _ [] = []

inquiry goal sub accum (next : rest) =

   let tote = sub + next

       naccum = accum << next

   in  case (compare tote goal) of

          LT -> inquiry goal tote naccum rest

          EQ -> dlToList naccum

          GT -> []

Simple enough, and I use a difference list as an accumulator, just because that’s how I roll (and the fact, too, that difference lists append an element in constant time is sweet!)

So, now all we need to do is move an index over the list to test each possible scenario.

Enter the (Comonad) Dragon

Of course, iterating over a list, keeping the context of the list itself active can be done functionally in many ways, but what suggested itself to me right away was the Comonad.

The Comonad of the list is the list itself and all of its tails, and this is exactly the paradigm we need to solve this problem simply, so, writing matchingSub became simply a comonadic extension:

matchingSub’ :: Int -> [Int] -> [[Int]]

matchingSub’ goal domain =

   domain =>> inquiry goal 0 emptyDL

Now, this doesn’t quite give the requested solution sets for the given examples, as it returns the empty list as ‘no solution,’ not ‘nothing at all’ as requested, but filtering out the empty list is easy enough: we just need a predicate to test if the list is not empty and then return only the lists of answers:

isCons :: [a] -> Bool

isCons [] = False

isCons _ = True

matchingSub :: Int -> [Int] -> [[Int]]

matchingSub goal = filter isCons . matchingSub’ goal

And there we have it!

I like comonads. They’re sweet!

Okay, prove it, buster!

(Who is this 'buster'-person, by the way, and why is he always having to prove things?)

All the above code is in Haskell programming, but it is also mutually-translatable to and from Idris. Nearly the same syntax (intentionally so), and nearly the same semantics (Idris's eager evalution looks and tastes very much like Haskell's normal order evaluation).

In Haskell, we'd hand-verify the above with the provided samples and we're done. We'd run it through quickcheck to be done-done.

In Idris, we can prove that what we specified is actually (heh: 'actually') correct in its implementation.

So, let's prove it.

prvSample : (expected : List (List Int)) 

            -> (actual : List (List Int))

            -> (so (expected == actual)) -> ()

prvSample expected actual pred = ()

Using the 'so' assertion, we're (almost) done.

Let's run our sample-set through our prover, such that it is:

sample1 : ()

sample1 = (prvSample [[1..4]]

                     (matchingSub 10 [1..5])) oh

sample2 : ()

sample2 = (prvSample [[1,1], [1,1]] 

                     (matchingSub 2 $ replicate 3 1)) oh

sample3 : ()

sample3 = (prvSample [[1,1], [1,1]]

                     (take 2 $ matchingSub 2 $ repeat 1)) oh

Code compiles? Yes? We're done: we've delivered functionality as specified.

Sweet!

keepEquals with Difference Lists

Yesterday's 1HaskellADay exercise was keepEqual but it could have easily have been ‘keepSimple’ or ‘write this in your sleep’ or ... something like that.

It was a good exercise, because there’s the obvious solution but then you look to improve the efficiencies.

And then, of course, there’re the wrong solutions, but that’s what we have proofs for, to prove ourselves into the correct implementations.

So the first stab I did was wrong:

keepEqual1 : Eq a => List a -> List a -> List a

keepEqual1 list1 list2 = list1 >>= \h1 =>

                         list2 >>= \h2 =>

                         (if h1 == h2 then return h1 else [])

The problem here is that this algorithm, albeit cleverish is, well: wrong.

It iterates through each element of list1, fine, but it compares the currently-selected element of that list to every element of list2.  There’s also a tiny problem in that if either list1 or list2 are infinite, see, as the binding operation goes through each element of the list (inner, then outer) before returning, which could be a problem if you ever want a return in this eternity.

Minor problem there.

The other problem is that this is an exponential algorithm: for each element of list1, it possibly iterates through the entire set of list2 to find a match.

Ouch.

So. Cleverish approach was a fail on my part. Shall we try the traditional approach?

keepEqual2 : Eq a => List a -> List a -> List a

keepEqual2 [] _ = []

keepEqual2 _ [] = []

keepEqual2 (h1 :: t1) (h2 :: t2) =

   (if h1 == h2 then [h1] else []) ++ (keepEqual2 t1 t2)

So, that’s traditional. That works (and we can choose to verify that it does work), and it terminates at the end of the first list, thereby neatly dodging the non-termination-with-infinite-list-arguments issue.

The problem here is that we are representing choice with a list-compressionescque algorithm here, so we continuously concatenate to the end of a single-element list, or, in the case of a non-match, the empty list.

That algorithm, concatenation-no-matter-what, just screams: “Improve me! Improve me, please!”

So, okay, one improvement is we can turn our choice-point from the above to construction or return:

   (if h1 == h2

    then (h1 :: (keepEqual2 t1 t2))

    else keepEqual2 t1 t2)

Okay, is that yummy-looking?

No. No, it is not.

I mean, for efficiency’s sake we are eliminating the whole ‘concatenate after the empty list’ operation for the not-equals case, and keepEqual2 is being called only once in this branch, but ...

But it’s still written twice, and that’s ugly. Why do we have to express something twice for the concept of ‘okay, add the head only if it’s the same and then continue on with the rest of the two lists.’ I mentioned the continuation (ooh! continuations!) just once here in my denotation, why do I have to mention it twice in my implementation?

Well, I don’t have to, actually. We’re working in a functional domain, so let’s get functional!

   (if h1 == h2 then ((::) h1) else id) (keepEqual2 t1 t2)

Boom! ... actually, not so ‘boom’ because of the overridded values of (::) confuses Idris (Vect, Stream, and List all use (::) as a constructor), so let’s clarify that:

cons : a -> List a -> List a

cons a list = a :: list

So, now we can write:

   (if h1 == h2 then (cons h1) else id) (keepEqual2 t1 t2)

I actually had this little partial function revelation just now, so my actual implementation involved me creating the difference list data type, which allowed constant time prepend and append operations. Which is better? Partial functions or the difference list?

Well, let’s take a look at my difference list implementation so we can judge their respective merits.

data DList a = DL (List a -> List a)

A difference list is the difference between two lists, and we represent this difference by capturing it in a function

unDL : DList a -> (List a -> List a)

And we can, of course, extract our function from the difference list type.

(<<) : DList a -> a -> DList a

list << a = DL ((unDL list) . (cons a))

Our append operator (<<) appends an element to the tail end of a DList in constant time (if it were needed, the corresponding (>>) operator prepends an element to the head of a DList, also in constant time).

So, we have our DList structure, but we need to start from something, and then, eventually convert back to a plain-old List structure. The below functions provide those functionalities for us:

emptyDL : DList a

emptyDL = DL id

dlToList : DList a -> List a

dlToList dlist = with List (unDL dlist [])

Now, with the difference list type, we rewrite our keepEqual in the natural style.

keepEqual : Eq a => List a -> List a -> List a

keepEqual’ : Eq a => DList a -> List a -> List a -> List a

keepEqual = keepEqual’ emptyDL

keepEqual’ dl [] _ = dlToList dl

keepEqual’ dl _ [] = dlToList dl

keepEqual’ dl (h1 :: t1) (h2 :: t2) =

   keepEqual’ (if (h1 == h2) then dl << h1 else dl) t1 t2

So, what do you think? For this example the DList doesn’t really shine all that much, but if we had something where appending to the end (in constant time) made a whole lot of sense, then we would have a clear win for it.

I like DList.

Abstract Nonsense, chapter 1: the List

Abstract Nonsense: Rambling thoughts of a Category Theorist

Synopsis: Looking at things through the lens of category theory, where 'things' may be anything from writing a good (a really, awesomely good) piece of code to ... well, what else is there in this life?

Chapter 1: the List

We consider the list: to monad or not to monad.

We consider the monad: to monad or to comonad, and, if we consider the monad, shall we consider the monoidal implications that monad lends itself it to?

A monad is not intrinsically monoidal, but, then again, the monad and the comonad are not intrinsically functors, but thinking of monads and comonads and thinking of them not as functors is a blocker for me ... it gives me a bit of a headache, thinking of a monad (the triple (T, mu (or 'join'), eta (or 'unit')). I mean, it is simple to think of monads as monads only when considering the join function, but what is the point of eta if you are not thinking of the monad in terms of a functor?

So I do not consider the monad, or the comonad (W, epsilon (or extract), delta (or duplicate)) (definition from "Introduction to Higher-Order Categorical Logic), http://books.google.com/books?isbn=0521356539, as being independently or intrinsically defined from the functor, Fa, as, after all unit and extract are functorable.

Okay. So we consider lists. We can consider lists free of the monadic and comonadic implications, because, after all, a list is simply a structure, and can be viewed as tree-like structure, where we define 

data list a = nil | (a, list a) 

we see that, firstly list is monoidal on a where mzero = nil and mappend is easily defined as append or (++).

So, anywhere along the list, one can grab the pair, and the tree falls out of the structure:

(a, |->) -> (b, |->) -> nil

The pairwise operators, fst and snd, are head and tail on list a, and the fundamental constructor of the list is cons, where cons :: a -> list a -> list a

(which looks like a continuation, now that I look at it, OMG!)

(The continuation monad is the 'mother of all monads', and the continuation is the 'mother of all function calls,' perhaps?)

from cons, mappend is simply defined:

nil ++ b = b

  a ++ b = cons (head a) (tail a ++ b)

             

Since list a is functor a (leaving aside nil) we have fmap for lists, too:

fmap f nil = nil

fmap f (head:tail) = cons (f head) (fmap f tail)

as you can see, list definitions lend themselves naturally to induction.

Okay. Lists qua lists (of course, as monoids and functors) are very easily defined in just a few lines of code in any programming language with any heft (I've demonstrated Haskell here, the definitions are similar in Java once monoid and functor are properly established as types. This requires that Arrows and functors be defined, but that is not part of the scope of this article ... it's hard, but doable).

Monadic Lists

Now let's consider the case of lists as monads.

First, monad:

class Monad m where

    return :: a -> m a

    join :: m (m a) -> m a

That definition is unusual in the programming community, but not to a categorist. Programmers are used to the more applicative definition of monad:

class MonadForProgrammersButNotForMeTheCategorist m where

    return :: a -> m a

    m >>= f :: m a -> (a -> m b) -> m b

The issue with defining monads in terms of bind (>>=) is that sometimes wrapping your head around what bind should be for a particular monad can be tricky (sometimes it isn't, but sometimes it is), but if one knows what join is for a monad, and, if that monad is a functor, then we have a very simple, and a very general, definition of bind:

bind m f = join . fmap f

proof

bind is defined as above

bind (m a) f = (join . fmap f) (m a) = m b (supposition)

                 = (join . fmap (a -> m b)) (m a)

                 = (join . (m a -> m (m b))) (m a)

                 = (join (m (m b)) = m b

Q.E.D.

So, given that we have join and fmap defined for a monad, bind falls out easily from their composition, and that's why I declare monads as per category theory, as being the triple of the monadic type, the unit function (in Haskell, it's called 'return') and the join function.

Now, the monadic aspect of list a is simply this:

instance Monad list where

  return a = [a]

  join [] = []

  join (head:tail) = head ++ join tail (where head and tail are (monadic) lists)

... or join for list [a,b,c] is a ++ b ++ c.

And thus we have have monadic lists defined and may therefor use lists monadically, e.g.:

[1,2,3] >>= return . succ = [2,3,4]

and, even better:

[1,null, 3] >>= return . succ = [2,4]

It. Just. Works.

(side note: it really works in Haskell, as, after all, 'null' is not a number so the list [1,null, 3] does not exist in Haskell.

In Java, null very much exists, but if we make monadic list construction dependent on the monadicity of the units then the lifting function (which we will cover later) from a 'plain' list to the monadic list gets us into the a good position already:

return [1,null, 3] = [1,3] (monadic)

And if we don't do that, then the binding operation will use the Maybe type to guarantee the safety of the operation:

[1,null,3] >>= return . succ == succ (Just 1) : succ (Nothing) : succ (Just 3) = [2, 4]

end side note.)

Comonadic Lists

Now that we have monadic lists defined, let's define comonad lists.

Why? Because whereas with monads we have bind, which lends itself nicely to each element of lists, with comonads we have extend which also extends itself very nicely to operations on lists as a whole, iteratively reductively.

So, a comonad is

class Comonad w where

    extract :: w a -> a

    duplicate :: w a -> w (w a)

Again, instead of making extend intrinsic to the definition of comonads, I chose, instead, the mathematical definition, again, using duplicate.

Again, for gainful reasons, because extend can be defined in terms of duplicate:

extend :: w a -> (w a -> b) -> w b

Or: 

extend f (w a) = (fmap f . duplicate) (w a) = w b (supposition)

proof:

extend f (w a) = (fmap f . duplicate) (w a)

                     = (fmap (w a -> b) . duplicate) (w a)

                     = ((w (w a) -> w b) . duplicate) (w a)

                     = ((w (w a) -> w b) (w (w a))

                     = w b

Q.E.D.

So for lists:

instance Comonad list where

    extract [] = doesn't happen. Really

    extract (head:_) = head

    duplicate [] = []

    duplicate list@(_:tail) = list : (duplicate tail)

... and we're done.

So, if we have the basic list type defined as (a, list a) or nil

Then we convert to mlist (monadic list) or wlist (comonadic list) by defining nil for each of the particular types and then just adding elements (with cons) to each of those container types:

asMonad [] = m[]

asMonad (h:t) = h m: asMonad t

asComonad [] = w[]

asComonad (h:t) = h w: asComonad t

and in the derived times

asMonad mlist = mlist

asComonad wlist = wlist

Piece of cake.

Or.

Is.

It?

Constructing Lists: Lists as Streams.

The 'problem' of these functional list types is that they look more like Stacks than Queue, so we can interact very easily with the most recent element and cdr down through the list in an orderly fashion, but if we have a preexisting list of one type and wish to view it from a different aspect, not only do we have to build it iteratively, but we have to make sure that iterative build is not penalized (linearly) for each insert at the end of the list (which turns out to be an exponential punishment).

How do we do this?

Lists are functions in a functional aspect.

So, the problem commonly faced by users of them in the functional domain is that when one has to construct a large one iteratively, one faces the problem of continuously appending the next element to the end of the list, and since naïve append is O(N) time (linear), then doing that, iteratively incurs a near O(N*N) time cost.

(side note: the cost is actually O(N*(N-1)/2) time)

What can we do about that?

Simple, actually, if you come from a Prolog programming background, just use difference lists.

A difference list is a list representation of a pair of lists, one list representing the whole and one representing a part of the this:

data dlist a = DL { realize :: list a -> list a }

In Prolog, logic variables are used to provide the (declarative) representation (and consequently, the implementation):

List = [1,2,3|L] - L

Since we have L and L is a part of the whole list, we have a reference into a latter part of the list that in standard list representations we do not. Further, as L can be anything, it can even be the 'end' of the list, and so 'prepending' onto L allows us, by consequence (actually: 'by accident') to 'postpend' onto the list we're working with.

We saw how to represent difference lists using unification and logic variables in Prolog. How do we represent difference lists functionally?

It comes down to the fundamental function of lists, cons:

cons :: a -> list a -> list a

that is, if we give cons an element and a list we get a cons'ed list in return.

What happens if we don't give cons the list to cons to, but instead, we defer it? We then get the partial or curried function:

(cons x) :: list a -> list a

Which is no different than before.

Or.

Is.

It?

Well, recall that a difference list is the difference of two lists. Look at the signature of (cons x) above and what do we have? We have a function that, when given a list, returns a list.

What is a difference list again? A think that, when given a list, gives the full list back.

(cons x), that is: the curried cons function, and the difference list type can be viewed as the same thing, and from that we have our difference list definition (of the realize function):

realize = cons x

So, given realize, we can define prepend and postpend operations:

prepend :: a -> dlist a -> dlist a

prepend x dl = DL { cons x . realize dl }

x |> dl = prepend x dl

postpend :: a -> dlist a -> dlist a

postpend x dl = DL { realize dl . cons x }

dl <| x = postpend x dl

So what? Well, for prepend, there's no big deal, the operation occurs in constant time, but so does cons for (regular) lists. But for postpend, the operation takes the same constant time, but for regular lists, if we were to define postpend in the regular fashion:

postpend :: a -> list a -> list a

postpend a list = list ++ [a]

we would be traversing to the tail of the list each time to append the new element, and that traversal incurs a linear-time cost. Upshot: postpend for regular lists has an O(n) cost, but for difference lists, it occurs in constant time.

And that's the payoff, if you are working with a large list from an external source and need to enlistify it in an order-preserving fashion, doing so with a regular list would incur an exponential cost (nearly O(N*N)) but using difference lists has a logarithmic flattening effect (O(2N)).

Using difference lists saved my bacon on a project where I did a scan-then-process operation on a framework that processes large documents.

Back to Java.

One way to convert from one representation of lists to another is to rebuild the list in the new type. Unfortunately, Java doesn't have the linear construct

mlist [] = m[]

mlist (h:t) = h m: mlist t

So what it does is iteratively build the new list with mappend (as lists are monoidal).

Well, using the O(N) mappend in an iterative fashion incurs an exponential-time cost for list-revisualization.

So, I've replaced my fromCollection() methods in Java from:

public static <L> L fromCollection(Collection coll, L basis) {

  L ans = basis.mzero();

  for(T elt : coll) {

    ans = ans.mappend(basis.singleton(elt)); // exponential cost

  }

  return ans;

}

to be:

public static <L> L fromCollection(Collection coll, L basis) {

   DifferenceList ans = DifferenceList.nil(basis);

   for(T elt : coll) {

      ans = ans.postpend(elt); // constant time cost

   }

   return ans.realizeFrom(basis);

}

so list construction that was at a cost of exponential time now become linear time, as it should be.

This way, I can work with a list either monadically or comonadically and pay only a linear cost when I change my (aspect) perspective on the list.

'List' leads off with the letter 'Lambda' (λ)

I was revisiting the Project Euler problems recently, and one of the problems addressed lexicographic permutations.

Well, problem solved if you're using C++ or other languages that have lexicographic_permutation packaged with their standard library set. Some languages do and some don't, but that discussion is not à propos to this article, nor even what lexicographic permutations are or how to go about getting to them.¹

But something common enough did come up in the solving of that problem, which is the question of appending to the end of lists effectively.

Now, I have a prejudice: I love lists, and by that I mean to say is that in more than a few functional and logical programming languages, the List Data Structure (uttered with reverence, and with not even (barely) a hint of mocking) provides a facility for grouping and then operating on sets of objects that I find unparalleled in other programming languages and paradigms. I can, for example, in Haskell create a list simply by typing [0..9] or ["Mary", "Sue", "Bob"], and if I'm feeling old-fashioned and gutsy, I can iterate through those lists inductively with a:

doSomething [] = []
doSomething (h:t) = f h : doSomething t

Or if I wish to embrace the modern era of programming (like, oh, since the 1970ish-es),² I can use map or fold to go anywhere I want to with a list. I mean, come on! fold is, after all, the 'program transformer function.' If I don't like my list as it is now (or if I don't even like it being a list at all), I just fold over it until it's exactly how I want it to be.

Like the above function, it's really just a specialization of map, isn't it?

map _ [] = []
map f (h:t) = f h : map f t

And map is just a specialization of fold, right?

foldr ((:) . f) [] ≡ map f

So, yeah, lists rock my world.

But, you complain, I know language X [yes, the great language (flame-)war, with endless debates in the imperial senate, continues] and language X has lists and map, so what's the big deal?

The big deal is this: have you ever tried to construct a list in language X? Is it easy as the example I provided above?

No, but ...

Yeah, no, it's not as easy. In fact, I've done quite a bit of programming in language X, and I put forward that constructing and then destructuring lists is a painfully long and tedious process:

BidirectionalLinkedList list = new BidirectionalLinkedList();
list.add("Mary");
list.add("Sue");
list.add("Bob");

Blech!

BUT THEN it gets better when you do destructuring:

BidirectionalLinkedList newlist = new BidirectionalLinkedList();
for(String elem : list) { newlist.add(doit(elem)); }


Um, and that's only after the "stunning" advances that the STL started with functionals³ grafted onto the language, so have you seen the contortions you have to go through to create a functional object to map with? And don't you dare get your template parameter off because the compiler error...? shudder!

Enough of that.

So lists are structures or collections, and structures can be viewed as objects (phenomenon), and that is a very useful and powerful way to view them and to define them:

data List t = [] | (t : List t)

No problem with that and everything is right with the world.

... until it isn't.

This definitely works, and works well, for lists in general, and it also works great most of the time for working with the elements of the list. After all, in practice, we are most concerned with the element we have worked on most recently, so, in most cases, the element we just put in is the element we'd most likely to be retrieving ... AND (generally) our interest diminishes the further (in time) we are from an element, and that translates directly into where elements are found in a list.

Generally.

So, in general, lists work just fine; great, in fact.

There are specific cases where what we care about is not the most recent element, but another ordering is important. Two cases spring immediately to mind: first, queuing, and secondly (and commonly and specifically), document assembly.

In these two cases we wish to push onto the end of the list new elements, and the above definition doesn't give us access to the last element or position of the list. And to get that access, we must reverse the list so the last element becomes the first, or prepend to a reversed list. Either of these options has at least a cost in linear time when reverse is (eventually) called.

Or, we must call append or a function like it to append elements to the end of the working list; this also has linear costs. Either way, we pay the full price.

Now there are objects that do give us immediate access to that last element and position: deques and queues, for example, but when we go there, we give up the ease of composition and decomposition that we have with lists. We pay a penalty in expressitively with these types or in performance when using lists against their nature.

Or do we?

Well, one way of looking at lists is as objects, and above we gave a definition of lists as objects, but this is not the only way to view lists. I propose another way of looking at lists: lists can be viewed as functions.⁴

(:) :: t → [t] → [t]

The above definition says that (:) (pronounced 'cons') takes an element and a list and gives a list.

Yeah, so? you ask, for this is already a well-known function in the list lexicon.

I propose we look at this function in an entirely different way:

(:) :: t → ([t] → [t])

In this case, (:) constructs a list function from a seed element. This allows us to use this function a novel but perfectly acceptable way:

x |> list = (x:) . list

What we are saying here is that (|>) (pronounced 'put to front') is an operator that takes an x and puts that value on the front of list, just like (:) does.

The difference here (heh: 'difference') (sorry, mathematician humor) is what list is. For (:), list is of type [a] (or, directly and tautologically: list is a list), but for (|>), list is of type [a] → [a]. Or, translating: list is a function.

So? You've just reinvented the wheel with lists as functions now. Big deal.

Well, actually, what I've done is to reinvent the wheel as a meta-wheel, and so the big deal is this:

list <| x = list . (x:)

What we have here with (<|) (pronounced 'put to back') is a function that adds an element to the end of a list in — wait for it! — constant time. For 'regular' lists the best you can do that operation is in linear time, and so my work of constructing a document by appending to the end of a list that was occurring in O(n²) time has just gone to a linear-time operation. Not a big deal for a small document, but we found that once a document became more than a page or two, the operation went from 'a blink of an eye' to 'keeping your eyes closed until the cows came home ... that had been eaten by wolves.' This is not the case with lists as functions: document construction became reasonable endeavor (that is, it occurred so quickly for us mere humans, living in this non-nanosecond-time, we didn't notice the elapsed time).

So, I've been a sly thing in one respect. I still haven't told you what a (functional) list is. I've defined the object view of lists, and I've declared what a function view of lists, but haven't defined them.

Here. Allow me to define them now:

empty = id

There you go. There are the 'definitions.' I say 'definitions' because with that sole definition, everything works, for to ground a functional list, we simply pass it an empty list:

empty [] ⇒ []

Or even whatever list we are working with:

empty [1,2,3] ⇒ [1,2,3]

When you append something to an empty list, you get that something back.

AND empty works as the seed of the 'put to' operators:

(5 |> 6 |> 2 |> empty) [1,2,4] ⇒ [5,6,2,1,2,4]

and:

(empty <| 1 <| 2 <| 3) [4,5,6] ⇒ [1,2,3,4,5,6]

It all works!

Summary
In this article we've demonstrated that there's more than one way to look at, specifically, lists. The standard way is to view them is as objects, and for the most cases, that works, and works well: this view provides a syntax that makes list processing simple and intuitive.

We've also shown that that is not the sole way to view things, and this view can be constraining, particularly when lists are played against type as a queue or a document assembler. In these cases it becomes simpler, declaratively, to view lists as functions, and not only does that provide a syntax for simple list construction either at the beginning or the end of the list, but also provide constant-time construction at either end. Furthermore, defining this view is as simple as viewing the empty list as id and then using the partial function of (:) ('cons'). That's the generative view. Then, to extract the ("real") list from that view, it's as simple as sending a list (for example, []) to that functional list to ground the value for disposition.

In these special cases of working at the back end of a list, that aren't all that rare, the functional view of list processing gives the programmer expressivity and efficiency, eliminating the chore of appending to the end or reversing the target list. I quite enjoy list processing this way: it gives me a fresh perspective on an old friend and makes list processing in these cases easy and fun.

Endnotes

1	There is an article at http://wordaligned.org/articles/next-permutation that provides a simple, clear explanation of the lexicographic permutation algorithm with a very nice demonstrative example if you are so inclined to investigate.
2	Laurent Siklóssy, Let's Talk Lisp talks about MAPCAR in chapter 6. And, if I may: this book is one of the rare ones. It's one of those books like Smullyan's To Mock a Mockingbird or van der Linden's Deep C Secrets (with a fish on the orange book cover, no less!) or, and let us not forget the ultimate: Hofstadter's Gödel, Escher and Bach: the Eternal Golden Braid (I mean, even the title is a pun, Doug doesn't waste time in having fun, does he? He gets right to it!) that make you a better person but you don't notice it, but everybody else does, because you are constantly busting out laughing or grinning from ear-to-ear at the cleverness of their prose. Why do books about esoterica have to be so heavy! These esoteric books show that they don't have to be heavy in the lightness they deal with the subject (and deal with dealing with these esoteric subjects). And who is that bright young man who left such a feisty review of that book back in (*le gasp!*) 2001? I can see a promising future for that boy, just so long as he doesn't get too big for his britches. À propose de rien, what are britches? *ahem* Yes, so those books are three of my favorites ... which ones are yours?
3	Bjarne Stroustrup, The C++ Programming Language, 3rd ed., §18.4
4	Such a view of lists has a name: these functional list types are called difference lists from the Prolog community. The standard Haskell library does not have Data.DList [sad loss, I say!] but this type is provided by Don Stewart of Galois in the hackageDB under the dlist package. The Data.DList works great, but I've implemented my own system that is more than twice as fast as I provide several specialized implementations of difference list operators that take a more direct approach in their implementations (foldr is elegant but can be a costly operation). If you'd like to use my Data.DiffList package please contact me, and I'll be delighted to share this library.

Using Difference Lists

I posted my enthusiasm about difference lists for Haskell earlier this month, but then became sidetracked by combinators and reading lists, so, let's get back on track.

Difference lists are a (very) useful data structure in Prolog, particularly when it comes to parsing with definite clause grammars (DCGs) and when it comes to list construction (again, using DCGs). Why? Well, to answer that question, let's examine the structure of difference lists. The Prolog (or relational) representation of a difference list is of the form:

X = [1,2,3|Y] - Y

What that relation describes is that X is the difference of the pair of lists of (first) [1,2,3] appended with the list Y minus (second) the list Y.

Well, what is the value of the list Y? To a Prologian, this question is not important (for Y, being a logic variable, can be any list or, even, not a list at all because the variable is still uninstantiated (a "free" variable)). Its importance is that it gives us an "instant" index into the list after the elements we've already processed. The significance of that index for parsing is that we now have a stream over the parsed (list) data, which gives us the ability to translate BNF grammars directly into working parsers. The significance for list construction is that we "simply" walk "backward" through the DCG to construct a list from a (parsed) internal representation, without paying the linear cost of either (a) traversing the list each time to add a new element (which results in exponential time list construction) or (b) building the list in reverse (adding new elements to the head of the list) and then applying reverse to the end result.

"Big deal!" you scoff, "zippers [also called 'finger trees'] already give us indices into data structures. Who needs a funny-looking specialized zipper just for lists?"

"Good point!" is my response. Zippers are powerful and flexible data structures that not only provide that index over any data structure, but, even better than difference list's index that only goes forward (with any dignity) in constant time, the zipper's index can go both forward and backward through that (generic) structure in constant time. So, if you are not familiar with zippers, I request that you run, don't walk, to a good overview to learn more about their utility.

With all their flexibility and power, in certain situations, a zipper is not the correct choice for some list processing tasks; the difference list's simplicity shines in these situations. First, for the unidirectional index of the difference list (it moves forward through the list well, but backwards ... not so much), this, for list construction purposes, is hardly ever an issue, and if it becomes one, then backtracking is easily installed with some MonadPlus magic. Next, you, the coder, are responsible for constructing a zipper list data type each time you need one, but Don Stewart has provided Data.DList; no construction necessary! Last, an example structure of a zipper list, for the list a++b is (reverse a,b), so if we wish to reconstruct the original list, for an a of large magnitude, we still pay the linear (reverse) cost in reconstruction as well as the linear cost of appending b to that result.

You heard it here first, folks — difference lists: [zipper lists] can't touch this!

Okay, I've finished throwing it down for now. Let's look at difference lists from the Haskell perspective and then use this data structure in a list construction example.

> import Data.DList

For my examples, I'm going to be looking at the subset of difference lists that I can compare and see:

> instance Eq a => Eq (DList a) where
>     x == y = toList x == toList y

> instance (Eq a, Show a) => Show (DList a) where
>     show x | x == empty = "\\x -> [x]"
>            | otherwise  = "\\x -> [" ++ show (head x)
>                           ++ doShow (toList (tail x)) ++ ":x]"
>         where doShow [] = ""
>               doShow (a:b) = ", " ++ show a ++ doShow b

With the above instance declarations, we see that

(singleton 1) `snoc` 2 `snoc` 3

gives us the representation

λ x . [1, 2, 3:x]

... snoc appends an element to the end of a list (so it's the reverse of cons).

Prologians are always smug with their ability to create an infinite stream of 1s with X = [1|X]. And, no doubt about it, Prolog is a programming language that makes list construction easy ... *ahem* almost as easy as list construction in Haskell ("Your list comprehensions outshine even Prolog for sure..."):

repeat 1
[1,1..]
... and now with difference lists ...
let x = unDL (singleton 1) x in x

But no self-respecting Prologian would freeze their interpreter with a such a rash proof; Haskellians have no such concern, thanks to weak head normal form:

take 5 (repeat 1)

So there!

Let's examine an application of difference lists. I have a little scanner that I use to help me in my oration. The meat of the algorithm (before difference lists) was as follows:

> lettersIn word = lettersIn' word []

> lettersIn' [] ans = reverse ans
> lettersIn' (h:t) ans | isLetter h = lettersIn' t (h:ans)
>                      | otherwise  = reverse ans

Ugh, yes, reverses galore! This is an oft-recurring pattern in Haskell code that is very easily fixed with some difference list magic:

> lettersIn word = lettersIn' word empty

> lettersIn' [] ans = toList ans
> lettersIn' (h:t) ans | isLetter h = lettersIn' t (ans `snoc` h)
>                      | otherwise  = toList ans

A very simply example, I grant you, for if we take a list whose elements are all in the set of the alphabet, the above code is a very complicated way of reinventing the id function. Or, put another way, who's going to teach me about scanl? Hm, would I be required to use the continuation Monad to escape the scan, I wonder? But you get the general idea for list construction, right? Instead of building the list by adding to the head ("cons"ing) and then applying reverse to the result, the different list allows one to "snoc" each element and return the correctly ordered result. For a single list construction, the benefit may not be all that obvious, but when one builds, e.g., an XML generator for a complex internal representation, reversing the reverse of the reversed reversed child element becomes an odious labour — difference lists eliminate all the internal juggling, replacing that complication with a straightforward constant-time list and element in-place append.

So, next time you need to do some list construction, instead of falling back on the reverse standby, flex your new difference list muscles; you'll be pleasantly surprised.

Difference Lists in Haskell!

Oooh! Scrumptious!

I've discovered while exploring one of my Tangents, the Comonad.Reader, that a member of the Galois team, Don Stewart, has developed a Difference List library ... in Haskell. My initial scan of the library is that it is simple, elegant and practical. Three feathers in his cap!

Excuse me while, initially, I replace in my code the 'cons then reverse' list-building pattern with Don's DList. I also can't wait to find other applications for this type.

While I'm away doing that, you can read sigfpe's blog, particularly his clever implementation of the Fibonacci series as a comonad.