At 09:25 -0400 1999/04/29, Chris Okasaki wrote:
>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) []
A set, if properly implemented, is a like a list by which one cannot assume
that the elements come in a certain specific order. The well ordering used
to put the elements on the balanced tree is not part of the interface of
the set, but the implementation, even though one can allow the user provide
such a well ordering to achieve different implementation effects.
Part of the set interface can be that one knows that there is a always a
first or smallest element, and that it is possible to exhaust the set by
successively removing the first element. But from implementation to
implementation, one cannot ensure the elements come out in a specific order
(unless the user writes a specific implementation of the sorting order);
expecting this is logically wrong and if that is expected, sets should not
used, but a list instead.
So the definition of fold() for sets, if one only can lop off the first
element of a set, becomes the same as for lists. It does not change with
the particular implementation (balanced trees or whatever). For example
set_foldl :: (a -> b -> a) -> a -> {b} -> a
set_foldl f z {} = z
set_foldl f z (x:xs) = foldl f (f z x) xs
Here one just knows that in the set {x} ++ xs, x is one element, the first,
but there is no way to determine which element x is, unless you go in and
fiddle around with it by writing your own sorting order (but if you do for
this purpose, sets are probably the wrong idea anyhow). Unlike the case
lists, (x:xs) simply means "take one element", but you do not know which
one, that is the very idea of a set.
If the result of this foldl varies from implementation to implementation in
a significant way you do not want, then either you have chosen a bad f to
fold with, or sets should not be used at all.
Hans Aberg
* Email: Hans Aberg <mailto:[EMAIL PROTECTED]>
* Home Page: <http://www.matematik.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
