SML: How to append an element to a list in SML?

Question

Is there an operator in SML which allows me to append to a list without having to create a new list? For example

I cant do this:

 [1,2,3]::1

but I can do this:

 [1,2,3]@[1]

which is odd as I have to create a list with 1 in it. Is there a better way of doing this?

Answer 1

You have to create a list with a one in it either way. The tail of the tail of the tail of [1,2,3,1] is [1]. So if you have [1,2,3,1] in memory, you also have [1] somewhere in memory.

So even if there were operator like [1,2,3] @:: 1, it wouldn't make a difference since it still needs to create a list with a one in it.

PS: The real issue with xs @ [x] isn't the creation of the list, but the fact that its runtime is in O(n) (as opposed to x :: xs, which is in O(1)). This is also an issue inherent in the nature of immutable singly linked lists and thus can't be helped, but it's why you generally should avoid appending to the end of a list like that.

Answer 2

[1,2,3]::1 tries to append the int list [1,2,3] into the integer value 1, which is not possible as an integer cannot be appended to.
1::[1,2,3] however, is completely valid as the list [1,2,3] supports the appending operation. The evaluation rules for :: require t1 :: t1 list, where t1 is a value from type 1, and t1 list is a list of type 1, what you're doing is t1 list :: t1.
[1,2,3] @ [1] is valid because you're appending a list into a list.