Стандартный бинарный тип дерева ML

Question

Я изучаю ML в классе, и у меня возникла проблема с домашней работой, на которой я застрял. Я провел весь день вчера в поисках, но добился небольшого прогресса, и мы не говорили об этом в классе, поэтому я надеюсь, что вы, ребята, можете мне помочь.

Нам дано:

datatype which = STRING of string | INT of int

Часть 1. Нам говорят, что нам нужно создать еще один тип данных с именем whichTree для двоичного дерева, содержащего значения типа which, где данные находятся только на листьях дерева.

Часть 2. Нам нужно создать функцию whichSearch, имеющую тип whichTree -> int -> bool, возвращающую true или false в зависимости от того, находится ли int в дереве.

Это то, что я имею до сих пор:

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. My whichTree не содержит тип which. Я не уверен, как я могу это исправить.
2. У меня должна быть whichSearch функция типа whichTree -> int -> bool, но она int * whichTree -> bool и я пытаюсь выяснить, как все исправить. Я не уверен, как мне исправить это, поскольку для поиска нужно указать значение i в whichSearch. Я ищу по этому вопросу, но любые советы будут хороши.

Кто-нибудь может помочь? Если так, спасибо! И спасибо ребятам, которые уже ответили.

Answer 1

Исходя из того, что вы придумали, я думаю, что я должен указать на несколько правил в языке Standard-ML, которые вы нарушаете, и надеюсь, что вам будет проще:

• Каждое вводимое вами имя, будь то тип, функция или переменная, может означать только одно (если они находятся в одной области действия в программе).

  • Вы ломаете это, сначала определяя тип данных which, а затем определяя функцию с тем же именем.
  • Вы также разбиваете его, сначала определяя тип данных whichTree, а затем определяя другой тип данных с тем же именем.
  • Вы также разбиваете его на 3-й строке, вводя два новых конструктора типов данных (STRING и INT), которые уже были введены в 1-й строке. Помните, что когда вы используете эти объявления datatype, вы определяете не только имя типа, но и конструкторы для типа.

• Если вы хотите ввести конструктор типа данных, принимающий два параметра, который выглядит так, как если бы вы хотели сделать в строке 3, вы должны использовать звездочку * между типами, а не оператор стрелки -> .

Я бы также согласился с Виктором, вы должны думать в общих чертах о том, что такое двоичное дерево на самом деле, концептуально. Затем переведите это в Standard-ML.

---

Редактировать после того, как код в вопросе был переписан: Ваш новый код намного лучше. Как вы указали, сейчас у вас два вопроса:

1. Как сделать дерево деревом с which значениями? Что ж, ваше дерево в настоящее время представляет собой дерево int значений, поэтому не имеет ли смысла, что вы должны изменить int на which? Но вы также утверждаете, что ваш тип данных дерева должен быть «двоичным деревом, содержащим значения типа», который «где данные находятся только в листьях дерева». Это отличается от того, что вы в данный момент закодировали, в котором int сохраняется на каждом неконечном узле. Неконечные узлы определяются рекурсивным регистром в объявлении типа данных, тогда как листовые узлы определяются нерекурсивным регистром.

2. Функция типа (A * B) -> C (где A, B и C являются типами) может быть переписана для типа A -> B -> C. И то, и другое допустимо и применимо в Standard-ML, но вторая форма обычно предпочтительнее в функциональных языках программирования, поскольку она допускает метод, известный как curry , что означает «применение частичной функции». Чтобы внести изменения, вы в основном пишете параметры другим способом: вместо myFunction(a, b) вы пишете myFunction a b - и там, где вы определяете функцию, и в том месте, где вы ее используете.

Обратите внимание, что я предлагаю вам разобраться с пунктом 2 позже, сначала сосредоточиться на получении правильных типов данных и получении работающей функции поиска, затем вы можете изменить его тип, когда вы знаете, что в противном случае он верен.

Answer 2

Забудьте о МЛ.Используя ручку и бумагу (или маркер и белую доску), можете ли вы объяснить, как будет выглядеть двоичное дерево, содержащее ваши данные на листьях?Можете ли вы объяснить в общих чертах, как вы будете искать элемент в дереве?(подсказка: поиск должен проходить по узлам, решая, идти ли влево или вправо, поэтому нужно , чтобы сохранить некоторую информацию в узлах дерева, чтобы помочь алгоритму поиска принять решение).

Как только вы представите представление и алгоритмы, изложенные в виде английских предложений, их перевод на SML станет проще.