Edison 1.2rc2

David Menendez zednenem at psualum.com
Fri Mar 3 20:28:57 EST 2006

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.

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

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.

[*] 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.

> 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?

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

Finally, thanks for reviving Edison. I had always been disappointed by
its obscurity.
David Menendez <zednenem at psualum.com> | "In this house, we obey the laws
<http://www.eyrie.org/~zednenem>      |        of thermodynamics!"

More information about the Libraries mailing list