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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Locked
