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