# Purely Functional Data Structures

## Chris Okasaki

Language: English

Pages: 232

ISBN: 0521663504

Format: PDF / Kindle (mobi) / ePub

Most books on data structures assume an imperative language such as C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures from the point of view of functional languages, with examples, and presents design techniques that allow programmers to develop their own functional data structures. The author includes both classical data structures, such as red-black trees and binomial queues, and a host of new data structures developed exclusively for functional languages. All source code is given in Standard ML and Haskell, and most of the programs are easily adaptable to other functional languages. This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study.

merge (T (x, []), h) fun mergePairs [] = E | mergePairs [h] = h | mergePairs (hi :: h2 :: hs) = merge (merge (hi, h2), mergePairs hs) fun findMin E = raise EMPTY | findMin (T (x, hs)) = x fun deleteMin E = raise EMPTY | deleteMin (T (x, hs)) = mergePairs hs end Figure 5.6. Pairing heaps. (a) Write a function toBinary that converts pairing heaps from the existing representation into the type datatype BinTree = E' | T of Elem.T x BinTree x BinTree (b) Reimplement pairing heaps using this new

singleton segment. If the smallest existing segment is also a singleton, we merge the two segments and continue merging until the new segment is smaller than the smallest existing segment. This merging is controlled by the bits of the size field. If the lowest bit of size is zero, then we simply cons the new segment onto the segment list. If the lowest bit is one, then we merge the two segments and repeat. Of course, all this is done lazily. fun add (x, (size, segs)) = let fun addSeg (seg, segs,

incremental rotation. First, consider how we might reverse a list in an incremental fashion by keeping two lists and gradually transferring elements from one to the other. datatype a ReverseState = WORKING of a list x a list | DONE of a list fun startReverse xs = WORKING (XS, []) fun exec (WORKING (X :: xs, xs')) = WORKING (XS, X :: xs') | exec (WORKING ([], xs')) = DONE XS' To reverse a list xs, we first create a new state WORKING (XS, []) and then repeatedly call exec until it returns DONE

tree is a complete &-ary tree that contains elements only at the leaves. Definition 9.5 (A -nomial trees) A ft-nomial tree of rank r is a node with k â€” 1 children of each rank from r â€” 1 to 0. Alternatively, a Ar-nomial tree of rank r > 0 is a &-nomial tree of rank râ€” 1 to which kâ€”1 other ^-nomial trees of rank r - 1 have been added as the leftmost children. From the second definition, it is easy to see that a &-nomial tree of rank r contains kr nodes. Definition 9.6 (&-ary pennants) A &-ary

that f is non-empty. If both f and m are empty, then the entire queue is empty. Otherwise, if f is empty we remove the first suspension from m, force it, and install the resulting list as the new f. fun checkF (lenfm, [], E, lenr, r) = E | checkF (lenfm, [], m, lenr, r) = Q (lenfm, force (head m), tail m, lenr, r) | checkF q = Qq fun checkQ (q as (lenfm, f, m, lenr, r)) = if lenr < lenfm then checkF q else checkF (lenfm+lenr, f, snoc (m, $rev r), 0, []) f A slightly more efficient alternative