straw poll on F# queue function names

[Jack Fox]

I'm almost ready to release Queue as a FSharpx.Collections immutable data structure. I implemented the common and accepted names for queue operations (peek/enqueue/dequeue), and I'm very dissatisfied with them:

1) enqueue/dequeue...I always have to stop and think what they mean. They both have the root "queue".

2) dequeue...used for 2 different operations: one returns just the tail, and the other returns a tuple of next element and tail. F# doesn't allow overloading of non-static type member or of module functions so combining these operations in a .NET-like way would be difficult (aside from the bad practice of naming different operations the same).

3) Double-ended queue is a different data structure I intend to implement...currently named "Deque" (notice lacking 2nd "ue") after Okasaki's naming standard. Another source of confusion with a "dequeue" action on queue.

Argument for sticking with "Okasaki" naming standard (cons/head/tail/snoc) supplemented by "uncons":

1) List is the most ubiquitous of all functional structures and already sets the standard for cons/head/tail. There are other "list-like" structures (random access list, double-ended queue, vector, difference list, queue, and heap, among others). Why not name functions the same across entire classes of structure rather than ad hoc names for each structure? 

(Admittedly "snoc" is an odd name, but "append" is already taken for some list-like structures by another operation. I can't think of an alternative to "uncons", but I'm open to suggestions.)

I'm open to sticking with "common and accepted" names, but so far the only argument in their favor is they are "common and accepted names", which is usually a sufficient argument, but I think in this case not. 

Looking for suggestions.

[Jerold Haas]

For some of the collections, namely the more "generic," such as the List and DifferenceList, many of the methods _can_ be the same. However, for cases like special collection types like the Queue, Stack, and Heap, one has to consider the nature of how these are to be used: FIFO, FILO, or random access, for example. With those, the "common and accepted" naming conventions make more sense to use to maintain consistency for programmers coming from other languages.

In cases with ambiguities like DEQueue versus Queue.Dequeue(), sometimes it works out well to simply put the specifying portion at the end (QueueDE for "queue, double-ended").

[7sharp9]

You will probably want to implement table like this once you have some samples over the range.  I would be interested in the Deque as I wrote something similar as an alternative to the mutable backed Queue in the MailboxProcessor.

[Jack Fox]

Thanks for pointing out the Wikipedia article, @7sharp9. There are already several immutable Deques in FSharpx.Datastructures. After I'm done with Queues I'll decide on the best candidate Deque and install it in FSharpx.Collections. Same plan for vectors/random access lists, heaps, and other immutable (purely functional) collections.

[Jack Fox]

I've been meaning to write a more coherent exposition on this topic, here it finally is http://jackfoxy.com/semantics-and-list-like-data-structures

[Jason McCampbell]

Two thoughts...

Personally I think your instincts, Jack, are right and my preference is to follow Okasaki's naming conventions as well. 

However, there was also a good discussion on Twitter today about increasing the acceptance and usage of F#. Following Okasaki's naming instead of general convention is endearing to some of us but is yet-another barrier for the much larger numbers of C#, Java, etc developers who might want to make the transition. I would be happy sucking it up and following the herd if it reduces the learning curve and grows the overall community.

Above all, though, what you are doing in compiling the collection is 95+% of the value, whatever the functions are named. Thank you for doing it.

Jason

[Jack Fox]

@7sharp9 pointed me to this reference in Wikipedia, which only makes it harder to "follow the herd". Queue and to a lesser extent Heap have pretty well-known function names, but double-ended queue, random access list, and vector have different function names in different languages. The "herd" is more a herd of cats. I really wanted to find a herd-like name for "snoc" I could use across List-like structures, but I have not found one. (It can't be append, because that name is used by the special case of appending a second structure.) 

But even if I went with the herd names for Queue, I discovered I can't overload the type member of module function for "dequeue". Classic dequeue is two different functions. One returns "tail" and the other returns the tuple of head and tail. So in F# one of those functions gets another name anyway.

I appreciate the argument of F# acceptance. I think even many experienced F# users don't see any purely functional data structures other than list (and maybe map and set) for a long time. So I'm kind of at peace with purely functional data structures being a side-show, even within functional programming.

I've decided to release the remaining 6 List-like structures at the same time, which I hope makes Okasaki naming more palatable.