0

一般的な二分木をペアとして表現しようとしています。

例として SML 構文を使用します。これは私の btree タイプの定義です:

datatype btree = leaf | branch of btree*btree;

したがって、btree を指定すると、次のように出力する関数を書きたいと思います。

bprint leaf = 0
bprint (branch (leaf,leaf)) = (0,0)
bprint (branch (leaf, branch (leaf,leaf))) = (0, (0, 0))

等々。

問題は、この関数が常に異なる型を返すことです。これは明らかに SML の問題であり、他の関数型言語の問題かもしれません。

何か案が？

4

2 に答える 2

1

他の人がすでに述べたように、他の場所で文字列表現が本当に必要ない場合は、ツリーを印刷するだけが最も簡単な方法かもしれません。

open TextIO

datatype btree = leaf | branch of btree * btree

fun print_btree leaf = print "0"
  | print_btree (branch (s, t)) =
    (print "("; print_btree s; print ", "; print_btree t; print ")")

を表す文字列も取得できるようにしたい場合btree、単純な解決策は次のようになります。

fun btree_to_string leaf = "0"
  | btree_to_string (branch (s, t)) =
    "(" ^ btree_to_string s ^ ", " ^ btree_to_string t ^ ")"

btreeただし、大きなs の場合、多くの文字列連結による問題があるため、このバリアントはあまりお勧めしません。

考えておくと良いのは、次のバリアントです。これは、トリック (たとえば、Haskell のShowクラスでも使用されます) によって連結の問題を回避します。つまり、文字列を処理する代わりに、char リストから char リストへの関数を処理します。次に、連結を関数合成に置き換えることができます

fun btree_to_string' t =
  let
    fun add s t = s @ t
    fun add_btree leaf = add [#"0"]
      | add_btree (branch (s, t)) =
        add [#"("] o add_btree s o add [#",", #" "] o add_btree t o add [#")"]
  in implode (add_btree t []) end
于 2013-04-25T04:51:27.360 に答える
1

ツリー構造を画面に出力するだけなので、それを実行して関数の戻り値の型を にすることができますunit。これは、タプルを返そうとする代わりに(0, (0, 0))、文字列 (0, (0, 0)) を画面に出力するだけです。このようにして、型に関する問題に遭遇することはありません。

于 2013-04-24T21:53:54.807 に答える