Specifications of 'any', 'all', 'findIndices'

[Jerzy Karczmarczuk]

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
   "specification"

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
you that...

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

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



Jerzy Karczmarczuk