2

与えられたツリーを接尾辞の順序（postorder）‘a btree -> ‘a option listで型の要素のリストに格納する型の関数を書くタスクがあります。‘a option

内部ノードはで表されNone、値を持つ外部ノード（葉）xはで表されSome xます。

これまでのところ、葉の場合は簡単ですが、どのように入れるの'a option listですか？

type 'a btree = L of 'a | N of 'a btree * 'a btree ;;

let rec store t =
    match t with
        | L x -> Some x
        | N (a,b) -> None ???   
;;

私が知っている2番目のマッチケースは正しくありませんが、それを解決するにはどうすればよいですか？

4

2 に答える 2

3

誰かがこの改良に興味を持っている場合は、追加のアキュムレータパラメータをスレッド化することで、Lenのソリューションよりもパフォーマンスの面で少し優れた方法を実行できます。

アイデアはstore : 'a btree -> 'a option list、ツリーを取得してリストを生成する関数から、パラメーターとして渡された既存のstore' : 'a btree -> 'a option list -> 'a option listリストにツリーの要素を追加する関数に移動することです。

let rec store' t acc = match t with
  | L x -> Some x :: acc
  | N (a, b) ->
    store' a (store' b (None :: acc))

この定義では、要素は、最初に一時リストを作成するために使用され、次にオペレーターstore aを介して最終結果に2回追加されるのではなく、最終結果リストに1回だけ追加されます。(@)

t前に書き込むaccと、リスト内の最後の要素の順序が直感的にわかるため、パラメーターの順序は重要です。の要素は、に既に存在する要素のt前になりますacc。これにより、ケースを非常に自然に読み取ることができます。結果には、最初に、、次に、、次にの要素Nが含まれることが簡単にわかります。abNoneacc

最後に、もちろん、次storeの観点から定義することができstore'ます。

let store t = store' t []

最初の定義を2番目の定義内にラップし（この「低レベル」関数をユーザーに公開したくない場合）、外部定義と同じ名前を付けるのが通例です（競合しません）。再帰的ではないため、内部スコープには入りません）：

let store t =
  let rec store t acc = match t with
    | L x -> Some x :: acc
    | N (a, b) ->
      store a (store b (None :: acc))
  in store t []

もちろん、この定義がレンの定義よりも「優れている」かどうかは、評価基準が何であるかによって異なります。Lenのソリューションはより短く、読みやすく、元の問題をより厳密にマッピングします。

（厳密なリストの代わりに遅延列挙を使用することで、両方の長所を活用できる場合がありますが、それはまた別の話です。）

于 2012-05-27T11:34:41.093 に答える
3

最初のケースを見ると、それも完全には存在しないことがわかります。を返し'a optionますが、関数がを返すようにし'a option listます。

明らかにリストを返すので、最初にそれを修正します。

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> [None] (* ??? *)

次に、2番目のケースを修正しましょう。出力に追加Noneしたいのですが、その前に、サブツリーのノードが必要です。

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> (store a) @ (store b) @ [None]

@タイプがあります

'a list -> 'a list -> 'a list

つまり、リストを結合します。左側のサブツリー、右側、最後にこの内部ノードの結果のリストを結合します。

于 2012-05-27T10:57:51.600 に答える