To close the chapter on Okasaki's Random Access Lists, I must record that there is an errata on the bottom of page 145 of his Purely Functional Data Structures. The argument to the recursive call to `update`

it must read `Zero (update (`

. It took me a while to figure it out, thinking that I had made a mistake.`i` div 2, `p`, `ps`)) **end**

For completeness, here's the translation for the chapter's pseudo-SML into *functional*, typesafe OCaml:

module Vec : sig type 'a t val nil : 'a t val cons : 'a -> 'a t -> 'a t val head : 'a t -> 'a val tail : 'a t -> 'a t val length : 'a t -> int val index : int -> 'a t -> 'a val update : int -> 'a -> 'a t -> 'a t end = struct type 'a t = Nil | Zero of ('a * 'a) t | One of 'a * ('a * 'a) t let nil = Nil type cons = { cons : 'a . 'a -> 'a t -> 'a t } let cons = let rec cons = { cons = fun x l -> match l with | Nil -> One (x, Nil) | Zero ps -> One (x, ps) | One (y, ps) -> Zero (cons.cons (x, y) ps) } in cons.cons type uncons = { uncons : 'a . 'a t -> 'a * 'a t } let uncons = let rec uncons = { uncons = function | Nil -> failwith "uncons" | One (x, Nil) -> (x, Nil) | One (x, ps ) -> (x, Zero ps) | Zero ps -> let ((x, y), ps) = uncons.uncons ps in (x, One (y, ps)) } in uncons.uncons let head l = fst (uncons l) and tail l = snd (uncons l) type length = { length : 'a . 'a t -> int } let length v = let rec length = { length = function | Nil -> 0 | One (_, ps) -> 1 + length.length (Zero ps) | Zero ps -> 2 * length.length ps } in length.length v type index = { index : 'a . int -> 'a t -> 'a } let index n = let rec index = { index = fun n l -> match l with | Nil -> failwith "index" | One (x, ps) when n = 0 -> x | One (x, ps) -> index.index (n - 1) (Zero ps) | Zero ps -> let (l, r) = index.index (n / 2) ps in if n mod 2 = 0 then l else r } in index.index n type update = { update : 'a . int -> ('a -> 'a) -> 'a t -> 'a t } let update n e = let rec update = { update = fun n f l -> match l with | Nil -> failwith "update" | One (x, ps) when n = 0 -> One (f x, ps) | One (x, ps) -> cons x (update.update (pred n) f (Zero ps)) | Zero ps -> let g (x, y) = if n mod 2 = 0 then (f x, y) else (x, f y) in Zero (update.update (n / 2) g ps) } in update.update n (fun _ -> e) end

Enjoy!

## 3 comments:

Thanks, that's a nice nested datatype full-featured example.

Does a fast

appendexist or just the naive one ?As i understand it the

skewBinaryListallows a fastappendyet it's not a nested datatype. I guess your module is exactly whatMike Furrmentions as the missing array module inOCaml-Reins.OCaml-Reinsis so much inspired byOkasakithat i would describe it asOkasakifor OCaml.I guess (I haven't tried) that you could write a O(log n) append by emulating a full adder.

The problem with this datatype is that both

consandunconsare O(log n) worst-case. Skew binary random-access lists have two advantages: O(1)consanduncons, and no special type discipline required to implement the datatype.As it is, this is just to (1) record the erratum I found in the book, and (2) as a simple example of how to encode structural polymorphism, perhaps to implement more advanced data structures (I'll see how far I can get with regular quadtrees).

I have some more comments, sorry for the late reply.

1) no special type discipline is required to implement this datatype, nested datatypes allow to statically enforce some invariants, i don't think they really contribute in the performance department.

type 'a tree =

| Leaf of 'a

| Node of 'a tree * 'a tree

type 'a seq =

| Nil

| Zero of 'a seq

| One of 'a tree * 'a seq

let cons x l =

let rec loop x = function

| Nil -> One (x,Nil)

| Zero ps -> One (x,ps)

| One (y,ps) -> Zero (loop (Node(x,y)) ps)

in loop (Leaf x) l

2) i have implemented the full adder operation as you suggested. the motivation is that if i provide a

foldthen a slowunconsis no longer such a big deal, and the slowconscould be compensated by a fastappendplus anunfold.let rec add a b carry =

match carry with

| None ->

( match a,b with

| _,Nil -> a

| Nil,_ -> b

| One(x,p),Zero q | Zero p,One(x,q) -> One(x,add p q None)

| Zero p,Zero q -> Zero(add p q None)

| One(x,p),One(y,q) -> Zero(add p q (Some(Node(x,y)))) )

| Some c ->

( match a,b with

| Nil,Nil -> One(c,Nil)

| Zero p,Nil | Nil,Zero p -> One(c,p)

| One(x,p),Nil | Nil,One(x,p) -> Zero(add p Nil (Some(Node(x,c))))

| One(x,p),Zero q | Zero p,One(x,q) -> Zero(add p q (Some(Node(x,c))))

| Zero p,Zero q -> One(c,add p q None)

| One(x,p),One(y,q) -> One(c,add p q (Some(Node(x,y)))) )

let merge a b = add a b None

unfortunately, as the name suggests, my

mergeoperation is not what expected, all the items are chained but they are not in theappendorder.Post a Comment