[Haskell-cafe] snoc vs cons
ctm at cs.nott.ac.uk
Wed Jul 25 06:37:30 EDT 2007
Scary word warning: Monoid, Monad, Applicative, Traversable, Context,
>> Does anyone know of a good article which discusses snoc vs cons
> 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
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
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
This is yet another example of a type being not only a data
but also a way of organising the structure of computations over that
Or in soundbitese... types don't just contain data, types explain data.
I'll crawl back under my rock now.
More information about the Haskell-Cafe