2

SML の課題があり、質問の 1 つは関数を実装することです

findAll : (int -> bool) -> binary search tree -> int list

これまでのところ、次のものがあります。 

datatype 'a tree = Empty | Node of (int * 'a tree  * 'a tree) 

exception answer of int list

fun findAll f Empty = raise answer []
  | findAll f (Node(x, l, r)) = 
    if (f x) then raise answer(x)::(findAll f l)::(findAll f r)
    else 
        (findAll f l)::(findAll f r)

基本的にfindAll、bool 関数を受け取り、この関数を満たすすべてのノードを例外の形で返します。元の（レイズアンサー）内に（レイズアンサー）があるため、コードが機能しない理由はわかっていますが、どちらにしてもこれはコンパイルされません。これを修正するにはどうすればよいか考えていました。すべての要素を取得してから例外を呼び出すヘルパー関数を呼び出すことはできませんが、例外を運ぶ値を使用する必要があります。また、すべての要素を順番に返すことができるはずです。

4

1 に答える 1

2

エラー メッセージを引用したり、使用しているコンパイラを指定したりしません。SML/NJ から得たものは次のとおりです。

3867615/john316.sml:7.25-7.64 Error: operator and operand don't agree [tycon mismatch]
  operator domain: int list
  operand:         int
  in expression:
    answer x
3867615/john316.sml:7.25-7.64 Error: operator and operand don't agree [circularity]
  operator domain: 'Z * 'Z list
  operand:         'Z * 'Z
  in expression:
    (findAll f) l :: (findAll f) r
3867615/john316.sml:7.25-7.64 Error: argument of raise is not an exception [tycon mismatch]
  raised: _ list
  in expression:
    raise (answer x :: (findAll <exp>) l :: (findAll <exp>) r)
3867615/john316.sml:9.9-9.37 Error: operator and operand don't agree [circularity]
  operator domain: 'Z * 'Z list
  operand:         'Z * 'Z
  in expression:
    (findAll f) l :: (findAll f) r

最初のエラーはかなり明白です:は引数answerを期待するように宣言されていますが、 a から来るan を使用し、でなければなりません。3 番目のエラーは、おそらく優先順位の問題です。コンパイラが式をどのように解析したかがわかりますが、これはおそらく意図したものではありません。(しかし、以下で説明するように、あなたが意図したことは意味がありません。)int listanswer xxNodeint

::2 番目と 4 番目のエラーは、リストの先頭に要素を追加する ("cons") コンストラクターと、@2 つのリストを連結する ("append") 演算子を混同したことが原因です。

ここで、例外に戻りanswerます。それはなんのためですか？関数はすべての出現箇所を見つける必要があるため、ツリー全体をトラバースする必要があります。あなたが早く帰らなければならない状況はありません。したがって、例外は必要ありません。あなたは基本的に正しいアルゴリズムを持っています (空のツリーでは、一致がないので空のリストを返します。ノードでは、存在する場合は再帰呼び出しの結果に一致を追加します)、物事を複雑にしないでください。

2 つの修正を行うと、次のコードが得られます (コンパイルされます)。

fun findAll f Empty = []
  | findAll f (Node(x, l, r)) = 
    if f x then x :: findAll f l @ findAll f r
    else findAll f l @ findAll f r
于 2010-10-10T11:42:37.810 に答える