0

私はこのコードを持っています：

datatype 'a Tree = Empty | LEAF of 'a | NODE of ('a Tree) list;
val iL1a = LEAF 1;
val iL1b = LEAF 2;
val iL1c = LEAF 3;
val iL2a = NODE [iL1a, iL1b, iL1c];
val iL2b = NODE [iL1b, iL1c, iL1a];
val iL3 = NODE [iL2a, iL2b, iL1a, iL1b];
val iL4 = NODE [iL1c, iL1b, iL3];
val iL5 = NODE [iL4];

fun treeToString f Node = let
    fun treeFun (Empty) = ["(:"]
    | treeFun (NODE([])) = [")"]
    | treeFun (LEAF(v)) = [f v]
    | treeFun (NODE(h::t)) = [""] @ ( treeFun (h)) @ ( treeFun (NODE(t)) )
    in
    String.concat(treeFun Node)
end;

treeToString Int.toString iL5;

関数を実行すると、「32123）231）12）））」という出力が得られます。

答えは「（（32（（123）（231）12）））」でなければなりません。

関数を変更して追加しようとしました（考えられるすべての場所で、「（」を追加する場所がわかりません。どこで混乱しましたか？）

編集：どこかでmapまたはList.filterを使用する必要があると思いますが、どこで使用するかわかりません。

4

1 に答える 1

2

リストノードの末尾を再帰する方法が問題のようです。treeFun hに追加する代わりにtreefun (NODE(t))、NODEの場合にこれを使用してみてください。

 treeFun (NODE(items)) = ["("] @ List.concat (map treeFun items) @ [")"]

つまり、ノードのコンテンツ全体にマップ し、結果をとtreeFunで囲みます。その定義は、何が起こっているのかを理解するには少し簡潔すぎる可能性があるため、より明確になる可能性のあるより詳細な形式を次に示します。"("")"

| treeFun (NODE(items)) =
  let val subtree_strings : string list list = map treeFun items
      val concatenated_subtrees : string list = List.concat subtree_strings
      in ["("] @ concatenated_subtrees @ [")"]
      end

subtree_stringsは、指定されたノード内のすべてのサブツリーを取得し、treeFun各サブツリーを再帰的に呼び出すことによって、それぞれを文字列のリストに変換した結果です。treeFun呼び出されるたびに文字列のリストが返され、サブツリーのリスト全体で呼び出されるため、結果はサブツリーのリストの対応するリストになります。したがって、たとえば、を呼び出すとmap treeFun [LEAF 1, LEAF 2, LEAF 3]、に戻り[["1"], ["2"], ["3"]]ます。

プレーンな文字列のリストではなく、文字列のリストのリストであるため、これは私たちが望む答えではありません。List.concatリストのリストを取得し、基礎となるすべてのアイテムの単一のリストを形成するを使用して、これを修正できます。したがって、たとえばをList.concat [["1"], ["2"], ["3"]]返します["1", "2", "3"]。これで、結果を括弧で囲むだけで完了です。

この戦略は、1つ以上のサブツリーを持つノードの場合と同様に、完全に空のノードでも機能するため、treeFun元の定義の2番目のケースが不要になることに注意してください。一般に、MLでは、1つの引数の関数が、引数の型のコンストラクターごとに正確に1つのケースを持たない場合、コードの臭いがします。

于 2010-11-07T23:44:27.987 に答える