[Haskell-cafe] Rewriting ord (revisited)

[Felipe Almeida Lessa]

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..]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41]
Prelude> length $ takeWhile (< c) [0..]
42
Prelude> [1 | x <- [0..], x < c]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1Interrupted.
Prelude> sum [1 | x <- [0..], x < c]
Interrupted.

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 [].

HTH,

-- 
Felipe.