6

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?

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

2 Answers 2

Reset to default
18

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.

Improve this answer
9
  • 4
    Okasaki is a must read for serious FP programmers.
    – daniel gratzer
    Dec 25, 2013 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, 2013 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.
    – C. K. Young
    Dec 25, 2013 at 22:38
  • 2
    confused by the part about not seeing stacks, a cons list basically is a stack
    – jk.
    Jan 6, 2014 at 13:31
  • 1
    @Akito: Link updated.
    – Robert Harvey
    May 15, 2022 at 16:58
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.

Improve this answer
2
  • I'm pretty sure queues are identical to queues ;)
    – jk.
    Jan 6, 2014 at 17:55
  • Doh! Typo corrected.
    – itsbruce
    Jan 6, 2014 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.