Найти символ в дереве с помощью SML

Question

Я новичок в SML и пытаюсь сосредоточиться на функциональном программировании. Я хочу иметь функцию, которая принимает дерево t и символ c и возвращает true или false, если дерево содержит символ.

Алгоритм, который я хочу реализовать:

1. если лист равен нулю, вернуть false,

2. иначе, если символ находится в листе, вернуть true,

3. вернуть результат левое дерево или результат правого дерева

Это мой тип данных дерева

datatype 'a tree =
    Leaf of 'a
  | Node of 'a tree * 'a * 'a tree;

И это функция

fun containsChar (Leaf t, c: char) = false 
  | containsChar (Node (left, t, right)) = 
    if t = c then true else false
  | containsChar (Node (left, t, right)) = (containsChar left) <> (containsChar right);

Я получаю Unbound value identifier "c". Почему это?

Answer 1

В этом пункте нет ничего под названием "c". В листовом корпусе есть "c", но это совершенно другой случай. Вы забыли этот параметр в других случаях.
(И if t = c then true else false эквивалентно t = c.)

У вас также есть идентичные шаблоны во втором и третьем предложениях, что не сработает ,

Другая проблема, с которой вы сталкиваетесь, это правило "leaf is null" - лист не может быть "null".
Я подозреваю, что это то, что сбило вас с толку, так как результатом вашего первого предложения является false даже если аргумент явно является существующим листом, а ваше второе предложение явно не листом, а выглядит как ваше второе правило.

Ваши правила должны быть такими:

Дерево содержит символ тогда и только тогда, когда

• это значение в листе, или
• это значение в узле, или
• , которое содержится в поддеревья узла.

В ML (снятие ограничения на char Tree, поскольку оно кажется произвольным),

fun contains (Leaf t, c) = t = c 
  | contains (Node (left, t, right), c) = t = c
                                       orelse contains(left, c)
                                       orelse contains(right, c) 

Answer 2

Вы можете обобщить функцию еще раз до

fun any p Leaf = false
  | any p (Node (left, x, right)) =
      p x orelse any p left orelse any p right

fun contains c t = any (fn x => c = x) t