Laszlo Nemeth wrote:
> > For me what would make an STL-like library useful would be having
> > collections of algorithms available which operate on any `bulk type' for
> > which they make sense, but I suspect that to be suitably efficient
> > handwritten versions would be needed for each type. (Folding over sets vs
> > folding over lists vs folding over bags ..., etc). It might also make the
> > error messages for some prelude functions, e.g., map, more slightly
> > more vague:
>
> You don't need handwritten versions for folding, mapping etc. as these
> functions happen to be *unique* and they are quite easy to generate
> (which I do) within the compiler, by looking at the type declaration.
>
> What is problematic is to let the user (and the compiler) know that
> these things exist. If I figure out how to convince the renamer pass
> of GHC not to complain about the absence of functions which I generate
> later, I'd be happy to give you a copy. (It's 3.02, I'm afraid)
Unfortunately, it's not quite that easy. For a library with several
implementations
of, say, sets, you want the various implementations to support the same
fold function. In other words, in a library with abstract data types, you
want
the folds to be over the abstract data type, not over their concrete
representations.
Of course, the fold over the abstract data type will often be implemented in
terms of the fold over the concrete representation, but rarely will it be
the same function.
For example, if you have an implementation of ordered sets represented as
unbalanced binary search trees, then the abstract fold probably has a type
something like
abs_fold :: (a -> b -> b) -> b -> Set a -> b
whereas the concrete fold (which is the one that would be generated by your
system)
has a type something like
conc_fold :: (b -> a -> b -> b) -> b -> Set a -> b
One simple but inefficient implementation of abs_fold might be
abs_fold f c s = List.foldr f c (flatten s)
where flatten = conc_fold (\ xs a ys -> xs ++ a:ys) []
Chris
