5

Is there any special reason that to construct list in Scheme you use

(cons 1 (cons 2 (cons 3 nil)))

instead of

(cons 3 (cons 2 (cons 1 nil)))

? While the first seems more obvious because it reads in the right order, the second is the one which actually reduces in the right order. Also, it seems more natural to construct a list starting with nil and adding elements to it, not the opposite. I've also found the latter has properties such as being very curry friendly: (cons 1) nicely becomes a function that appends 1 to a list.

  • Disclaimer: I've just asked a similar (not identical) question. Now that I have a better understanding of the problem I've realized this is much better. I hope it is OK. – MaiaVictor Dec 25 '13 at 22:18
  • 1
    The only way for cons to work like this if it appended at the end of the list (which is apparently what you want, considering the currying remark). That, however, is a slow and (imho) unnatural operation on linked lists. Do you only want 1 2 3 to occur on the right order in the source code, or are you dead set on cons appending? If it's merely the former, you can flip the arguments and get (cons (cons (cons nil 1) 2) 3). Or you could use the linear time append function which undoubtedly exists - why focus on cons alone? It's only one (admittedly primitive) of many list operation. – user7043 Dec 25 '13 at 22:39
  • 5
    BTW your natural-ness arguments seem nonsensical. (1) cons as is does "construct a list starting with nil and adding elements to it". It just adds the element at the front rather than the back. (2) The common definition of cons is exactly as currying friendly: (cons 1) is becomes "a function that prepends 1 to a list". Whether that's better or worse than the same thing for appending depends entirely on how you use the list. – user7043 Dec 25 '13 at 22:43
  • @delnan great argument, I didn't see it like that. Thanks! – MaiaVictor Dec 25 '13 at 23:12
  • @delnan the second one still reduces on the right order and has the property that the newest inserted elements are reached in O(n), not the first. Somehow it still seems a little more natural to me, but I'm partially convinced. – MaiaVictor Dec 25 '13 at 23:20
13

How do you propose the head be reached in this reversed list? If not using mutable structures the reversed list would only be performant if you made the head linear time and tail constant. But now you've got the exact same structure as before except you're calling the head the tail and vice versa.

the structure is the way it is because regardless of which side you declare to be the front or the back, that particular form is the only known one with constant time readahead and constant time insert without mutation or doing amortization trickery.

you're getting hung up on the terms thinking one side could be head or tail but those terms don't matter, the part that counts is the structure.

  • 4
    @Dokkat side note, I can't suggest enough if you're wading into this area and having questions about it regarding FP and how data structures work, seriously read Okasaki's thesis, often times this is suggested as just fundamental reading for FP, but for your specific question it literally holds the answer. Okasaki's teaches you to understand how data structures work and why they are formed the way they are in pure functional languages, which if you had that understanding you wouldn't be asking this question - so read it, you'll be enlightened – Jimmy Hoffa Dec 26 '13 at 16:08
3

Because appending to the end of a linked list is O(n) and appending to the front is O(1). The operation you're looking for is called snoc and can be implemented. But inefficiently.

To see why, realize that when you append to the back of a list, if you don't mutate anything, every single element must be copied, where as with appending to the front, you can just allocate a cons cell and have it point to the existing list, a relatively cheap operation.

  • That doesn't make sense, appending to the end of a linked list is O(n) simply because you chose it to. You can reverse things and then appending to the end is O(1) and to the beginning is O(n). Which is exactly what I've done by switching the representation! – MaiaVictor Dec 25 '13 at 22:59
  • 1
    @Dokkat Then you're still just appending to the head.. Unless you want to make traversal/querying the head more expensive – jozefg Dec 25 '13 at 23:04
  • @dokkat In that case, you are appending to something by allocating a new cell and populating its predecessor-field with a pointer to the existing list. That is, on the whole, not very useful, since you usually want to traverse a list from its head and you have just turned "find next element" into an O(size-of-RAM) time operation (so, constant, but with a rather scary multiplier). Unless you are proposing double-linked lists, of course... – Vatine Dec 26 '13 at 10:12
3

As I mentioned in a comment in your previous question, if you want immutable linked lists, a straightforward implementation using cons cells can only have either a forward (next) pointer or a backward (previous) pointer, not both. In other words, they're singly-linked lists.

That means that if you want to represent (1 2 3) using (cons 3 (cons 2 (cons 1 '()))), your variable would point to the "last" node (containing the 3), and you'd traverse "backwards" to get to the 2, then the 1. Using this system, it would be impossible to access the 2 node from the 1 node, so you cannot easily traverse the list in the (1 2 3) order.

  • That makes sense, but why would the ability to transverse in that order matter when you're not having side effects anyway? I mean, you can implement most recursive functional algorithms such as map and fold "backwards". They'd still return the same result and have the same complexity. – MaiaVictor Dec 25 '13 at 23:03
  • @Dokkat map and fold have to visit every element of the list no matter what (not accounting for coroutines) this is why forwards or backwards they're still O(n), the difference is that to append an element in front of the last appended element it's O(1) and to append an element in front of the first appended element it's O(n), call the first appended element whatever you want but reaching it still requires iterating through all other elements unless you use a doubly linked list, amortized, or mutable structures – Jimmy Hoffa Dec 26 '13 at 16:24
  • You don't understand what I mean. I'm just saying that even if you reverse the order, you can still implement foldl with the same time complexity. I've learned it is just a matter of convention (which side is "front") - the structure I'm proposing is actually the same. – MaiaVictor Dec 27 '13 at 1:30
0

We use the first method because it produces the correct list. The second produces a reversed list. The nil very clearly shows which element must be the last.

The order matters!

See this trivial example in Common Lisp:

(reduce #'expt (cons 1 (cons 2 (cons 3 nil))))
1
(reduce #'expt (cons 3 (cons 2 (cons 1 nil))))
9

You could use the second method if you have the language's implementation to handle the reversed order under the hood, but then:

  1. the implementation would be more complicated (= more opportunity for bugs)
  2. performance would be affected as mentioned in other answers (some cases, such as full traversals, could have the performance hit mitigated by using more memory, i.e. creating a copy of the list in the correct direction behind the scenes then doing the work on that copy. That's still making two traversals where just one would have been sufficient before.)
  3. unreliable humans would have to remember to build their lists backwards.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.