5

Most functional programming languages such as Scheme and Haskell use lists as their main data structure. Queues are identical to lists, except for the fact appending to the end - not to the begin - has constant time. Every algorithm that is written elegantly using lists with head and tail can be written elegantly using queues with init and last.

Considering appending to the end is more common than the opposite, I'd guess queues are more natural than lists. Is there any reason lists have always been preferred?

  • 4
    Which queue? Persistent queues with O(1) operations exist, but they're rather complicated and have high constant factors AFAIK. – user7043 Dec 25 '13 at 19:51
17

Queues don't functionally compose, and are difficult to implement in a well-performing way without making them mutable.

The very nature of a queue suggests that you put things into it and take things out of it, which is at odds with the immutable nature of functional languages. Oh, sure, you can do the same thing with lists, but generally what you are really doing is composing a new list, not adding to one, and a list doesn't have the special requirement of forcing you to put items into one end and take them out of the other, like a queue does.

All that said, have a look at Okasaki's paper on Purely Functional Data Structures, which does outline a strategy for creating a queue with adequate performance in a functional way.

  • 4
    Okasaki is a must read for serious FP programmers. – Daniel Gratzer Dec 25 '13 at 21:18
  • It seems like you know what you are talking about, but I can't grasp it. Before going further, let me check if you understood what I said, because I've found a better way to express it. I'm asking why it is (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 naturally, the second is the one which reduces in the right order. It seems more natural to construct a list starting with nil and adding elements to it, not the opposite. I've found the latter has properties such as being very curry friendly. – MaiaVictor Dec 25 '13 at 22:10
  • @Dokkat Suppose you have a list (1 2 3) that is represented by (cons 3 (cons 2 (cons 1 '()))). That would mean that your variable would be a pointer to the last node of the list, and each node has a pointer to the "previous" node. Is that what you want? Note that in order to preserve structural induction, the lists are singly linked, by design. That means that the pointers only go one way, not both. – Chris Jester-Young Dec 25 '13 at 22:38
  • @ChrisJester-Young exactly, that is what I want. But my argument about that being natural is somewhat nonsensical, as someone pointed on the other thread: the usual way is, too, curry-friendly and does start with nil and constructs a list from it. – MaiaVictor Dec 25 '13 at 23:18
  • 2
    confused by the part about not seeing stacks, a cons list basically is a stack – jk. Jan 6 '14 at 13:31
2

Queues are identical to lists, except for the fact appending to the end - not to the begin - has constant time.

Queues are commonly understood to be FIFO structures, which are not "identical to lists apart from appending to the end". With queues, you typically write to the tail and read from the head; this is an entirely different semantic.

If you mean a LIFO structure, then you're really talking about a stack, which is how Lists are most commonly used in recursive/functional code. In which case, why do you care that we call the location that we read from and write to the head or the tail? The way of working with it would be the same either way. The only context in which it would make a difference is where the list is also being used as a string (a rather mundane concern).

Lists/stacks are very useful structures in functional programming:

  1. The head can represent the state of a computation.
  2. The structure is persistent, minimizing copying while preserving immutability.
  3. head and tail access in constant time with a much simpler structure than any indexed type (simpler underlying code etc).

Queues lose some of these benefits (e.g. persistence) and add complexity to no gain. If the main benefit is that you find queues easier to understand, try harder.

  • I'm pretty sure queues are identical to queues ;) – jk. Jan 6 '14 at 17:55
  • Doh! Typo corrected. – itsbruce Jan 6 '14 at 17:56

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.