書き換え可能なデータ構造を使ったキュー

いつもの如くまずは型の定義。

# type 'a mlist = MNil | MCons of 'a * 'a mlist ref;;
type 'a mlist = MNil | MCons of 'a * 'a mlist ref
# type 'a queue = {mutable head : 'a mlist; mutable tail : 'a mlist};;
type 'a queue = { mutable head : 'a mlist; mutable tail : 'a mlist; }

キューを作る関数の定義。

# let create () = {head = MNil; tail = MNil};;
val create : unit -> 'a queue = <fun>
# let q : int queue = create ();;
val q : int queue = {head = MNil; tail = MNil}

キューに要素を加える関数の定義。

# let add a = function
    {head = MNil; tail = MNil} as q ->
      let c = MCons (a, ref MNil) in
      q.head <- c; q.tail <- c
  | {tail = MCons (_, next)} as q ->
      let c = MCons (a, ref MNil) in
      next := c; q.tail <- c
  | _ -> failwith "enqueue: input queue broken";;
val add : 'a -> 'a queue -> unit = <fun>
# add 1 q; add 2 q; add 3 q;;
- : unit = ()
# q;;
- : int queue =
{head =
  MCons (1,
   {contents = MCons (2, {contents = MCons (3, {contents = MNil})})});
 tail = MCons (3, {contents = MNil})}

先頭要素を返す関数の定義。

# let peek = function
    {head = MNil; tail = MNil} -> failwith "peek: queue is empty"
  | {head = MCons(a, _)} -> a
  | _ -> failwith "peek: queue is empty";;
val peek : 'a queue -> 'a = <fun>
# peek q;;
- : int = 1

先頭要素を削除し、その要素を返す関数の定義。

# let take = function
    {head = MNil; tail = MNil} -> failwith "take: queue is empty"
  | {head = MCons (a, next)} as q when !next = MNil ->
      q.head <- MNil; q.tail <- MNil; a
  | {head = MCons (a, next)} as q -> q.head <- !next; a
  | _ -> failwith "take: queue is broken";;
val take : 'a queue -> 'a = <fun>