В sml, почему он выдает Error: синтаксическая ошибка: удаление IN IF - PullRequest
Новая
       10

В sml, почему он выдает Error: синтаксическая ошибка: удаление IN IF

0 голосов
/ 28 сентября 2018

Я делаю функцию, чтобы определить, является ли дерево сбалансированным или нет. 

fun balanced(tree) =
  let 
    fun size tree =
      case tree of
           Lf => 0
         | Br(xs,ys,zs) => 1 + size ys + size zs
    fun depth tree =
      case tree of
           Lf => 0
         | Br(xs,ys,zs) =>
            let val l_count = 1 + depth ys
                val r_count = 1+ depth zs
            in
              if l_count > r_count then l_count else r_count
            end
  in
    if size(ys) = size(zs) andalso depth(ys) = depth(zs) then true
    else if tree=Lf then true
    else false
  end;

Но выдает следующие ошибки: 

stdIn:829.18-829.20 Error: unbound variable or constructor: zs
stdIn:829.9-829.11 Error: unbound variable or constructor: ys
stdIn:829.48-829.50 Error: unbound variable or constructor: zs
stdIn:829.36-829.38 Error: unbound variable or constructor: ys

Ответы [ 2 ]

0 голосов
/ 28 сентября 2018

Вы не указали тип данных, с которым работает эта функция.Я предполагаю, что это выглядит так: 

datatype 'a binary_tree = Lf | Br of 'a * 'a binary_tree * 'a binary_tree

Вы получаете ошибки несвязанных переменных, потому что код 

if size(ys) = size(zs) andalso ...

не имеет таких переменных в своей области видимости.Эти переменные доступны только в области действия ваших вспомогательных функций.Вот некоторые подсказки:

  1. Не называйте свои переменные xs, ys и zs, когда xs фактически является значением, находящимся в ветви, и ysи zs фактически являются левым и правым поддеревьями ветви.Лучшими именами могут быть x (или _, если вы его не используете), left и right.

  2. Используйте Int.max (x, y) вместо if x > y then x else y.

    Аналогично, if foo then true else false эквивалентно просто foo.

    Так что вам не нужно if-then-else в теле balanced.

  3. Выполните сопоставление с шаблоном непосредственно в аргументе функции.

  4. Не нужно знать количество элементов в поддереве (size)чтобы определить, сбалансирован ли он.Необходимо знать только высоту / глубину дерева (depth).

  5. Переместить вспомогательные функции из этой функции.

    Они полезны сами по себе.право. 

    fun size Lf = 0
  | size (Br (_, left, right)) = 1 + size left + size right

fun depth Lf = 0
  | depth (Br (_, left, right)) = 1 + Int.max (depth left, depth right)

  6. Запись balanced декларативным способом : Пустое дерево (Lf) тривиально сбалансировано.Непустое дерево (Br ...) сбалансировано, если левое поддерево сбалансировано, правое поддерево сбалансировано, а разница глубины левого и правого поддерева не превышает 1.

    fun balanced Lf = true
  | balanced (Br (_, left, right)) =
      balanced left andalso
      balanced right andalso
      ...the 'abs'(olute) difference of 'depth left' and 'depth right' is not more than 1...

  7. Это решение довольно часто проходит по дереву: сначала с balanced и , затем с depth.Вы можете написать решение для этого упражнения, которое обходит дерево только один раз, возвращая кортеж (is_subtree_balanced, subtree_height). 

    fun balanced_helper Lf = (true, 0)
  | balanced_helper (Br (_, left, right)) =
    let val (is_left_balanced, left_height) = balanced_helper left
    in ...we can stop here if the left sub-tree isn't balanced...
       let val (is_right_balanced, right_height) = balanced_helper right
       in ...we can stop here if the right sub-tree isn't balanced...
          ...otherwise: (true, 1 + Int.max(left_height, right_height))...
       end
     end

fun balanced tree = #1 (balanced_helper tree)
0 голосов
/ 28 сентября 2018

Между in и end

  in
    if size(ys) = size(zs) andalso depth(ys) = depth(zs) then true
    else if tree=Lf then true
    else false
  end;

вы используете ys и zs, которые вы никогда не определяли ранее.Функции ys и zs, имеющиеся в depth и size, являются локальными для этих функций и не видны для balanced.

...