2

私はクラスでMLを勉強していますが、宿題の問題にぶつかりました。私は昨日一日中検索をしましたが、ほとんど進歩がなく、クラスでこれについて話しませんでした。皆さんが私を助けてくれることを願っています。

私たちは与えられます：

datatype which = STRING of string | INT of int

パート1。データがツリーのリーフにのみwhichTreeあるタイプの値を含むバイナリツリーにちなんで名付けられた別のデータタイプを作成する必要があると言われています。which

パート2。intがツリー内にあるかどうかに基づいて、trueまたはfalseを返すwhichSearch型を持つ関数を作成する必要があります。whichTree -> int -> bool

これは私がこれまでに持っているものです：

datatype which = STRING of string | INT of int;
datatype whichTree = Empty | Node of int*whichTree*whichTree;

val t1 = Node(6, Node(4,Empty,Empty), Node(15, Node(11,Empty,Empty), Node(24,Empty,Empty)));
val t2 = Node(157,Empty,Empty);
val t3 = Node(102,t1,t2);

fun whichSearch (i, Empty) = false
| whichSearch (i, Node(entry, left, right)) =
    if i = entry then true
    else whichSearch (i, left)
    orelse whichSearch (i, right);

私が今直面している問題はこれです：

  1. MywhichTreeにはタイプが含まれていませんwhich。どうすれば修正できるかわかりません。
  2. 私は自分whichSearchの型の関数を持っているべきですwhichTree -> int -> boolが、それはint * whichTree -> bool問題を修正する方法を見つけようと取り組んでいます。検索するにはiinの値を指定する必要があるため、これを修正する方法がわかりません。whichSearch私はこれを探していますが、どんなヒントも素晴らしいでしょう。

誰か助けてもらえますか？もしそうなら、ありがとう！そして、すでに応答してくれた人たちに感謝します。

4

2 に答える 2

3

あなたが思いついたことに基づいて、あなたが破っている標準 ML 言語のいくつかのルールを指摘する必要があると思います。

  • 導入する各名前は、型、関数、変数のいずれであっても、(プログラム内で同じスコープにある限り) 1 つのことしか意味しません。

    • which最初にデータ型を定義し、次に同じ名前で関数を定義することにより、これを破ります。
    • whichTreeまた、最初にデータ型を定義し、次に同じ名前で別のデータ型を定義することによっても、これを破ることができます。
    • 実際には、1 行目に既に導入されている2 つの新しいデータ型コンストラクター (STRINGおよび) を導入することにより、3 行目でもそれを中断しています。INTこれらのdatatype宣言を使用するときは、型名だけでなく、型のコンストラクターも定義していることに注意してください。

  • 2 つのパラメーターを取るデータ型コンストラクターを導入する場合 (3 行目で行うように見えます) *、矢印演算子ではなく、型の間にアスタリスクを使用する必要があります->。

私もビクターに同意します。二分木が実際に何であるかについて、概念的に一般的に考える必要があります。次に、これを Standard-ML に変換します。

質問のコードが書き直された後に編集します。新しいコードははるかに優れています。ご指摘のとおり、あなたは今、2 つの疑問を抱えています。

  1. whichツリーを値のツリーにするにはどうすればよいですか? さて、あなたのツリーは現在、int値のツリーintですwhich。ただし、ツリーのデータ型は「データがツリーの葉にのみある「タイプ」の値を含むバイナリツリー」である必要があるとも述べています。intこれは、すべての非リーフノードでを保持する、現在コーディングしているものとは異なります。非リーフ ノードはデータ型宣言の再帰ケースによって決定され、リーフ ノードは非再帰ケースによって決定されます。

  2. 型 (A、B、C は型) の関数は、型(A * B) -> Cに書き換えることができますA -> B -> C。どちらも標準 ML で有効で使用可能ですが、通常、関数型プログラミング言語では 2 番目の形式が好まれます。これは、「部分関数適用」を意味するカリー化 と呼ばれる手法を使用できるためです。変更を行うには、基本的に別の方法でパラメーターを記述します。 の代わりに、関数を定義する場所と使用する場所の両方に --myFunction(a, b)を記述します。myFunction a b

後でポイント 2 を処理することをお勧めします。最初にデータ型を正しく取得し、機能する検索機能を取得することに焦点を当てます。

于 2010-11-02T18:06:24.637 に答える
1

MLを忘れてください。ペンと紙（またはマーカーとホワイトボード）を使用して、葉にデータを含む二分木がどのように見えるかを説明できますか？ツリー内の要素を検索する方法を大まかに説明できますか？（ヒント：検索では、左に移動するか右に移動するかを決定してノードをトラバースする必要があるため、検索アルゴリズムの決定に役立つ情報をツリーノードに保持する必要があります）。

表現とアルゴリズムを英語の文章として配置すると、それらをSMLに変換するのが簡単になります。

于 2010-11-02T18:02:02.440 に答える