> FiniteMap
> implemented via balanced binary trees.
> Such a useful thing - has not it to move to the Standard library?
> To my mind, it is more important for Haskell than arrays.
Perhaps, but I'm not willing to add anything to the library at this
stage. Two months ago maybe. Now, no.
> Standard Prelude, standard library define the values like
>
> span, foldl, minimum, sort, and so on.
>
> These definitions, they, probably, only specify what map has to be
> computed. And the implementation is free to substitute any correct
> definition. Right?
Yes, and the introduction to Appendix A tries to say this:
"In this appendix the entire \Haskell{} Prelude is given. It constitutes
a {\em specification} for the Prelude. Many of the definitions are
written with clarity rather than efficiency in mind,
and it is {\em not} required that the specification be implemented as shown
here."
Should I clarify this more? How?
> In particular, in Haskell-1.4, sort is defined via insert.
> But this makes O(n^2) computational cost in the worst case.
> While the merge sorting gives O( n*(log n) ). So the
> implementation
> are, probably, encouraged to substitute merge sorting for sort - ?
Absolutely. Same for foldl, and your other examples.
Since this point clearly did not come over to you, can you suggest
how I might state it more clearly?
> *
> Some operations with association lists.
> In Haskell-1.4 libraries i could not find a good replacement for
> the following operations:
Same as FiniteMap. Reasonable suggestions, but too late.
Simon
