CODEWITHSUNDEEP
haskell
PepeHands
PepeHands

Reputation: 1406

Haskell function parameter force evaluation

I need to take last n elements from list, using O(n) memory so I wrote this code 

take' :: Int -> [Int] -> [Int]
take' n xs = (helper $! (length $! xs) - n + 1) xs
    where helper skip [] = []
          helper skip (x : xs) = if skip == 0 then xs else (helper $! skip - 1) xs

main = print (take' 10 [1 .. 100000])

this code takes O(|L|) memory where |L| -- is the length of given list.

But when I write this code

take' :: Int -> [Int] -> [Int]
take' n xs = helper  (100000 - n + 1) xs
    where helper skip [] = []
          helper skip (x : xs) = if skip == 0 then xs else (helper $! skip - 1) xs


main = print (take' 10 [1 .. 100000])

This code now takes only O(n) memory (the only chage is (helper $! (length $! xs) - n + 1) -> helper (100000 - n + 1))

So, as I understand, Haskell for some reason doesn't evaluate length xs before the first call of helper so it leaves a thunk in skip and haskell has to keep this value in every stack frame instead of making tail recursion. But in second piece of code it evaluates (100000 - n + 1) and gives the pure value to the helper.

So the problem is how to evaluate the length of list before the first call of helper and use only O(n) memory.

Upvotes: 3

Views: 619

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 152682

The other answer referred to what it means to be a good consumer. You have posted two versions of your function, one which works for arbitrary-length lists but is not a good consumer, and one which is a good consumer but assumes a particular list length. For completeness, here is a function that is a good consumer and works for arbitrary list lengths:

takeLast n xs = go (drop n xs) xs where
    go (_:xs) (_:ys) = go xs ys
    go _ ys = ys

Upvotes: 8

leftaroundabout
leftaroundabout

Reputation: 120711

The second version does not really take only O(n) memory. Regardless of what take' does: you start off with a list of length L, and that has to be stored somewhere.

The reason it effectively takes O(n) memory is that the list is only used by one “good consumer” here, namely helper. Such a consumer deconstructs the list from head to last; because no reference to the head is needed anywhere else, the garbage collector can immediately start cleaning up those first elements – before the list comprehension has even built up the rest of the list!

That changes however if before using helper you compute the length of that list. This already forces the entire list to be NF'd†, and as I said this inevitably takes O(L) memory. Because you're still holding a reference to be used with helper, in this case the garbage collector can not take any action before the whole list is in memory.

So, it really has nothing to do with strict evaluation. In fact the only way you could achieve your goal is by making it less strict (require only a sublist of length n to be evaluated at any given time).

†More precisely: it forces the list's spine to normal form. The elements aren't evaluated, but it's still O(L).

Upvotes: 5

Related Questions