Purely functional set

Question

Is there an algorithm that implements a purely functional set?

Expected operations would be union, intersection, difference, element?, empty? and adjoin.

Those are not hard requirements though and I would be happy to learn an algorithm that only implements a subset of them.

Answer 1

The links from the answer by @ninjagecko are good. What I've been following recently are the Persistent Data Structures used in Clojure, which are functional, immutable and persistent.

A description of the implementation of the persistent hash map can be found in this two-part blog post:

http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice/

http://blog.higher-order.net/2010/08/16/assoc-and-clojures-persistenthashmap-part-ii/

These are implementations of some of the ideas (see the first answer, first entry) found in this reference request question.

The sets that come out of these structures support the functions you need:

http://clojure.org/data_structures#Data Structures-Sets

All that's left is to browse the source code and try to wrap your head around it.

Answer 2

You can use a purely functional map implementation, where you just ignore the values.

See http://hackage.haskell.org/packages/archive/containers/0.1.0.1/doc/html/Data-IntMap.html (linked to from https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki ).

(sidenote: For more information on functional datastructures, see http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 )

Answer 3

A purely functional implementation exists for almost any data structure. In the case of sets or maps, you typically use some form of search tree, e.g. red/black trees or AVL trees. The standard reference for functional data structures is the book by Okasaki:

http://www.cambridge.org/gb/knowledge/isbn/item1161740/

Significant parts of it are available for free via his thesis:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Answer 4

Here is an implementation of a purely functional set in OCaml (it is the standard library of OCaml).

Answer 5

Is there an algorithm that implements a purely functional set?

You can implement set operations using many different purely functional data structures. Some have better complexity than others.

Examples include:

Lists

Where we have:

List Difference:

(\\) :: Eq a => [a] -> [a] -> [a]

The \\ function is list difference ((non-associative). In the result of xs \\ ys, the first occurrence of each element of ys in turn (if any) has been removed from xs. Thus

union :: Eq a => [a] -> [a] -> [a]

The union function returns the list union of the two lists. For example,

"dog" `union` "cow" == "dogcw"

Duplicates, and elements of the first list, are removed from the the second list, but if the first list contains duplicates, so will the result. It is a special case of unionBy, which allows the programmer to supply their own equality test.

intersect :: Eq a => [a] -> [a] -> [a]

The intersect function takes the list intersection of two lists. For example,

[1,2,3,4] `intersect` [2,4,6,8] == [2,4]

If the first list contains duplicates, so will the result.

Immutable Sets

More efficient data structures can be designed to improve the complexity of set operations. For example, the standard Data.Set library in Haskell implements sets as size-balanced binary trees:

• Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.

Which is this data structure:

data Set a    = Bin !Size !a !(Set a) !(Set a)
              | Tip

type Size     = Int

Yielding complexity of:

• union, intersection, difference: O(n+m)