Edison 1.2rc2

[Robert Dockins]

On Friday 03 March 2006 08:28 pm, you wrote:
> Robert Dockins writes:
> > The second release candidate for Edison 1.2 is now ready for
> > comments.  The notable changes from RC1 are:
> >
> >    * add strict variants of all folds and reduces
>
> You know, I was looking through the code last night and thought, "what
> about foldl'?" Funny.
>
> That being said, eight variants of fold* (plus six variants of reduce*)
> feels excessive to me. I can understand the desire for generality, but
> I'm not sure it's possible to decide between, say, foldr and foldr'
> without knowing the sequence type.

Well, that's certainly an issue I considered when adding them to the API.

> As I understand it, with regular lists you almost always[*] want either
> foldr or foldl', because foldl builds up a chain of unevaluated thunks
> and foldr' has linear call stack growth. (When I was learning ML, we
> were told to always prefer foldl over foldr for that reason.)
>
> With reverse lists (i.e., Rev []), the situation is reversed: foldr' is
> tail-recursive, foldl is fully lazy, and foldr and foldl' have linear
> growth.

I toyed for a good while with only defining some of the strict folds, or doing 
some other halfway measure.  The thing that eventually made be decide to 
throw in the whole kitchen sink (all the strict folds) was the realization 
that the API is specified at a purely semantic level; at that level, the only 
thing that matters about strict folds is that they have exactly the same 
semantics as the non-strict fold given a combining function which is strict 
in the correct argument(s) (otherwise they are guaranteed to be the same 
except that the strict fold may diverge in cases where the non-strict fold 
does not).  When it comes time to implement, the strict folds give you more 
leway to force closures early BUT YOU DON'T HAVE TO!  For the regular list 
example, I could define foldr' = foldr and it would be correct according to 
the specification.  For now I have defined all the implementations to be as 
strict as possible in all cases, but I can make them lazier later if it turns 
out to have better space behavior; as you mention, foldr' on regular lists is 
problematic and it will probably be the first thing to be reverted to a lazy 
implementation.

> For the other sequences, there may not be clear winners. With
> SimpleQueue, for example, the choice between foldr and foldr' might
> depend on how the queue is arranged.
>
> Maybe it would be better to have each implementation default to the
> strictness that's most likely best, at least in the generic Seq
> interface. That way, [] would get strict foldl and non-strict foldr, but
> Rev [] would get strict foldr and non-strict foldl. Individual modules
> could provide extra variants as desired outside the class interface.

Both the collection and the associated collection have fold (and fold') which 
folds over elements in an unspecified order.  Perhaps I could add that to the 
sequence API to give the "best behavior" choice to the sequence implementer.  
Then for lists you would have (lazy) fold = foldr and (strict) fold' = 
foldl'.

> [*] I guess you might want a non-strict foldl with lists if the foldee
> is expensive enough that building up a pile of thunks is worth it if
> they can potentially be skipped.

> > -- Edison defines 'subset' and 'subsetEq' in the set API.  Data.Set
> > has operations with the
> >     same meanings named 'isProperSubsetOf' and 'isSubsetOf'.  I am
> > considering adoping the
> >     Data.Set names, but they are quite a bit longer.  Also what about
> > the meaning of "subset"
> >     vs "proper subset"?  What do you find most intuitive?
>
> I would go with subset and properSubset. The "isSubsetOf" form only
> makes sense if used in-line, but we have (|=) for that.

I'm leaning in this direction as well; I think I've pretty well decided the 
names as they stand now have to go (they contradict standard usage), and I 
don't really like the Data.Map names.

> > In addition, I'm interested in any API related feedback you might
> > have.
>
> Is there a reason why the TernaryTrie and the PatriciaLoMap don't
> implement OrdAssoc?

Not really.  When I inherited Edison, none of the associated collections 
implemented the Ord* classes (I don't know why).  I added AssocList and 
StandardMap because they were easy.  The others are significantly more 
complicated and I thought it was more important to work out the API issues 
and kick 1.2 out the door before tacking this (same reason the 'strict' folds 
for TernaryTrie are really just the non-strict folds).

> For the Seq class, I'd rather have the O(n) stuff listed with the
> implementations, rather than having a default in the interface.

Noted.  Its a dreadfully tedious cut-n-paste job which is why I haven't done 
it; patches and clever scripts to do this are welcome ;-)  Of course, it 
would be nice to have time complexity for the Collection and Associated 
Collections as well...

> Finally, thanks for reviving Edison. I had always been disappointed by
> its obscurity.

Indeed; it has always seemed to me like a great project that never got the 
attention it deserved.


Thanks for your comments!
Rob Dockins