Lately I’ve taken a closer look at Julien’s F# implementations of Chris Okasaki’s Purely Functional Data Structures1.
AltBinaryRandomAccessList2 caught my eye because judging from its existing
update function it looked pretty simple to implement a
remove function. As you may have noticed in all the major collections of F# data structures –FSharp.Core.Collections, FSharpx.core.DataStructures, and PowerPack —
remove is pretty rare. And both
remove seem to be neglected stepchildren in the purely functional data structure world. (By
remove I am referring to functions updating and removing any element by index.)
Let’s look at Okasaki’s “pseudo-canonical”3 update for
list, implemented in F#.
let rec loop i y (l:'a list) =
match (i,y,l) with
| i',y, -> raise (System.Exception("subscript"))
| 0,y',x::xs -> y::xs
| i',y,x::xs -> x::(loop (i'-1) y xs)
Do you see the problem? I’ll get back to it below.
How else might we implement update? We could just punt by converting to
Array, updating, and back to
let punt i y (l:’a list) =
let a = List.toArray l
a.[i] <- y
And our last candidate is a hybrid, in which we progressively take the
tail, collecting each
head in an
Array, until we pass the element for update. Then
cons the new element and the elements from the
let hybrid i y (l:'a list) =
if (i = 0) then List.Cons (y, (List.tail l))
let rec loop i' (front:'a array) back =
match i' with
| x when x < 0 -> front, (List.tail back)
| x ->
Array.set front x (List.head back)
loop (x-1) front (List.tail back)
let front', back' = loop (i - 1) (Array.create i y) l
let rec loop2 i' frontLen (front'':'a array) back'' =
match i' with
| x when x > frontLen -> back''
| x -> loop2 (x + 1) frontLen front'' (front''.[x]::back'')
loop2 0 ((Seq.length front') - 1) front' (y::back')
AltBinaryRandomAccessList is a structure with the same basic functions as
List, but optimized for
update. Here’s the type structure:
type AltBinRndAccList<'a> =
| Zero of AltBinRndAccList<'a * 'a>
| One of 'a * AltBinRndAccList<'a * 'a>
The element grouping represents the binary number of the count of elements, with least significant digit to the left4. This allows for a member update function which runs in O(log n) time. (The best we have seen so far is O(i), where i is the index of the target element, and punt runs in O(n)).
static member fupdate : ('a -> 'a) * int * AltBinRndAccList<'a> -> AltBinRndAccList<'a> = function
| f, i, Nil -> raise Subscript
| f, 0, One(x, ps) -> One(f x, ps)
| f, i, One (x, ps) -> AltBinRndAccList.cons x (AltBinRndAccList.fupdate (f, i-1, Zero ps))
| f, i, Zero ps ->
let f' (x, y) = if i % 2= 0 then f x, y else x, f y
Zero(AltBinRndAccList.fupdate(f', i/2, ps))
Now lets look at actual performance for our
|Size||10k Random Updates||One-time Worst Case|
By way of comparison
Array, which is not a purely functional structure, performs 10,000 updates in 0.1 millisecond at all scales, and really has no “worst case” single update. And notice because its function is not tail recursive Pseudo-Canonical eventually took a stack overflow. Also of interest, starting at the scale of 1,000 elements Punt outperforms Pseudo-Canonical in random updates, even though it is O(n) and the latter O(i). Time complexity does not tell the whole performance story.
So where does this leave
remove? As it turns out my original idea to modify the
AltBinaryRandomAccessList resulted with a function that was not tail recursive, but applying the hybrid technique to it resulted in a satisfactory algorithm6 and marginally improved performance, but like most every
remove implemented in a purely functional list-like structure, the best time complexity you are going to get is O(i). (With a double-ended queue you can achieve ~O(i/2) .)
Here’s the comparative summary of
remove performance on list-like structures. This time I include
Array, where I copy the retained elements into a new structure one element shorter.
|Size||10k Random Deletes||One-time Worst Case|
As you can see,
remove is a viable function for moderate-sized data structures, but suffers from the limitation of its time complexity as you scale up. You could easily modify
remove functions to process an ordered list or range of indexes and still have O(max i) performance.
One remaining question for purists: are the stepchildren still Purely Functional when they use mutation inside a function?
1 Okasaki, Purely Functional Data Structures, 1998
3 Okasaki, 1998.
4 See Okasaki, 1998 or Okasaki, Purely Functional Data Structures, 1996 for in depth discussion of numerical representations of data structures.
5 Times were taken on a not particularly fast dual core 64-bit system. Time multiples were calculated at a finer granularity, and so may not perfectly match the timings in milliseconds.
AltBinaryRandomAccessList is abbreviated to “RndAcc”.
6 I hope to release it soon in an open source library.