The :: operator in F# always prepends elements to the list. Is there an operator that appends to the list? I'm guessing that using @ operator
[1; 2; 3] @ [4]
would be less efficient, than appending one element.
+2
A:
I'm guessing that using @ operator [...] would be less efficient, than appending one element.
If it is, it will be a negligible difference. Both appending a single item and concatenating a list to the end are O(n) operations. As a matter of fact I can't think of a single thing that @ has to do, which a single-item append function wouldn't.
sepp2k
2010-03-20 13:23:10
Before appending a list with a @ operator one needs to create a list of one element.
Max
2010-03-20 13:27:34
@Max: How would you implement an append function which did not create a single-element list containing the appended item? After all the tail of the tail of the tail of `[1,2,3,4]` is `[4]`. And you can't construct a list without constructing its tail.
sepp2k
2010-03-20 13:30:55
Why the downvote?
sepp2k
2010-03-20 18:54:05
Remember what it actually means to have a list: It means you have `a :: b :: c :: d :: []`. In order to append a new element to the end, you have to construct `a :: b :: c :: d :: e :: []`. And as was illustrated earlier, `e :: []` is the same thing as `[e]`. On the other hand, to prepend an element to a list, it's just `e :: original_list`.
Chuck
2010-03-20 23:21:38
-1 : as pointed out by Brian, since F# lists are singly-linked, adding to the end is an O(N^2) operation where N is the length of the list. This can become quite substantial for large lists. Much better to prepend as you build the list, then List.rev when returning the final result, which is O(N).
James Hugard
2010-03-21 17:33:52
@JamesHugard: Appending to a list is *not* `O(N^2)`. Appending N times is `O(N^2)`. Appending to a list once is `O(N)` which is the same as concatenating a list of length 1 to the end of the list. Yes, prepending is faster (because it is `O(1)`), but that was NOT the question. The question was whether concatenating a single item list to the end was slower than appending a single item. Which it's not.
sepp2k
2010-03-21 17:43:25
I stand corrected, and tried to remove the downvote (can't because it is too old). However, the answer may be misleading to some. Adding a single item, ONE TIME, will not be very expensive: O(N), where N is the original list size. BUT, lists are generally iteratively built in N operations and would therefore cost O(N^2), where N is the number of items to put in the list.
James Hugard
2010-03-25 14:29:29
Also, I'm not clear on the difference between "appending" and "concatenating" a single element; aren't they synonymous?
James Hugard
2010-03-25 14:36:29
@James: O(N) is certainly slow for adding an item to the list. And yes concattenating a one-item list and appending an element are the same sematically. The question was whether a function that knew it was only appending a single element would be faster than using `@` with a single element list. Which it's not.
sepp2k
2010-03-25 14:59:27
+1
A:
The efficiency (or lack of) comes from iterating through the list to find the final element. So declaring a new list with [4] is going to be negligible for all but the most trivial scenarios.
Brian Agnew
2010-03-20 13:24:56
+6
A:
As others said, there is no such operator, because it wouldn't make much sense. I actually think that this is a good thing, because it makes it easier to realize that the operation will not be efficient. In practice, you shouldn't need the operator - there is usually a better way to write the same thing.
Typical scenario: I think that the typical scenario where you could think that you need to append elements to the end is so common that it may be useful to describe it.
Adding elements to the end seems necessary when you're writing a tail-recursive version of a function using the accumulator parameter. For example a (inefficient) implementation of filter function for lists would look like this:
let filter f l =
let rec filterUtil acc l =
match l with
| [] -> acc
| x::xs when f x -> filterUtil (acc @ [x]) xs
| x::xs -> filterUtil acc xs
filterUtil [] l
In each step, we need to append one element to the accumulator (which stores elements to be returned as the result). This code can be easily modified to use the :: operator instead of appending elements to the end of the acc list:
let filter f l =
let rec filterUtil acc l =
match l with
| [] -> List.rev acc // (1)
| x::xs when f x -> filterUtil (x::acc) xs // (2)
| x::xs -> filterUtil acc xs
filterUtil [] l
In (2), we're now adding elements to the front of the accumulator and when the function is about to return the result, we reverse the list (1), which is a lot more efficient than appending elements one by one.
Tomas Petricek
2010-03-20 16:59:38
Surely there is a way to do this w/o the need to reverse the array at the end?
RodYan
2010-03-23 22:01:12
If you wanted to do this without reverting the list, you could use the implementation described by Norman Ramsey or use a mutation (in F#, you'd have to define mutable list). Using standard list type, there is no way to do that.
Tomas Petricek
2010-03-23 22:15:30
+6
A:
Lists in F# are singly-linked and immutable. This means consing onto the front is O(1) (create an element and have it point to an existing list), whereas snocing onto the back is O(N) (as the entire list must be replicated; you can't change the existing final pointer, you must create a whole new list).
If you do need to "append one element to the back", then e.g.
l @ [42]
is the way to do it, but this is a code smell.
Brian
2010-03-20 17:00:40
snoc ? And are you suggesting appending to a list is a bad idea ? In which case, how would you build up a list incrementally ?
Brian Agnew
2010-03-20 21:35:13
@Brian Agnew, you build it up at the front, then List.rev when you've finished (see Tomas's answer). Unfortunately, I'm not clever enough to tell you how many O()'s that makes.
Benjol
2010-03-20 22:34:10
@Benjol: Well, building the list initially requires one cons for each element, and the reverse operation does a fold over that list, once again doing one cons for each element. This means there's 2n cons operations needed to build a list of length n in such a manner. However, in big-O notation the constant factor of 2 is irrelevant here, so the task of building a list in such a manner is O(n).
bcat
2010-03-22 02:49:37