[Haskell-cafe] Rewriting ord (revisited)

Felipe Almeida Lessa felipe.lessa at gmail.com
Sun Sep 30 08:32:12 EDT 2007

On 9/30/07, PR Stanley <prstanley at ntlworld.com> wrote:
> Hi
> This was my original version plus some modifications as advised by the list:
> f c = sum [1 | x <- ['\0'..], x < c]
> The following version was sent by a list member:
> f c = length $ takeWhile (<c) ['\0'..]
> Now, the sender asserted that the first version was much too slow.
> I'm wondering how the second version is any more efficient than the
> first. Looking at them through my C programmers' eye, as it were,
> both would require at least two loops before returning the ANSI value.
> Any ideas?

It's very simple. You know that ['\0'..] is in ascending order, of
course. So, if you want all elements (< c), then they must be a prefix
of that list. IOW, after you found the first x in ['\0'..] such that x
< c == False, then you know that all the elements following x will
also be greater than c, as they are greater then x and the operator
(<) is transitive.

In the first version, you traverse the entire list looking for those
elements, no matter what c you give. OTOH, the second traverse only
(ord c + 1) elements, stopping after reaching some x >= c, and it
would also work even if ['\0'..] were infinite, e.g:

Prelude> let c = 42 :: Integer -- Integers are unbounded
Prelude> takeWhile (< c) [0..]
Prelude> length $ takeWhile (< c) [0..]
Prelude> [1 | x <- [0..], x < c]
Prelude> sum [1 | x <- [0..], x < c]

Note that the second list will wait forever for the list comprehension
to finish before it can be seen that after those 42 ones there's the
empty list [].



More information about the Haskell-Cafe mailing list