Does anyone know of a good article which discusses snoc vs cons lists? E. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Tue, 2007-07-24 at 17:34 +0100, Eric wrote:
> Does anyone know of a good article which discusses snoc vs cons lists? There's no reason to; there is no difference between a snoc list and a cons list. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Derek Elkins writes:
> On Tue, 2007-07-24 at 17:34 +0100, Eric wrote: >> Does anyone know of a good article which discusses snoc vs cons lists? > > There's no reason to; there is no difference between a snoc list and a > cons list. Still, it (snoc) may be considered as a useful exercice in recursion, patterns, generalization, and whatever. This is not a good answer : "just no". Look : http://trevion.blogspot.com/2006/12/little-knowledge-gets-you-long-way.html http://citeseer.ist.psu.edu/cache/papers/cs/1482/http:zSzzSzbrahms.fmi.uni-p assau.dezSzclzSzpaperszSzGesGor97b.pdf/geser97parallelizing.pdf http://citeseer.ist.psu.edu/cache/papers/cs/27853/http:zSzzSzwww-2.cs.cmu.ed uzSz~rwhzSzcourseszSzmoduleszSzpaperszSzwadler87zSzpaper.pdf/wadler86views.p df and some others. And, anyway, when I was young, my Master used to say: "If you have nothing to say, then." Jerzy Karczmarczuk _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Derek Elkins
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 |
On Wed, 2007-07-25 at 11:37 +0100, Conor McBride wrote:
> 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 heartily agree with all that (and especially that last line is a large part of why I value static typing and see it as providing something dynamic typing doesn't). One way saying snoc lists are the same as cons lists is by saying that you simply change your point of view on cons lists to one where the first element is the "end". Of course, such distinctions can and often should be made by the type system. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |