[Haskell-cafe] appending an element to a list

[Tillmann Rendel]

Lanny Ripple wrote:
> My $0.02 is to say
> 
> -- O(1) longList ++ [5]
> 
> Yay.  I've got a thunk.  Oh wait, I need to access the '5'?  No 
> different than doing so for
> 
> -- O(n) until ((==5) . head) [l,o,n,g,L,i,s,t,5]
> 
> It's not the (++) that's O(n).  It's the list traversal.

Lets look at the actual reductions going on. To make the example easier,
I would like to use last instead of your complicated until. It shouldn't
make a difference.

Lets look at the reduction of (last "longList") to whnf first:

L)      last "longList"
L)  ~>  last "ongList"
L)  ~>  last "ngList"
L)  ~>  last "gList"
L)  ~>  last "List"
L)  ~>  last "ist"
L)  ~>  last "st"
L)  ~>  last "t"
     ~>  't'

The L prefixed marks all lines which are reduced by calls to last.
Clearly, we need n reduction steps here.

Now, what about last ("longList" ++ "!")?

A)      last ("longList" ++ "!")
L)  ~>  last ('l' : ("ongList" ++ "!"))
A)  ~>  last ("ongList" ++ "!")
L)  ~>  last ('o' : ("ngList" ++ "!"))
A)  ~>  last ("ngList" ++ "!")
L)  ~>  last ('n' : ("gList" ++ "!"))
A)  ~>  last ("gList" ++ "!")
L)  ~>  last ('g' : ("List" ++ "!"))
A)  ~>  last ("List" ++ "!")
L)  ~>  last ('L' : ("ist" ++ "!"))
A)  ~>  last ("ist" ++ "!")
L)  ~>  last ('i' : ("st" ++ "!"))
A)  ~>  last ("st" ++ "!")
L)  ~>  last ('s' : ("t" ++ "!"))
A)  ~>  last ("t" ++ "!")
L)  ~>  last ('t' : ("" ++ "!"))
A)  ~>  last ("" ++ "!")
L)  ~>  last "!"
     ~>  '!'

Calls to ++ are marked with A (for append). Now, we have to reduce a
call to ++ everytime before we can reduce a call to last, so we have

     n steps for calls of last as before
   + n steps for interleaved calls of ++
   + 1 step for the final call of ++
   + 1 step for the final call of last
   = 2n + 2 steps in total

The difference between (2n + 2) and (n) is (n + 2) and lies clearly in
O(n). So, by the addition of ++ "!" to our program, we had to do O(n)
reduction steps more.

Since we had to do O(n) reductions steps anyway, this didn't show up in
the overall complexity, but our program is only half as fast,
instead of constant amount slower, which seems to make a difference to me.

And other programs could suffer even more badly, since their complexity
could go up, e.g., from O(n) to O(n^2). A simple example is this naive
reverse function:

   reverse [] = []
   reverse (x:xs) = reverse xs ++ [x]

let's see how (last (reverse "long")) is reduced to whnf. I will not
even attempt "longList" ...

R)      last (reverse "long")
R)  ~>  last (reverse "ong" ++ "l")
R)  ~>  last ((reverse "ng" ++ "o") ++ "l")
R)  ~>  last (((reverse "g" ++ "n") ++ "o") ++ "l")
R)  ~>  last ((((reverse "" ++ "g") ++ "n") ++ "o") ++ "l")
R)  ~>  last (((("" ++ "g") ++ "n") ++ "o") ++ "l")

At this point, we have reduced reverse in n steps to an expression
containing n calls to ++. If ++ were O(1), we would need only O(n)
additional steps to finish the job. But see what happens:

         last (((("" ++ "g") ++ "n") ++ "o") ++ "l")
A)  ~>  last ((("g" ++ "n") ++ "o") ++ "l")

The first ++ was easy, only 1 reduction step.

         last ((("g" ++ "n") ++ "o") ++ "l")
A)  ~>  last ((('g' : ("" ++ "n")) ++ "o") ++ "l")
A)  ~>  last (('g' : (("" ++ "n") ++ "o")) ++ "l")
A)  ~>  last ('g' : ((("" ++ "n") ++ "o") ++ "l"))
L)  ~>  last ((("" ++ "n") ++ "o") ++ "l")
A)  ~>  last (("n" ++ "o") ++ "l")

Oups, for the second ++, we needed n reduction steps to move the first
char out of all these nested ++'s.

         last (("n" ++ "o") ++ "l")
A)  ~>  last (('n' : ("" ++ "o")) ++ "l")
A)  ~>  last ('n' : (("" ++ "o") ++ "l"))
L)  ~>  last (("" ++ "o") ++ "l")
A)  ~>  last ("o" ++ "l")

Another (n - 1) reduction steps for the second ++ to go away.

         last ("o" ++ "l")
A)  ~>  last ('o' : "" ++ "l"))
L)  ~>  last ("" ++ "l")
A)  ~>  last ("l")
L)  ~>  'l'

And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
steps. Counting together, we had to use

   n + (n - 1) + (n - 2) + ... = n!

reduction steps to get rid of the n calls to ++, which lies in O(n^2).
Thats what we expected of course, since we know that each of the ++
would need O(n) steps.

> I can further beat this pedantic point to death by pointing out there
> is no difference between
> 
> longList ++ [5]
> 
> and
> 
> longList ++ (repeat 5)
> 
> Getting to the first 5 is still O(n).

That's a different question. For the complexity of ++, the right-hand
side operand is irrelevant. The n means the length of the left-hand side
operand here.

   Tillmann