Q:

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

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

A:

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]

A:

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.

