[Haskell-cafe] snoc vs cons

[Conor McBride]

Hi folks

Scary word warning: Monoid, Monad, Applicative, Traversable, Context,
   Cursor

> Eric:
>> Does anyone know of a good article which discusses snoc vs cons  
>> lists?

Derek:
> There's no reason to; there is no difference between a snoc list and a
> cons list.

There's no technical reason to, but sometimes there are human factors.

Basically, I want the lists in my code to resemble the lists in my head.
I occasionally implement typecheckers, and it's traditional to present
the context as growing on the right as you peel off binders from the
left: I prefer to use snoc-lists for them. Keeping the code consistent
with the mental picture means I seldom need to think about which things
are in scope of what, and so on. I make fewer reverse-parity mistakes.

Amongst my standard equipment, I keep

   data Fwd x = F0 | x :> Fwd x
   data Bwd x = B0 | Bwd x :< x

They're both monoids by concatenation, and Applicative with the
zipping behaviour, ie, not the ap of the [] monad, or any other monad
for that matter.

They're both Traversable, left-to-right, and that makes them really
different:

   traverse f (x :> xs)   does the effects of   (f x)   first;
   traverse f (xs :< x)   does the effects of   (f x)   last.

If I'm representing a cursor in a list, I use (Bwd x, Fwd x), or better,
Prod Bwd Fwd x where

   data Prod f g x = f x :*: g x
   type Cursor = Prod Bwd Fwd

so that I keep the left-to-right ordering, as well as fastest access  
to the
elements nearest the cursor.

As Prod lifts monoids and preserves applicative structure, I get the
zipping structure of cursor and the splicing-in-the-middle monoid for  
free.

This is yet another example of a type being not only a data  
representation,
but also a way of organising the structure of computations over that  
data.
Or in soundbitese... types don't just contain data, types explain data.

I'll crawl back under my rock now.

Cheers

Conor