Is there any difference between those?

user_13293475 0
Viewed 61

I just started to learn Haskell and while reading the "Learn You a Haskell" book I got a question. Is there any difference between those two ways of doing essentially the same thing:

qtz 1 = [1]
qtz x
    | even x = x : qtz (x `div` 2)
    | odd  x = x : qtz (x * 3 + 1)

-- this
length (filter (>15) (map length (map qtz [1..100])))
-- and this
length (filter (\ xs -> length xs > 15) (map qtz [1..100]))
haskell
1 Answers

No, both will yield the same answer, there is a difference in the subexpressions filter (>15) (map length (map qtz [1..100])) and filter (\ xs -> length xs > 15) (map qtz [1..100]) however. In the former, you create a list of lengths, and then filter out the elements that are less than or equal to 15, so this gives us:

Prelude> filter (>15) (map length (map qtz [1..100]))
[17,20,18,18,21,21,16,16,24,112,19,19,19,107,27,22,22,22,35,110,30,17,17,17,105,25,25,25,113,113,20,33,20,33,20,20,108,108,28,28,28,103,23,116,23,23,23,36,36,23,111,111,31,31,18,31,18,93,18,18,106,106,119,26,26,26]

In the latter we make a list of sequences, and we filter out the sequences that have less than or equal to 15 elements:

Prelude> filter (\ xs -> length xs > 15) (map qtz [1..100])
[[7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1],[9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1],[14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1],…]

But that does not matter, since you call length on these lists, and length is not interested in the individual elements, but only in the number of elements, so it basically "throws away" the elements in the list.

Using length to determine if a list has more than a given number of elements is often not that efficient. If the list contains thousands of elements, it will first determine the length, and then compare that to 15. If the list has infinite length, it will even get stuck in an infinte loop. Some utility libraries offer a function like lengthAtLeast :: Int -> [a] -> Bool, which will stop from the moment the required length is reached, or the list is exhausted.

You can thus rewrite the function to:

import Data.List.HT(lengthAtLeast)

(length . filter (lengthAtLeast 16) . map qtz) [1..100]
user_675790
Related