[Haskell-cafe] *GROUP HUG*

[Evan Laforge]

On Tue, May 24, 2011 at 10:03 AM, Stephen Tetley
<stephen.tetley at gmail.com> wrote:
> Neither OCaml nor PLT Scheme cache the length or they didn't a year of
> two ago when someone asked this question on the Haskell Beginners list
> and I checked the respective source trees. As the PLT Scheme list was
> implemented in C at the time (maybe it still is?) I was a bit
> surprised by this.

I dunno, I hardly ever use length and when I do it's always lists I
know are very short.  And it tends to be shortcuts like 'drop (length
prefix) word' because I'm too lazy to write a special function.  Lists
are variable length and homogenous, so the main thing you do is
iterate over them, I don't see much call for getting their length.
Length is handy for arrays because you iterate with an index, but
lists are different.

Adding an int to every cons cell would make lists larger by 2/3x and
could hurt more than help.  That would be a pretty heavy price to
speed up a rarely used function.

I'm not familiar with java and c++ list implementations, but I imagine
they don't share tails, presumably because of mutability.  So a cached
length is reasonable for them, especially because they're probably
expecting it to be used as an array with fast splicing, which implies
it's probably large.  After all, if you simply wanted to iterate over
something small you would have used an array.  So, it's a different
situation.


On the catMaybes thing, I have a function 'mapMaybe = Maybe.catMaybes
. map'.  I turns out I only ever used catMaybes after mapping a Maybe
function, so I hardly ever use catMaybes anymore.  I suppose it should
have been maybeMap for consistency with concatMap.