「二分木のドット付き文字列表現」（中級）:OCaml演習 -60問目-

　二分木についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約十分でした。

問題 60.

　相互に識別可能な英小文字を値とする節からなる二分木は、行きがけ順に集められた節の文字と、空の部分木を表すドット「.」とからなる文字列で表現することができる。
 　例えば、上図の二分木は、次のドット文字列で表現される。

abd..e..c.fg...

イ）ドット付き文字列のバッカス標準形または構文図式を書け。
ロ）二分木とドット付き文字列とを相互に変換する関数tree_dotstringを書け。差分リストを用いること。

定義と用語

行きがけ順：親、左部分木、右部分木の順
差分リスト：リストの表現であって、そのリストを他のリストの前方（左）に連接する関数で表した表現

答案

本問の解き方

イ）について
　構文図式は、図なのでバッカス標準形よりも読み易いのですが、その分だけ書くのに手間がかかります。
　なので、バッカス標準形を選ぶことにしました。バッカス標準形は、二分木の定義をそのままドット付き文字列で書き直すだけです。

ロ）について
　二分木からドット付き文字列を生成する関数と、その逆にドット付き文字列から二分木を生成する関数を作成し、それらをヴァリアントにより一つの関数に纏めます。

 　なお、出題者により使用を指定された「差分リスト」は、ドット付き文字列を生成する関数内で使っています。本答案の算法では、無駄に計算量が増えるだけで、何の利点もありません。
　

バッカス標準形

<dotstring> ::= . | <label><dotstring><dotstring>
<label> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

コード

open Binary_tree
open Dlist

(* 文字のリストを二分木に変換する関数 *)
let clist_of_tree empty tr =
	let rec loop = function
		| Empty -> dlist_of [empty]
		| Node (a, l, r) -> (dlist_of [a])@@(loop l)@@(loop r) in
	to_list (loop tr)


(* 二分木を文字のリストに変換する関数 *)
let tree_of_clist empty lst =
	let rec loop = function
		| a::tl when a = empty -> (Empty, tl)
		| a::tl ->
			let (l, tl) = loop tl in
			let (r, tl) = loop tl in
			(Node (a, l, r), tl)
		| _ -> failwith "Invalid argument" in
	let (ret, _) = loop lst in ret

(* 文字列または文字の二分木からなる型の定義 *)
type u = Ustring of string| Ubtree of char Binary_tree.t

let tree_dotstring =
(* 文字のリストを文字列に変換する関数 *)
	let to_string lst = String.init (List.length lst) (List.nth lst) in
(* 文字列を文字のリストに変換する関数 *)
	let to_clist src =
		let len = (String.length src) in
		let rec loop = function
			| i when i < len -> (String.get src i)::(loop (i+1))
			| _ -> [] in
		loop 0 in
	function
		| Ustring a -> Ubtree (tree_of_clist '.' (to_clist a))
		| Ubtree a -> Ustring (to_string (clist_of_tree '.' a))

感想

ドット付き文字列

　例によって、出題者お利口さんが、文字列（string）と文字の列（character sequaence）と文字のリスト（char list）をごっちゃにしており訳が分からないので、答案では全て文字列（string）に統一しました。
　したがって、本記事のドット付き文字列とは、ドットが含まれ得る文字列のことです。

差分リスト

　出題者お利口さんが、「差分リスト、差分リスト」とバカの一つ覚えのように繰り返す理由が知りたかったので、今回ばかりは解答を見てみたら、残念ながら製作中でした。
　一体どのような変態的超絶技巧が繰り出されるのか楽しみにしていたのにがっかりです。
　文章の構成は、しっちゃかめっちゃかでも、プログラミングの腕だけは本物だと信じていたのに、まさか…口だけ…
　いや、そんなはずはありません！きっと本業が忙しいのでしょう。まさか…そんな…ただのイキリだなんて…そんなはずが…

予告

　二分木の問題は今回で終わりです。次回からは、多分、木の問題です。