CODEWITHSUNDEEP
haskell
Jason Hu
Jason Hu

Reputation: 6333

execution order influenced space complexity in haskell

i am reading about haskell in wikibook:

https://en.wikibooks.org/wiki/Haskell/Graph_reduction

and in the article, there is an example that puzzles me:

Tricky space leak example:

(\xs -> head xs + last xs) [1..n]
(\xs -> last xs + head xs) [1..n]

The first version runs on O(1) space. The second in O(n).

how come?

I assume last is implemented like following:

last [] = error ""
last [r] = r
last (_:t) = last t

so a tail recursion should take constant space. why the second one would yield linear space?

Upvotes: 2

Views: 77

Answers (1)

ErikR
ErikR

Reputation: 52039

The simple answer has to be that when evaluating a + b, the expression a gets evaluated before b in practice.

Normally last xs only takes O(1) space - the elements of xs can be discarded as last traverses down the list. However, if xs is needed for another expression, the expansion of xs must be kept in memory for the other expression, and this is what is happening in the second case since it appears that xs is needed for head.

In the first case head xs is evaluated "first" which only evaluates the first element of xs. Then last xs is evaluated, traversing down the list. But since there isn't any further need for the elements of the list they may be discarded during the traversal.

Upvotes: 2

Related Questions