Re: [Haskell-cafe] Rewriting ord (revisited)

On 9/30/07, PR Stanley 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 (

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.