Haskell: What's the underlying data structure for list?

Question

If it's linked list, why doesn't it support push_back?

If it's simply array, why does it need linear time when accessed by subscript?

Appreciated for your help.

---

Edit: We can append element in front of a list like this 1:[2,3], that's push_front; but we can't do it this way: [2,3]:4, that's push_back.

ps. actually I borrow push_front/back from C++'s STL

Answer 1

Since the question asks about the "underlying implementation":

The list type is (conceptually) defined like this:

data [a] = [] | a:[a]

You can't actually write this declaration, because lists have funky syntax. But you can make exactly the same kind of thing yourself

data List a = Nil | a :* List a
infixr 5 :*

When you write something like [1,2,3], that's just special syntax for 1:2:3:[]. Since : associates to the right, this really means 1:(2:(3:[])). The functions on lists are all, fundamentally, based on pattern matching, which deals with just one constructor at a time. You may have to open up a lot of : constructors to get to the end of a list, and then build a bunch of : constructors to put together a new version with an extra element at the end. Any functions (like ++) that you may use will end up going through this sort of process internally.

Answer 2

If by push_back you mean adding an element to the end, of course it "supports" it. To add an element x to a list list (and get a new list so constructed), use the expression list ++ [x].

Beware though, that this is an O(n) operation, n being the length of list.

That's because it is a singly linked list. It also answers your other question about subscript.

Answer 3

Haskell list are singly linked list. It supports appending to the end of the list, but it has to traverse the entire list for this operation.:

λ> let x = [1,2,3]
λ> x ++ [4]
[1,2,3,4]