7.2 パターンマッチングを用いたデータ構造の利用
問 7.5
2分木に対する以下の各関数を定義せよ．
-
1.
ノードの総数を求める関数 nodes．
-
2.
型が int tree である木を対象とし， ノードの値の総和を求める関数 sumTree．
-
3.
引数で与えられた関数を木の各ノードのデータに適用して得られる新しい 木を作る関数mapTree．
-
4.
string tree 型データを，前節で解説した post-order表現，およびin-order表現に変換する以下の各関数．
toPostOrder : string tree -> string toInOrder : string tree -> string
文字列の形式は，以前同様とする．
解答例
fun nodes Empty = 0
| nodes (Node(_, L, R)) = 1 + nodes L + nodes R
fun sumTree Empty = 0
| sumTree (Node(n, L, R)) = n + sumTree L + sumTree R
fun mapTree f Empty = Empty
| mapTree f (Node(x, L, R)) = Node(f x, mapTree f L, mapTree f R)
fun toPostOrder Empty = ""
| toPostOrder (Node(a,b,c)) =
"(" ^ toPostOrder b ^ ")"
^ "(" ^ toPostOrder c ^ ")"
^ a
fun toInOrder Empty = ""
| toInOrder (Node(a,b,c)) =
"(" ^ toInOrder b ^ ")"
^ a
^ "(" ^ toInOrder c ^ ")"
問 7.6
本問では string tree型データとpre-order，in-order，post-orderの各文字列表 現との変換処理を，以下の方針に従い，7.1節で定義 した多相型の’a newTree型に一般化することを考える．
-
1.
’a newTree型の文字列表現の生成には， ’a型の文字列表現の生成が必要である． そこで， 木の文字列表現生成関数を， ’a -> string型の関数を引数として取る高階関数とする． 文字列表現からの復元関数も同様に， string -> ’a型の関数を引数として取る高階関数とする．
-
2.
string treeの場合， ‘(’と‘)’がノードの値に含まれないと仮定し， これらを，文字列表現における部分木の区切り記号として用いた． しかし，たとえばint * int型のデータを考えれば明らかなよう に，一般にこの仮定は成立しない． 区切り文字は，可能な限り，種々の文字列表現に現れないものを選ぶ必要がある． ここでは，文字列定数
"\000"と"\001"の2つを利用することとする． さらに，特別な型を処理したい場合に備え， 変数val lp = "\000" val rp = "\001"
を定義し，プログラムではこれらの変数を使用することとする．
-
3.
’a newTreeでは，子ノードが存在しないことを表現する必要が ある． 種々の表現が可能であるが，string treeの場合の関数の再利用性 などを考慮し，子ノードが存在しないことを， string treeの場合の空の木の表現
"()"に対応させ， 文字列"\000\001"で表すことにする．
以上の方針に従い，文字列表現への変換とその逆変換を行う以下の関数を定義せよ．
val newTreeToPreOrder : (’a -> string) -> ’a newTree -> string val newTreeToInOrder : (’a -> string) -> ’a newTree -> string val newTreeToPostOrder : (’a -> string) -> ’a newTree -> string val preOrderToNewTree : (string -> ’a) -> string -> ’a newTree val inOrderToNewTree : (string -> ’a) -> string -> ’a newTree val postOrderToNewTree : (string -> ’a) -> string -> ’a newTree
さらに，int * int型と文字列との変換関数を定義し， (int * int) newTree型に対して，上記の各関数のテストを行え．
解答例
datatype ’a newTree
= Leaf of ’a
| Node of ’a * ’a newTree * ’a newTree
| NodeL of ’a * ’a newTree
| NodeR of ’a * ’a newTree
val lp = "\000"
val rp = "\001"
val LP = #"\000"
val RP = #"\001"
fun searchLP s p =
if substring(s,p,1) = lp then p
else searchLP s (p+1)
fun searchRP s p n =
if substring(s,p,1) = lp then searchRP s (p+1) (n+1)
else if substring(s,p,1) = rp then
if n=0 then p else searchRP s (p+1) (n - 1)
else searchRP s (p+1) n
fun decompose s =
let val lp1 = searchLP s 0
val rp1 = searchRP s (lp1+1) 0
val lp2 = searchLP s rp1
val rp2 = searchRP s (lp2+1) 0
in (substring (s,0,lp1),
substring (s,lp1+1,rp1-lp1 -1),
substring (s,lp2+1,rp2 - lp2-1))
end
fun decomposeIn s =
let val lp1 = searchLP s 0
val rp1 = searchRP s (lp1+1) 0
val lp2 = searchLP s rp1
val rp2 = searchRP s (lp2+1) 0
in (substring (s, rp1+1, lp2 - rp1 - 1),
substring (s, lp1+1, rp1 - lp1 -1),
substring (s, lp2+1, rp2 - lp2 - 1))
end
fun decomposePost s =
let val lp1 = searchLP s 0
val rp1 = searchRP s (lp1+1) 0
val lp2 = searchLP s rp1
val rp2 = searchRP s (lp2+1) 0
in (substring (s,rp2+1,size s - rp2 - 1),
substring (s,lp1+1,rp1-lp1 -1),
substring (s,lp2+1,rp2 - lp2-1))
end
fun newTreeToPreOrder toString t =
let
val preOrder = newTreeToPreOrder toString
in
case t of
Leaf v => toString v ^ lp ^ rp ^ lp ^ rp
| Node(v, L, R) => toString v ^ lp ^ preOrder L ^ rp ^ lp ^ preOrder R ^ rp
| NodeL(v, L) => toString v ^ lp ^ preOrder L ^ rp ^ lp ^ rp
| NodeR(v, R) => toString v ^ lp ^ rp ^ lp ^ preOrder R ^ rp
end
fun newTreeToInOrder toString t =
let
val inOrder = newTreeToInOrder toString
in
case t of
Leaf v => lp ^ rp ^ toString v ^ lp ^ rp
| Node(v, L, R) => lp ^ inOrder L ^ rp ^ toString v ^ lp ^ inOrder R ^ rp
| NodeL(v, L) => lp ^ inOrder L ^ rp ^ toString v ^ lp ^ rp
| NodeR(v, R) => lp ^ rp ^ toString v ^ lp ^ inOrder R ^ rp
end
fun newTreeToPostOrder toString t =
let
val postOrder = newTreeToPostOrder toString
in
case t of
Leaf v => lp ^ rp ^ lp ^ rp ^ toString v
| Node(v, L, R) => lp ^ postOrder L ^ rp ^ lp ^ postOrder R ^ rp ^ toString v
| NodeL(v, L) => lp ^ postOrder L ^ rp ^ lp ^ rp ^ toString v
| NodeR(v, R) => lp ^ rp ^ lp ^ postOrder R ^ rp ^ toString v
end
fun toNewTree decomp fromString s =
let
val (root,left,right) = decomp s
val toTree = toNewTree decomp fromString
in
case (left, right) of
("","") => Leaf (fromString root)
| (_, "") => NodeL (fromString root, toTree left)
| ("",_) => NodeR (fromString root, toTree right)
| _ => Node (fromString root, toTree left, toTree right)
end
fun preOrderToNewTree fromString s = toNewTree decompose fromString s
fun inOrderToNewTree fromString s = toNewTree decomposeIn fromString s
fun postOrderToNewTree fromString s = toNewTree decomposePost fromString s
int * int型に対する処理関の定義例。
fun intIntToString (x : int * int) = Dynamic.format x
fun stringToIntInt s =
let
val ss = Substring.full s
val (x,y) = Substring.splitl (fn x => x <> #",") ss
val x = Substring.dropl (fn x => x = #"(") x
val x = Substring.string (Substring.takel Char.isDigit x)
val y = Substring.dropl (fn x => x = #"," orelse Char.isSpace x) y
val y = Substring.string (Substring.takel Char.isDigit y)
val i1 = valOf (Int.fromString x)
val i2 = valOf (Int.fromString y)
in
(i1,i2)
end
fun intIntNewTreeToPreOrder t = newTreeToPreOrder intIntToString t
fun intIntNewTreeToInOrder t = newTreeToInOrder intIntToString t
fun intIntNewTreeToPostOrder t = newTreeToPostOrder intIntToString t
fun preOrderToIntIntNewTree s = preOrderToNewTree stringToIntInt s
fun inOrderToIntIntNewTree s = inOrderToNewTree stringToIntInt s
fun postOrderToIntIntNewTree s = postOrderToNewTree stringToIntInt s
以下は(int * int) newTreeに対するSML#でのテスト例である。
# val T = Node((1,2), Leaf (2,3), NodeR((3,4), Leaf (4,5)));
val T =
Node ((1, 2), Leaf (2, 3), NodeR ((3, 4), Leaf (4, 5))) : (int * int) newTree
# val preOrderOfT = intIntNewTreeToPreOrder T
# val inOrderOfT = intIntNewTreeToInOrder T;
val preOrderOfT =
"(1, 2)\^@(2, 3)\^@\^A\^@\^A\^A\^@(3, 4)\^@\^A\^@(4, 5)\^@\^A\^@\^A\^A\^A"
: string
# val inOrderOfT = intIntNewTreeToInOrder T;
val inOrderOfT =
"\^@\^@\^A(2, 3)\^@\^A\^A(1, 2)\^@\^@\^A(3, 4)\^@\^@\^A(4, 5)\^@\^A\^A\^A"
: string
# val postOrderOfT = intIntNewTreeToPostOrder T;
val postOrderOfT =
"\^@\^@\^A\^@\^A(2, 3)\^A\^@\^@\^A\^@\^@\^A\^@\^A(4, 5)\^A(3, 4)\^A(1, 2)"
: string
# val T1 = preOrderToIntIntNewTree preOrderOfT;
val T1 =
Node ((1, 2), Leaf (2, 3), NodeR ((3, 4), Leaf (4, 5))) : (int * int) newTree
# val T2 = inOrderToIntIntNewTree inOrderOfT;
val T2 =
Node ((1, 2), Leaf (2, 3), NodeR ((3, 4), Leaf (4, 5))) : (int * int) newTree
# val T3 = postOrderToIntIntNewTree postOrderOfT;
val T3 =
Node ((1, 2), Leaf (2, 3), NodeR ((3, 4), Leaf (4, 5))) : (int * int) newTree
問 7.7
リストデータを処理するさまざまな関数は，高階関数 foldr を使って 簡単に定義できた． 2分木に対しても，foldr に対応する高階関数があると便利である． ’a tree を処理する汎用の高階関数 treeFold を書いてみよう．
まず treeFold の取るべき引数を考えてみよう． foldr の場合との対応から，以下の引数が必要であると推定できる．
-
1.
変換の対象とする木 t．
-
2.
木が Empty のときの値 z．
-
3.
左部分木と右部分木をそれぞれ treeFold した結果とノードのデー タから，木 Node(,,) の結果を計算する関数 f．
処理の対象となる木の型を ’a tree とし，結果の型を ’b とす る． すると引数 z の型は ’b であるはずである． 変換関数 f は，木構成子 Node の型と対応させて，’a * ’b * ’b -> ’b の型を持つ関数と定義すると，treeFold を使って種々 の木変換関数を定義する上で都合がよい． 以上より treeFold は以下のような関数として定義できる．
# fun treeFold f z Empty = z
| treeFold f z (Node (x, L, R)) =
...
val treeFold = fn : (’a * ’b * ’b -> ’b) -> ’b -> ’a tree -> ’b
-
1.
treeFold の定義を完成せよ．
-
2.
前節で定義した各関数を treeFold を使って定義せよ．
解答例 treeFoldの定義例は以下の通り。
fun treeFold f z Empty = z
| treeFold f z (Node(a,b,c)) = f (a,treeFold f z b,treeFold f z c);
上記の各関数は、treeFoldを使って以下の通り定義できる。
fun nodes t = treeFold (fn (x,y,z) => 1 + y + z) 0 t
fun sumTree t = treeFold (fn (x,y,z) => x + y + z) 0 t
fun mapTree f t = treeFold (fn (x,y,z) => Node(f x, y, z)) Empty t
fun toPostOrder t =
treeFold
(fn (x,L,R) => "(" ^ L ^ ")" ^ "(" ^ R ^ ")" ^ x)
""
t
fun toInOrder t =
treeFold
(fn (x,L,R) => "(" ^ L ^ ")" ^ x ^ "(" ^ R ^ ")")
""
t