Haskell: accessing lists from back

问题:

Today I started learning Haskell. I'm kind of new with functional languages, and I'm enjoying Haskell a lot.

However I've got a question about its design which is bugging me: from what I understood so far it looks like accessing an element to the back of a list is a lot more complicated that accessing the element to the front (something like xs:x where xs::[a] and x::a doesn't seem to be possible).

(From what I understood) it's possible to append a list to another one (xs++[a]), but it'll cost more at run time (it requires to traverse the whole list) and it cannot be used for pattern matching.

Why is Haskell missing such operation?

回答1:

The list datatype

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

is defined like above. There's only two patterns you can match: [] and x : xs, where x is the head and xs is the tail.

Prepending to a list

a = 1 : 2 : []
b = 0 : a

 (:) <-- b
 / \  
0  (:)  <-- a
   / \
  1  (:)
     / \
    2   []

simply adds a new cons cell and reuses the original list as the tail.

However, keep in mind that Haskell data structures are immutable. Appending to the tail of a list

a = 1 : 2 : []
b = a ++ [3]

 (:) <-- a      (:) <-- b
 / \            / \
1  (:)         1  (:)
   / \            / \
  2   []         2  (:)
                    / \
                   3   []

requires building an entirely new list, because no part of the original structure can be reused.

In fact, consider

a = 0 : a
b = 0 : [ x+1 | x <- b ]

 (:) <-- a         (:) <-- b
 / \               / \
0  (:) <-- a      0  (:) <-- [ x+1 | x <- b ]
   / \               / \
  0  (:) <-- a      1  (:) <-- [ x+1 | x <- [ x+1 | x <- b ] ]
     ...               ...

How would you ever get the last element of the list, or append to the end?

There are other data structures such as dequeues which are more suited for both front- and back-based access.

回答2:

The list data type in Haskell is a linked list, so a lookup uses O(n) time. If you need frequent access to the back of a list you might want to take a look at Data.Sequence which has O(1) add to beginning and end.

To answer why Haskell uses this data structure as a "standard container" (like C and arrays), it's because Haskell is a pure functional language, and therefore has a preference to purely functional data structures (immutable and persistent.) For further reading look at this wiki page. To use non-functional data structures in Haskell would require it to be inside the IO or ST monad.

回答3:

It is the problem with pure List data structure, not with haskell itself. You can read Purely Functional Data Structures paper to learn more about other pure data structures, that can have better performance on such operations

回答4:

Don't be affraid to reverse() your list whenever you need. It's not uncommon to reverse a list before giving it to a recursive function, or to reverse the final result of a fold().

回答5:

These aren't issues with the language, just the List data type, which has some special syntax but is otherwise not exactly an "integral part of Haskell". You have the same issue in C with singly linked lists but that's obviously not an issue of the C programming language.

If you want a doubly linked list with tail pointer then make such a data type and use that! You might want to learn more data types (see the containers package, vector, and the dlist package for examples).