f# - リストからツリーを構築する関数を書く

Question

F# でリストからツリーを構築する関数を作成するにはどうすればよいですか?

 type Tree =
         | Node of (Tree * Tree)
         | leaf of int

ツリーのラベルを左から読み取って書き込む場合、それらは元のリストと同じ順序になるはずです。

Answer 1

ここでは、開始するためのヒントをいくつか示します。あなたの定義を考えるとTree：

type Tree = 
    | Leaf of int
    | Node of (Tree * Tree) 

Tree整数のリストから値を構築する関数を定義したいとします。問題をより小さな断片に分割することをお勧めします。そのため、fromList関数を直接定義する代わりに、単一の要素を追加するためのより単純な関数から始めることができます。これを行うには、2 つのケース、つまり考えられる 2 つのツリーの形状を考慮する必要があるだけなので、そのような関数のスタブは既に与えられています。

let addInt n tree =
    match tree with
    | Leaf x        -> ??
    | Node (t1,t2)  -> ??

合理的な定義を見つけたら、リストと再利用を操作する関数をどのように定義するかを考えることから始めることができますaddInt。今回は、リストの基本ケースを一致させる必要があります。

let rec addMany xs tree =
    match xs with
    | []        -> ??
    | x :: xs   -> ??

このような問題を明示的な再帰を使用して問題なく解決できるようにList.foldなったら、ソリューションを単純化するために を参照してください。