二分木と Lisp のリスト
今回は簡単な例題として、Lisp のリストのようなデータ構造を F# で作成してみましょう。
●Lisp のリスト
Lisp のリストは複数の「コンスセル (cons cell)」を連結したものです。ひとつのコンスセルには、データを格納する CAR (カー) という場所と、次のセルを連結する CDR (クダー) という場所からなっています。次の図を見てください。
上図はコンスセルを箱で表しています。左側の CAR がデータを格納する場所で、CDR が次のコンスセルと連結しています。上図の場合、先頭のコンスセルの CAR には 1 が格納され、CDR は次のコンスセルと連結しています。2 番目のコンスセルには CAR に 2 というデータが格納されています。このあとに接続されるコンスセルはもうないので、CDR にはリストの終わりを示す特別なデータ (NIL) が格納されます。このようなリストを Lisp では (1 2) と表記します。F# で記述すると [1; 2] になります。
ここまでは F# のリストとよく似ていますが、Lisp のリストは CAR にリストを格納して、リストを入れ子にすることができます。次の図を見てください。
上図のリストを Lisp で記述すると (1 (2 10 11) (3 12 13)) になります。F# で記述すると [1; [2; 10; 11]; [3; 12; 13]] になりますが、これは要素の型が int と int list で異なるため、F# ではエラーになります。
F# の場合、このような構造は二分木として表すことができます。
リスト : 二分木の定義 type 'a tree = Nil | Leaf of 'a | Cons of 'a tree * 'a tree
木構造はバリアント (判別共用体) を使うと簡単に定義することができます。型名は tree としました。Nil は空の木を表します。Leaf は葉を表していて、要素を格納します。節は Cons で表します。第 1 要素がコンスセルの CAR に、第 2 要素が CDR に対応します。けっきょく、Lisp のリストは線形のリストではなく、F# では二分木として扱うことになります。
それでは実際に試してみましょう。
> type 'a tree = Nil | Leaf of 'a | Cons of 'a tree * 'a tree;;
type 'a tree =
| Nil
| Leaf of 'a
| Cons of 'a tree * 'a tree
> let a = Cons(Leaf 2, Cons(Leaf 10, Cons(Leaf 11, Nil)));;
val a: int tree = Cons (Leaf 2, Cons (Leaf 10, Cons (Leaf 11, Nil)))
> let b = Cons(Leaf 3, Cons(Leaf 12, Cons(Leaf 13, Nil)));;
val b: int tree = Cons (Leaf 3, Cons (Leaf 12, Cons (Leaf 13, Nil)))
> let c = Cons(Leaf 1, Cons(a, Cons(b, Nil)));;
val c: int tree =
Cons
(Leaf 1,
Cons
(Cons (Leaf 2, Cons (Leaf 10, Cons (Leaf 11, Nil))),
Cons (Cons (Leaf 3, Cons (Leaf 12, Cons (Leaf 13, Nil))), Nil)))
表示がごちゃごちゃしていて、このままでは二分木の構造がよくわかりませんね。M.Hiroi は Lisp のカッコに慣れているせいか、(1 (2 10 11) (3 12 13)) と表示したほうがわかりやすいと思います。そこで、まずは最初に二分木 tree を Lisp 風のカッコで表示するプログラムを作ってみましょう。
●リストの表記法
ここで Lisp でのリストの表記法について簡単に説明しておきましょう。コンスセルの CDR は NIL だけではなく他のデータを格納することもできます。Lisp ではリストの終端が NIL 以外のデータの場合、そのリストを次のように表します。
左右のカッコの中間にドット ( . ) を置き、左側に CAR のデータを、右側に CDR のデータを書きます。つまり、リスト (1) は (1 . NIL) と表すことができます。このようなデータを Lisp では「ドット対 (dotted pair)」と呼びます。たとえば、CAR が 1 で CDR が 2 であれば (1 . 2) となります。普通のリストも次のようにドット対を使って表現できます。
(1) ≡ (1 . NIL) (1 2 3) ≡ (1 . (2 . (3 . NIL))) ((1 2) (3 4)) ≡ ((1 . (2 . NIL)) . ((3 . (4 . NIL)) . NIL)) ((1 2) 3 4) ≡ ((1 . (2 . NIL)) . (3 . (4 . NIL)))
それでは、リスト (a b c) の終端を d に変えてみましょう。ドット対を使った表記法では、(a . (b . (c . d))) となりますが、これは (a b c . d) と表すことができます。
このように、NIL 以外のアトムで終端されたリストを Lisp では「ドットリスト (dotted list)」と呼びます。
ドットの後ろは CDR にセットするデータを指定するのですから、複数のデータを書いたり省略してはいけません。次の場合、Lisp ではエラーになります。
( . a) ; CAR がない (a . ) ; CDR がない (a . b c) ; CDR にデータが複数ある (a . . b) ; ドットが複数ある (a . b . c )
●二分木の表示
Lisp のリストのように二分木 tree を表示するプログラムは簡単です。次のリストを見てください。
リスト : 二分木の表示 (バリアント tree に追加)
member this.ToStringSub() =
match this with
Nil -> ""
| Leaf x -> " . " + x.ToString()
| Cons(a, d) -> " " + a.ToString() + d.ToStringSub()
override this.ToString() =
match this with
Nil -> "()"
| Leaf x -> x.ToString()
| Cons(a, d) -> "(" + a.ToString() + d.ToStringSub() + ")"
バリアンド tree でメソッド ToString() をオーバーライドします。this が Nil の場合は文字列 "()" を返します。Leaf x の場合は x のメソッド ToString() を呼び出して文字列に変換します。Cons(a, d) の場合、"(" と ")" で囲み、CAR を ToString() で、CDR を ToStringSub() で文字列に変換します。
ToStringSub() の this は CDR を表します。たとえば、(1) のようなリストの CDR は Nil とマッチングします。この場合、空文字列 "" を返します。(1 . 2) のようなドット対の CDR は Leaf x とマッチングします。" . " と x.ToString() を連結して返します。
(1 2 3) のようなリストの CDR は Cons(a, d) とマッチングします。空白を挿入してから a.ToString() で要素 a を文字列に変換し、残りを d.ToStringSub() で文字列に変換します。
●書式指定子 %O
なお、バリアントの場合、ToString() をオーバーライドしても書式指定子 "%A" や REPL の出力が変わるわけではありません。次の例を見てください。
> type oops = - | Foo - | Bar - override this.ToString() = - match this with - Foo -> "Foo!" - | Bar -> "Bar!!" - ;; type oops = | Foo | Bar override ToString: unit -> string > Foo;; val it: oops = Foo > Bar;; val it: oops = Bar > Foo |> printfn "%A";; Foo val it: unit = () > Bar |> printfn "%A";; Bar val it: unit = () > Foo.ToString();; val it: string = "Foo!" > Bar.ToString();; val it: string = "Bar!!"
ToString は .NET のクラス System.Object のメソッドです。バリアントは F# のデータ型なので、Object (F# の obj) へのアップキャスト (ボックス化) が必要になります。F# のクラスは暗黙のうちに obj を継承するので、%A でも REPL でも問題なく動作します。
このような場合、書式指定子 %O を使うと上手くいきます。%O は引数をボックス化してから ToString() を呼び出します。
> Foo |> printfn "%O";; Foo! val it: unit = () > Bar |> printfn "%O";; Bar!! val it: unit = ()
●REPL の出力をカスタマイズ
REPL の出力は、fsi.AddPrinter を使ってカスタマイズすることができます。
fsi.AddPrinter<型>(fun item -> ...)
> fsi.AddPrinter<oops>(fun x -> x.ToString());; val it: unit = () > Foo;; val it: oops = Foo! > Bar;; val it: oops = Bar!!
ただし、型指定でジェネリックを指定する、たとえば 'a tree と指定すると次のようなワーニングが表示されます。
> fsi.AddPrinter<'a tree>(fun x -> x.ToString());; fsi.AddPrinter<'a tree>(fun x -> x.ToString());; ---------------^^ /home/mhiroi/work/fsharp/stdin(23,16): warning FS0064: このコンストラクトによって、 コードの総称性は型の注釈よりも低くなります。型変数 'a' は型 'obj' に制約されました。 val it: unit = () > Cons(Leaf 1, Nil);; val it: int tree = Cons (Leaf 1, Nil) > Cons(Leaf (box 1), Nil);; val it: obj tree = (1)
これだと要素 ('a) をボックス化しないと上手く表示されないので、とりあえず型を int tree に限定することにします。
簡単な実行例を示します。
> fsi.AddPrinter<int tree>(fun x -> x.ToString());; val it: unit = () > let a: int tree = Nil;; val a: int tree = () > let b = Cons(Leaf 1, Nil);; val b: int tree = (1) > let c = Cons(Leaf 2, b);; val c: int tree = (2 1) > let d = Cons(Leaf 3, c);; val d: int tree = (3 2 1) > let e = Cons(Leaf 4, Leaf 5);; val e: int tree = (4 . 5) > Cons(Leaf 1, Cons(c, Cons(d, Nil)));; val it: int tree = (1 (2 1) (3 2 1))
正常に動作していますね。
●基本的な操作関数
次は述語と基本的な操作関数を作りましょう。
リスト : 述語
let consp = function
Cons(_, _) -> true
| _ -> false
let listp = function
Leaf _ -> false
| _ -> true
let emptyp = function
Nil -> true
| _ -> false
// 等値の判定
let rec equal xs ys =
match (xs, ys) with
(Nil, Nil) -> true
| (Leaf a, Leaf d) -> a = d
| (Cons(a1, d1), Cons(a2, d2)) -> equal a1 a2 && equal d1 d2
| _ -> false
述語 consp は引数がコンスセル (Cons) ならば真を返します。listp は引数がコンスセルまたは空リストならば真を返します。emptyp は引数が空リストならば真を返します。Lisp / Scheme の場合、空リストを判定する述語に null があるのですが、.NET では何も無いことを表す値として null が使われているので、名前を emptyp としました。述語名の最後に p を付けるのは Lisp の慣習です。
述語 equal は 2 つの引数 xs, ys の等値を判定します。xs と ys が Nil の場合は true を返します。Leaf a と Leaf d の場合は a と d を等値演算子 = で比較します。Cons の場合は CAR を equal で比較し、それから CDR を equal で比較します。それ以外の場合は false を返します。
リスト : 基本的な操作関数
let car = function
Cons(a, _) -> a
| _ -> raise ConsRequired
let cdr = function
Cons(_, d) -> d
| _ -> raise ConsRequired
let cons x xs = Cons(Leaf x, xs)
// 長さ
let length xs =
let rec iter xs c =
if consp xs then
iter (cdr xs) (c + 1)
else c
iter xs 0
// 反転
let reverse xs =
let rec iter xs acc =
if consp xs then
Cons(car xs, acc) |> iter (cdr xs)
else acc
iter xs Nil
// 連結
let rec append xs ys =
if consp xs then Cons(car xs, append (cdr xs) ys) else ys
// 生成
let fromList xs =
let rec iter xs acc =
match xs with
[] -> reverse acc
| y::ys -> cons y acc |> iter ys
iter xs Nil
関数 car と cdr はコンスセルの CAR と CDR を返します。引数がコンスセルでなければ例外を送出します。関数 cons は Cons のかわりに使用します。length はトップレベルの要素数を返します。葉の数ではないことに注意してください。reverse はトップレベルの要素を反転します。append は引数 xs と ys をトップレベルで連結した tree を返します。fromList は F# のリストを tree に変換します。
簡単な実行例を示します。
> let a = cons 1 (cons 2 (cons 3 Nil));; val a: int tree = (1 2 3) > car a;; val it: int tree = 1 > cdr a;; val it: int tree = (2 3) > car (cdr a);; val it: int tree = 2 > cdr (cdr a);; val it: int tree = (3) > car (cdr (cdr a));; val it: int tree = 3 > cdr (cdr (cdr a));; val it: int tree = () > consp a;; val it: bool = true > car a |> consp;; val it: bool = false > consp Nil;; val it: bool = false > listp a;; val it: bool = true > listp Nil;; val it: bool = true > car a |> listp;; val it: bool = false > emptyp a;; val it: bool = false > emptyp Nil;; val it: bool = true > car a |> emptyp;; val it: bool = false > length a;; val it: int = 3 > reverse a;; val it: int tree = (3 2 1) > append a (reverse a);; val it: int tree = (1 2 3 3 2 1) > fromList [1..10];; val it: int tree = (1 2 3 4 5 6 7 8 9 10)
●高階関数
次は高階関数を作りましょう。
リスト : 高階関数
type 'a tree =
| Nil
| Leaf of 'a
| Cons of 'a tree * 'a tree
member this.Fst() =
match this with
Cons(Leaf x, _) -> x
| _ -> raise AtomRequired
member this.Snd() =
match this with
Cons(_, Leaf x) -> x
| _ -> raise AtomRequired
・・・略・・・
let rec map fn xs =
if consp xs then
cons (fn (xs.Fst())) (map fn (cdr xs))
else Nil
let rec filter pred xs =
if consp xs then
if pred (xs.Fst()) then Cons(car xs, filter pred (cdr xs))
else filter pred (cdr xs)
else Nil
let rec foldl fn a xs =
if consp xs then
foldl fn (fn a (xs.Fst())) (cdr xs)
else a
let rec foldr fn a xs =
if consp xs then
fn (xs.Fst()) (foldr fn a (cdr xs))
else a
tree の定義にドット対の CAR と CDR から値を取り出すメソッド Fst と Snd を追加します。Fst を用意することで、高階関数を簡単に定義することができます。関数 map はマッピングを行います。引数 xs がコンスセルならば、Fst で値を取り出して fn を呼び出し、その評価結果を格納したコンスセルを返します。
関数 filter は述語 pred が真を返す要素を取り出します。Fst で要素を取りして述語 pred に渡します。結果が真であれば要素 car xs を tree に追加します。偽であれば car xs を tree に追加しません。関数 foldl, foldr は畳み込みを行います。Fst で要素を取り出し、それと累積変数 a を関数 fn に渡して畳み込みを行います。
簡単な実行例を示します。
> let a = fromList [1..8];; val a: int tree = (1 2 3 4 5 6 7 8) > map (fun x -> x * x) a;; val it: int tree = (1 4 9 16 25 36 49 64) > filter (fun x -> x % 2 = 0) a;; val it: int tree = (2 4 6 8) > foldl (+) 0 a;; val it: int = 36 > foldr (+) 0 a;; val it: int = 36 > foldl (fun a x -> cons x a) Nil a;; val it: int tree = (8 7 6 5 4 3 2 1) > foldr cons Nil a;; val it: int tree = (1 2 3 4 5 6 7 8)
●二分木の探索
次は二分木 tree を探索する関数 memberTree と findTree を作ります。tree は二分探索木ではないので、tree を巡回してすべての要素を調べることになります。
リスト : 二分木の探索 let rec memberTree x = function Nil -> false | Leaf y -> x = y | Cons(a, d) -> memberTree x a || memberTree x d let rec findTree pred = function Nil -> None | Leaf x -> if pred x then Some x else None | Cons(a, d) -> findTree pred a |> Option.orElse (findTree pred d)
memberTree は CAR と CDR の部分木をたどり、引数 x と等しい要素を探します。二分木が Nil ならば false を返します。Leaf y の場合は x と等しいかチェックします。Cons(a, d) の場合は CAR を調べて結果が false であれば CDR を調べます。
findTree は述語 pred が真を返す最初の要素を探します。Option.orElse を使っていることに注意してください。tree が Nil の場合は None を返します。Leaf の場合、pred x が真であれば Some x を返し、そうでなければ None を返します。Cons(a, d) の場合は findTree を CAR に適用し、その結果が None であれば findTree を CDR に適用します。この処理を Option.orElse で行っています。
Option.orElse expr1 expr2
orElse は expr1 と expr2 を評価し、評価結果が None ではない方の値を返します。両方とも None であれば None を返します。どちらも None 以外の値であれば expr2 の評価結果を返します。演算子 || とは違って短絡評価ではないことに注意してください。
簡単な実行例を示します。
> Option.orElse (Some 10) None;; val it: int option = Some 10 > Option.orElse None (Some 20);; val it: int option = Some 20 > Option.orElse (Some 10) (Some 100);; val it: int option = Some 100 > Option.orElse (None: int option) None;; val it: int option = None > cons 3 (Cons(cons 4 (Leaf 5), cons 6 Nil));; val it: int tree = (3 (4 . 5) 6) > cons 2 (Cons(it, cons 7 Nil));; val it: int tree = (2 (3 (4 . 5) 6) 7) > let a = cons 1 (Cons(it, cons 8 (cons 9 Nil)));; val a: int tree = (1 (2 (3 (4 . 5) 6) 7) 8 9) > memberTree 4 a;; val it: bool = true > memberTree 5 a;; val it: bool = true > memberTree 9 a;; val it: bool = true > memberTree 0 a;; val it: bool = false > memberTree 10 a;; val it: bool = false > findTree (fun x -> x > 6) a;; val it: int option = Some 7 > findTree (fun x -> x > 2) a;; val it: int option = Some 3 > findTree (fun x -> x < 2) a;; val it: int option = Some 1 > findTree (fun x -> x < 1) a;; val it: int option = None
●二分木のマッピング
次は tree のマップ関数 mapTree を定義しましょう。次のリストを見てください。
リスト : マッピング let rec mapTree fn = function Nil -> Nil | Leaf x -> Leaf (fn x) | Cons(a, d) -> Cons(mapTree fn a, mapTree fn d)
mapTree の最後の引数が Nil ならば Nil を返します。Leaf x ならば Leaf (fn x) を返します。Cons(a, d) ならば、CAR と CDR に mapTree を適用し、その結果を Cons に格納して返します。とても簡単ですね。
簡単な実行例を示します。
> a;;
val it: int tree = (1 (2 (3 (4 . 5) 6) 7) 8 9)
> mapTree (fun x -> x * 2) a;;
val it: int tree = (2 (4 (6 (8 . 10) 12) 14) 16 18)
> mapTree (fun x -> x + 1) a;;
val it: int tree = (2 (3 (4 (5 . 6) 7) 8) 9 10)
> mapTree (fun x -> [x]) a;;
val it: int list tree =
Cons
(Leaf [1],
Cons
(Cons
(Leaf [2],
Cons
(Cons
(Leaf [3],
Cons (Cons (Leaf [4], Leaf [5]), Cons (Leaf [6], Nil))),
Cons (Leaf [7], Nil))), Cons (Leaf [8], Cons (Leaf [9], Nil))))
●二分木の畳み込み
次は木を畳み込む関数 foldTree を作りましょう。
リスト : 畳み込み let rec foldTree fn acc = function Nil -> acc | Leaf x -> fn x acc | Cons(a, d) -> foldTree fn (foldTree fn acc d) a
foldTree の最後の引数が Nil ならば累積変数 acc を返します。Leaf x ならば x と acc に関数 fn を適用します。Cons(a, d) であれば CDR に foldTree を適用してから、CAR に foldTree を適用します。これで foldr と同様の動作になります。
簡単な実行例を示します。
> a;; val it: int tree = (1 (2 (3 (4 . 5) 6) 7) 8 9) > let flatten xs = foldTree (fun x a -> x::a) [] xs;; val flatten: xs: 'a tree -> 'a list > flatten a;; val it: int list = [1; 2; 3; 4; 5; 6; 7; 8; 9] > let countLeaf xs = foldTree (fun _ a -> a + 1) 0 xs;; val countLeaf: xs: 'a tree -> int > countLeaf a;; val it: int = 9 > let sumTree xs = foldTree (+) 0 xs;; val sumTree: xs: int tree -> int > sumTree a;; val it: int = 45
foldTree を使うと二分木を平坦化する関数 flatten、葉 (要素) の個数を求める countLeaf、要素の合計値を求める関数 sumTree など、いろいろな関数を簡単に定義することができます。
また、次のように述語が真を返す要素をリストに格納して返す関数 filterTree も簡単に定義することができます。
リスト : フィルター let filterTree pred xs = foldTree (fun x a -> if pred x then x::a else a) [] xs
foldTree のラムダ式の中で、pred x の返り値が真であれば x を a に追加します。そうでなければ a をそのまま返します。
簡単な実行例を示します。
> a;; val it: int tree = (1 (2 (3 (4 . 5) 6) 7) 8 9) > filterTree (fun x -> x % 2 = 0) a;; val it: int list = [2; 4; 6; 8] > filterTree (fun x -> x % 2 <> 0) a;; val it: int list = [1; 3; 5; 7; 9]
●二分木の置換
次は二分木 z の中で y と等しい部分木を x に置き換える関数 subst x y z を作ってみましょう。
リスト : 二分木の置換
let rec subst x y z =
if equal y z then x
else
match z with
Cons(a, d) -> Cons(subst x y a, subst x y d)
| _ -> z
引数 x が新しい値、y が元の値、z が tree を表します。z が Nil であれば Nil を返します。Nil でなければ、部分木 z が y と等しいかチェックし、そうであれば x を返します。それ以外の場合、z が Cons(a, d) であれば、CAR と CDR に subst を適用して、その返り値を Cons に格納して返します。それ以外の場合は z をそのまま返します。
それでは実行してみましょう。
> a;; val it: int tree = (1 (2 (3 (4 . 5) 6) 7) 8 9) > subst (Leaf 10) (Leaf 5) a;; val it: int tree = (1 (2 (3 (4 . 10) 6) 7) 8 9) > subst (Leaf 10) (Cons(Leaf 4, Leaf 5)) a;; val it: int tree = (1 (2 (3 10 6) 7) 8 9) > subst (Cons(Leaf 10, Nil)) (Cons(Leaf 4, Leaf 5)) a;; val it: int tree = (1 (2 (3 (10) 6) 7) 8 9)
●二分木の高さ
最後に、二分木の高さを求める関数 heightTree を作りましょう。
リスト : 二分木の高さ let rec heightTree = function Nil -> 0 | Leaf _ -> 1 | Cons(a, d) -> 1 + max (heightTree a) (heightTree d)
tree が Nil ならば 0 を、Leaf ならば 1 を返します。Cons ならば CAR と CDR に heightTree を適用し、大きいほうの値に 1 を加算します。
それでは実行してみましょう。
> heightTree Nil;; val it: int = 0 > heightTree (Leaf 1);; val it: int = 1 > heightTree (cons 1 Nil);; val it: int = 2 > heightTree (cons 1 (cons 2 Nil));; val it: int = 3 > a;; val it: int tree = (1 (2 (3 (4 . 5) 6) 7) 8 9) > heightTree a;; val it: int = 8
正常に動作していますね。
●プログラムリスト
//
// lisp.fsx : Lisp ライクな連結リスト (二分木)
//
// Copyright (C) 2022 Makoto Hiroi
//
module Lisp
// 例外
exception ConsRequired
exception AtomRequired
// 二分木の定義
type 'a tree =
| Nil
| Leaf of 'a
| Cons of 'a tree * 'a tree
member this.Fst() =
match this with
Cons(Leaf x, _) -> x
| _ -> raise AtomRequired
member this.Snd() =
match this with
Cons(_, Leaf x) -> x
| _ -> raise AtomRequired
member this.ToStringSub() =
match this with
Nil -> ""
| Leaf x -> " . " + x.ToString()
| Cons(a, d) -> " " + a.ToString() + d.ToStringSub()
override this.ToString() =
match this with
Nil -> "()"
| Leaf x -> x.ToString()
| Cons(a, d) -> "(" + a.ToString() + d.ToStringSub() + ")"
// 述語
let consp = function
Cons(_, _) -> true
| _ -> false
let listp = function
Leaf _ -> false
| _ -> true
let emptyp = function
Nil -> true
| _ -> false
let rec equal xs ys =
match (xs, ys) with
(Nil, Nil) -> true
| (Leaf a, Leaf d) -> a = d
| (Cons(a1, d1), Cons(a2, d2)) -> equal a1 a2 && equal d1 d2
| _ -> false
// 基本的な操作関数
let car = function
Cons(a, _) -> a
| _ -> raise ConsRequired
let cdr = function
Cons(_, d) -> d
| _ -> raise ConsRequired
let cons x xs = Cons(Leaf x, xs)
// 長さ
let length xs =
let rec iter xs c =
if consp xs then
iter (cdr xs) (c + 1)
else c
iter xs 0
// 反転
let reverse xs =
let rec iter xs acc =
if consp xs then
Cons(car xs, acc) |> iter (cdr xs)
else acc
iter xs Nil
// 連結
let rec append xs ys =
if consp xs then Cons(car xs, append (cdr xs) ys) else ys
// 生成
let fromList xs =
let rec iter xs acc =
match xs with
[] -> reverse acc
| y::ys -> cons y acc |> iter ys
iter xs Nil
// 高階関数
let rec map fn xs =
if consp xs then
cons (fn (xs.Fst())) (map fn (cdr xs))
else Nil
let rec filter pred xs =
if consp xs then
if pred (xs.Fst()) then Cons(car xs, filter pred (cdr xs))
else filter pred (cdr xs)
else Nil
let rec foldl fn a xs =
if consp xs then
foldl fn (fn a (xs.Fst())) (cdr xs)
else a
let rec foldr fn a xs =
if consp xs then
fn (xs.Fst()) (foldr fn a (cdr xs))
else a
// 木の探索
let rec memberTree x = function
Nil -> false
| Leaf y -> x = y
| Cons(a, d) -> memberTree x a || memberTree x d
let rec findTree pred = function
Nil -> None
| Leaf x -> if pred x then Some x else None
| Cons(a, d) -> findTree pred a |> Option.orElse (findTree pred d)
// マッピング
let rec mapTree fn = function
Nil -> Nil
| Leaf x -> Leaf (fn x)
| Cons(a, d) -> Cons(mapTree fn a, mapTree fn d)
// 畳み込み
let rec foldTree fn acc = function
Nil -> acc
| Leaf x -> fn x acc
| Cons(a, d) -> foldTree fn (foldTree fn acc d) a
// フィルター
let filterTree pred xs =
foldTree (fun x a -> if pred x then x::a else a) [] xs
// 置換
let rec subst x y z =
if equal y z then x
else
match z with
Cons(a, d) -> Cons(subst x y a, subst x y d)
| _ -> z
// 木の高さ
let rec heightTree = function
Nil -> 0
| Leaf _ -> 1
| Cons(a, d) -> 1 + max (heightTree a) (heightTree d)