3

As a followup to this question, I'm attempting to understand how not to add elements to a list using ++.

From this answer:

Again if you only want to append a single element to the list, that is not a problem. This is a problem if you want to append n elements that way to a list, so if you each time append a single element to the list, and you do that n times, then the algorithm will be O(n2).

So from my understanding, this means you shouldn't do this:

let numbers = [1,3,5,10,15]
newNumbers = numbers ++ [27]
listofnumbers = newNumbers ++ [39]

Is this what the bold text in the quoted answer telling you not to do? If not, using code, what is the bold text warning you not to do?

  • If you are adding multiple items to a list, it is more efficient to append all of the times at once, rather than looping through, adding one at a time. – tylerweir Nov 18 '18 at 15:49
  • You have to find a way to change your appending order from left associative to right associative. In another words you shouldn't do like `((numbers ++ new1) ++ new2) ++ new3)` but `(numbers ++ (new1 ++ (new2 ++ new3)))`. I would also advise you to have a look at [difference lists](http://learnyouahaskell.com/for-a-few-monads-more) towards the end of the chapter. – Redu Nov 18 '18 at 15:50
  • check out [this canonical answer](https://stackoverflow.com/a/13879693/849891) by [Daniel Fischer](https://stackoverflow.com/users/1011995/daniel-fischer) (also maybe [this one](https://stackoverflow.com/a/14942678/849891) (disclaimer: it's by me)) which talk about this stuff. – Will Ness Nov 18 '18 at 20:31
  • incidentally that [second question](https://stackoverflow.com/questions/14938584/haskell-foldl-poor-performance-with) *answers* your question here, with the example code it uses. – Will Ness Nov 18 '18 at 20:47

2 Answers2

1

The answer talks about a bad time complexity when it comes to appending elements to the end of the list. When you concat a list xs of length m and a list ys of length n together using (++) then xs ++ ys will have time complexity O(m) (under the assumption you evaluate xs ++ ys for a number of steps in proportion to m).

So if your list ys consists of a single element y (that is ys == [y]) then [y] ++ xs will be O(1) because you add it to the beginning but xs ++ [y] will be O(m) because you add it to the end of another list. So when you repeatedly add elements to the end of another list you will end up with O(m^2). So better do it within one go so you will have O(m).

Note that lists in Haskell are actually stacks which could have an infinite number of elements.

Elmex80s
  • 3,428
  • 1
  • 15
  • 23
  • if `xs++ys` is *O(m)* where `m = length xs`, how come `head ([1..]++[0])` doesn't take infinite time? – Will Ness Nov 18 '18 at 20:40
  • @WillNess Because of laziness. The time complexities from my answer where under the assumption you need to do a full evaluation and `xs` is finite. – Elmex80s Nov 18 '18 at 20:51
  • perhaps this assumption is important and should be included explicitly then. :) – Will Ness Nov 18 '18 at 20:55
  • @WillNess Well I could do `(xs ++ ys) !! (m - 1)` which would indeed need *m* steps. But it is under the assumption of a full evaluation of the expression of course. – Elmex80s Nov 18 '18 at 20:56
  • this is too vague. what if we have `ys = xs++[y]; zs = ys++[z]`. if `ys` is O(m) only after full access, this seems to leave `zs` with only one more step to be done, so *it* would now seem to become O(1) all of a sudden. the precise [canonical answer](https://stackoverflow.com/a/13879693/849891) already exists BTW. :) – Will Ness Nov 18 '18 at 21:00
  • @WillNess I honestly wonder if it is important, especially because I rarely come across this assumption when reading reflections by other people on time/space complexity of Haskell expressions (apart from papers which I do not read). But let me add it to the answer. – Elmex80s Nov 18 '18 at 21:01
  • @WillNess But full access of `zs` is still *O(m)* after all. – Elmex80s Nov 18 '18 at 21:06
0

Try these two functions with a large list (like [1..10000]) and see if you notice any difference:

func1 a [] = a
func1 a (x:rest) = func (a ++ [x]) rest


func2 a b = a ++ b
Mor A.
  • 3,805
  • 2
  • 16
  • 19
merlyn
  • 2,273
  • 1
  • 19
  • 26