練習問題 8.9

本文中で示したデキュー関数 dequeue の定義を正しく動作するように修正しなさい。

準備

type 'a mlist = MNil | MCons of 'a * 'a mlist ref;;

type 'a queue = {mutable head : 'a mlist; mutable tail : 'a mlist};;

(* create -- 新しいキューをつくる = 空のキュー *)
let create () = {head = MNil; tail = MNil};;

(* 実行例 *)
let q : int queue = create ();;
q;;

(* add -- 要素を加えるための関数 *)
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";;

add 1 q;;
q;;

(* peek -- 先頭要素を返す関数 *)
let peek = function
    {head = MNil; tail = MNil} -> failwith "ht: queue is empty"
  |{head = MCons(a, _)} -> a
  | _ -> failwith "hd: queue is broken";;

解答

(* dequeue -- 先頭要素を削除して、その先頭要素を返す関数 *)
let dequeue = function
    {head = MNil; tail = MNil} ->failwith "dequeue: queue is empty"
  | {head = MCons(a, next)} as q ->
     if !next == MNil
     then (q.head <- !next; q.tail <- !next)
     else (q.head <- !next);
     a
  | _ -> failwith "dequeue: queue is broken";;

Tweet