On Tue, May 24, 2011 at 10:03 AM, Stephen Tetley
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.