Binary Random-Access List

OCaml

引き続き、http://www.cs.cmu.edu/~rwh/theses/okasaki.pdfを眺めていますが、今回はBinary Random-Access Listについてメモ。

  • これは完全二分木と二進数を合体させたリストみたい。
  • このリストは二進数のように0か1を持っていて、1の場合はその中に完全二分木を格納できるようになっている。
  • 完全二分木は葉に要素を格納しており、その木が格納できる要素数は以下のように2^k-1個になる。
    • 葉が一つ→1個
    • 枝が一つ & 葉が二つ→2個
    • 枝が三つ & 葉が四つ→4個
    • 以下略
  • 完全二分木の要素数は上記の二進数の値2^k-1と一致するようになっている（後述の例を参照）。
  • このリストの0と1を二進数として評価すると格納されている要素数になる（ということに気がついたけど特にこの特性は利用されていないみたい）。


と、ここまで書いてみたが自分で数ヶ月後に読み返しても全然意味がわからなさそう… まぁPDFの補足的なものとして。


とりあえず具体例をあげると…

  • [a]が格納されている場合（要素数0b1）
    • [1(葉:a)]
  • [a; b]が格納されている場合（要素数0b10）
    • [0; 1(葉:a, b)]
  • [a; b; c]が格納されている場合（要素数0b11）
    • [1(葉:c) ;1(葉:a, b)]
  • [a; b; c; d]が格納されている場合（要素数0b100）
    • [0; 0; 1(葉:a, b, c. d)]
  • [a; b; c; d; e]が格納されている場合（要素数0b101）
    • [1(葉:e); 0; 1(葉:a, b, c, d)]

という感じ。


で、やはりStandardMLのコードが載っていたのでOCamlにしてみた。というか書いて動かしてみてやっと仕組みが分かったという。

module BinaryRList :
  sig
    type 'a tree
    type 'a rlist
    val zero : 'a rlist
    val cons : 'a -> 'a rlist -> 'a rlist
    val borrow : 'a rlist -> 'a tree * 'a rlist
    val head : 'a rlist -> 'a
    val tail : 'a rlist -> 'a rlist
    val lookup : 'a rlist -> int -> 'a
  end
=
  struct
    type 'a tree = Leaf of 'a | Node of int * 'a tree * 'a tree
    type 'a digit = Zero | One of 'a tree
    type 'a rlist = 'a digit list

    let zero = [Zero]

    let size = function Leaf _ -> 1 | Node (sz, _, _) -> sz

    let cons x rl =
      let link t1 t2 =
        Node (size t1 + size t2, t1, t2)
      in
      let rec inc t rl =
        match rl with
        | [] -> [One t]
        | Zero::rest -> One t::rest
        | One t1::rest -> Zero::inc (link t t1) rest
      in
      inc (Leaf x) rl

    let rec borrow = function
      | [One t] -> t, []
      | One t::rest -> t, Zero::rest
      | Zero::rest -> (
        match borrow rest with
        | Node (_, t1, t2), rest -> t1, One t2::rest
        | _ -> failwith "It can't decrese any more."
      )
      | _ -> failwith "It can't decrese any more."

    let head rl =
      match (borrow rl) with
      | Leaf x, _ -> x
      | _ -> failwith "It should be Leaf."

    let tail rl =
      match (borrow rl) with
      | _, rest -> rest

    let rec lookup rl i =
      let rec lookup_tree t i =
        match t with
        | Leaf x -> x
        | Node (w, t1, t2) ->
          if i < w / 2 then lookup_tree t1 i
          else lookup_tree t2 (i - w / 2)
      in
      match rl with
      | Zero::rest -> lookup rest i
      | One t::rest ->
        if i < size t then lookup_tree t i
        else lookup rest (i - size t)
      | [] -> failwith "Empty list."
  end

(* main *)
let l = [100; 101; 102; 103; 104; 105; 106; 107; 108; 109]
let rl = List.fold_left (fun rl x -> BinaryRList.cons x rl) BinaryRList.zero l
let head_of_rl = BinaryRList.head rl
let tail_of_rl = BinaryRList.tail rl
let the_2nd_elm_of_rl = BinaryRList.lookup rl (2 - 1)
let the_5th_elm_of_rl = BinaryRList.lookup rl (5 - 1)
let the_8th_elm_of_rl = BinaryRList.lookup rl (8 - 1)

これの結果はこちら。

komamitsu@potato:~/lab/ocaml/binary_ramdam_access_list$ ocaml 
        Objective Caml version 3.10.2

# #use "binary_random_access_list.ml";;
module BinaryRList :
  sig
    type 'a tree
    type 'a rlist
    val zero : 'a rlist
    val cons : 'a -> 'a rlist -> 'a rlist
    val borrow : 'a rlist -> 'a tree * 'a rlist
    val head : 'a rlist -> 'a
    val tail : 'a rlist -> 'a rlist
    val lookup : 'a rlist -> int -> 'a
  end
val l : int list = [100; 101; 102; 103; 104; 105; 106; 107; 108; 109]
val rl : int BinaryRList.rlist = <abstr>
val head_of_rl : int = 109
val tail_of_rl : int BinaryRList.rlist = <abstr>
val the_2nd_elm_of_rl : int = 108
val the_5th_elm_of_rl : int = 105
val the_8th_elm_of_rl : int = 102
#

本来 type 'a treeのNodeが保持しているサイズ（int）は不要なのだけど、実装の都合上持たせているらしい。

あと、cons, head, tailはO(1)。ランダムアクセスであるlookupはO(log n)。