CODEWITHSUNDEEP
haskell
abden003
abden003

Reputation: 1335

Space complexity of the following two lambda functions

I was reading the following: https://en.wikibooks.org/wiki/Haskell/Graph_reduction, and it had the following written:

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).

Is this statement correct? I'm unable to see how they are different. Once executed they both seem to take the same amount of time and space, and before executing you can lazily determine that their types are compatible.

Upvotes: 2

Views: 236

Answers (1)

Luis Casillas
Luis Casillas

Reputation: 30227

One way to do this is to evaluate the expressions by hand and observe how the maximum length of the intermediate expressions grows as a function of n. This is trickier to do than it sounds, because of the sharing of xs inside the definition of your lambas, but I'll do it and hopefully it'll be helpful.

First, let's write definitions for head and last:

head :: [a] -> a
head (a:_) = a

last :: [a] -> a
last (a:[]) = a
last (_:as) = last as

Now, armed with this, let's do the first one:

(\xs -> head xs + last xs) [1..n]
  => let xs = [1..n] in head xs + last xs
  => let xs = 1:[2..n] in head xs + last xs
  => let xs = 1:[2..n] in 1 + last xs
  => 1 + last [2..n]
  => 1 + last (2:[3..n])
  => 1 + last [3..n]
  => 1 + last (3:[4..n])
  .
  .
  .
  => 1 + last (n:[])
  => 1 + n

As you can see, the expressions in the intermediate steps have some constant upper bound on their size, and the value of n doesn't matter. Now let's try your second example. I've chosen to illustrate the structure sharing and the forcing by making the list of bindings in the let grow:

(\xs -> last xs + head xs) [1..n]
  => let xs = [1..n] in last xs + head xs
  => let xs = 1:[2..n] in last xs + head xs
  => let xs  = 1:xs2
         xs2 = 2:[3..]
     in last xs2 + head xs
  => let xs  = 1:xs2
         xs2 = 2:xs3
         xs3 = 3:[4..]
     in last xs3 + head xs
  .
  .
  .
  => let xs  = 1:xs2
         xs2 = 2:xs3
         xs3 = 3:xs4
             .
             .
             .
         xsn = n:[]
     in last xsn + head xs
  => let xs  = 1:xs2
         xs2 = 2:xs3
         xs3 = 3:xs4
             .
             .
             .
         xsn = n:[]
     in n + head xs
  => n + 1

As you can see, the size of the largest expression is going to be proportional to n. This means that the evaluation uses O(n) space.

The difference between the two examples is an artifact of the fact that the + function is forcing its first argument before forcing the second one. As a general rule, when you have a function with multiple arguments one of them must be forced before the others, and the order in which it happens can have subtle effects like these.

Upvotes: 2

Related Questions