2

I was reading on this Haskell page about adding an element to the end of a List.

Using the example, I tried it out for my self. Given the following List I wanted to add the number 56 at the end of it.

Example:

let numbers = [4,8,15,16,23,42] 
numbers ++ [56]

I was thrown off by this comment:

Adding an item to the end of a list is a fine exercise, but usually you shouldn't do it in real Haskell programs. It's expensive, and indicates you are building your list in the wrong order. There is usually a better approach.

Researching, I realize that what I'm actually doing is creating a List with 56 as the only element and I'm combining it with the numbers list. Is that correct?

Is using ++ the correct way to add an element to the end of a List?

  • Are you familiar with how `[a]` is defined? It's a nested structure, like a Russian doll: the "end" of the list is better thought of as the center. If you wish to add a new smallest doll you'll need to unwrap every layer (an O(n) operation). Try implementing `++` for yourself – jberryman Nov 02 '18 at 17:24
  • "It's expensive, and indicates you are building your list in the wrong order. There is usually a better approach" part is very important. May be you should concentrate on how to create your `numbers` list in the reverse order first and then just do like `56 : numbers` for efficiency. – Redu Nov 02 '18 at 17:35

2 Answers2

7

++ [x] is the correct way to add an element to the end of a list, but what the comment is saying is that you shouldn't add elements to the end of a list.

Due to the way lists are defined, adding an element at the end always requires making a copy of the list. That is,

xs ++ ys

needs to copy all of xs but can reuse ys unchanged.

If xs is just one element (i.e. we're adding to the beginning of a list), that's no problem: Copying one element takes practically no time at all.

But if xs is longer, we need to spend more time in ++.

And if we're doing this repeatedly (i.e. we're building up a big list by continually adding elements to the end), then we need to spend a lot of time making redundant copies. (Building an n-element list in this way is an O(n2) operation.)

If you need to do this, there is usually a better way to structure your algorithm. For example, you can build your list in reverse order (adding elements at the beginning) and only call reverse at the end.

melpomene
  • 84,125
  • 8
  • 85
  • 148
5

It's the correct way in that all ways of doing it must reduce to at least that much work. The problem is wanting to append to the end of a list at all. That's not an operation that's possible to do efficiently with immutable linked lists.

The better approach is figuring out how to solve your specific problem without doing that. There are a lot of potential approaches. Picking the right one depends on the details of what you're doing. Maybe you can get away with just using laziness correctly. Maybe you are best off generating the list backwards and then reversing it once at the end. Maybe you're best off using a different data structure. It all depends on your specific use case.

Carl
  • 26,500
  • 4
  • 65
  • 86