Specifications of 'any', 'all', 'findIndices'
Tue, 23 Jan 2001 13:09:59 +0000
Koen Claessen wrote:
(about the definitions of any, all, etc.)
> The definitions in the Haskell report are a *specification*,
> not an implementation. It probably depends on the compiler
> which particular implementation runs faster.
> Therefore, the Haskell report provides a clear (yes, this is
> debatable) *possible* implementation, and the compiler
> writer is free to implement this in whatever way (s)he
> likes. As long as the implementation has the same functional
> behavior as the specification in the report.
I am sorry, but
any p = or . map p
is not an implementation-neutral specification, a
*functional* specification. This is a very concrete way
of doing things. As everybody knows, this is a folding process.
Of course, 'or' uses (normally, again, according to the Report
if I am not mistaken) 'foldr', and it is essentially trivial
to get rid of 'map', putting (||) and 'p' together in the
fold function, but:
1. Perhaps it is too optimistic to think that the compilers will
to that optimisation by themselves. Hugs uses literally this
2. I maintain my opinion that from the pedagogical point of view
this definition is imperfect. I think that the specification
should say no more nor less what 'any', 'notElem' etc. functions
provide, and put (possibly) in the Report that possible
implementations are (...)
But the generation of this "garbage", the intermediate list of
booleans, whether real or virtual only, goes beyond the semantics
of 'all', etc.
As Koen said, several people already commented on that.
And, I am afraid that this will continue. I can promise
Bjorn Lisper adds:
> ... What I in turn would like to add is that specifications like
> any p = or . map p
> are on a higher level of abstraction than definitions like
> any p  = False
> any p (x:xs) = p x || any p xs
> This makes it easier to find different implementations, which makes it
> easier to adapt the implementation to fit different architectures.
> The first specification is, for instance, directly data parallel
> which facilitates an implementation on a parallel machine or in hardware.
> Björn Lisper
map is data parallel. foldr not so obviously...
I am not sure about this higher level of abstraction. Unless, of course,
we want to use generalized, monadic maps, but then, also folds. And
we will produce, say, trees of boolean garbage instead of lists.