SML: дерево сокращено с помощью базовой и композиционной функции - PullRequest
Новая
       39

SML: дерево сокращено с помощью базовой и композиционной функции

0 голосов
/ 28 февраля 2019

Я хочу уменьшить двоичное дерево с базовым значением z, объединяющей функцию g.Эта функция должна иметь работу O (n), но диапазон O (log n).Дерево определяется как datatype tree = Leaf of int | Node of tree * tree.

Это мой код 

treeReduce : ('a * 'a -> 'a) -> 'a -> 'a tree -> 'a
Requires: g is associative, z is an identity of g
Ensures: treereduce g z T ~= foldr g z (inord T) ~= foldl g z (inord T)

fun treeReduce (g: 'a * 'a -> 'a) (z : 'a) (Empty: 'a tree)=z
  | treeReduce g z (Node(l,x,r))=g(g(treeReduce g z l,x),treeReduce g z r)

Однако это не дает правильного ответа.Что я делаю не так?

1 Ответ

0 голосов
/ 28 февраля 2019

Вы говорите, что ваш код не дает правильного ответа, но вы не говорите, какой ответ вы получите, и почему это не правильно.Так что, возможно, в вашем коде есть ошибка, или вы обходите дерево в другом порядке, чем вы хотите.Если бы я узнал, я бы немного переформатировал ваш код: 

fun treeReduce g z0 Empty = z0
  | treeReduce g z0 (Node (left, x, right)) =
    let val z1a = treeReduce g z0 left
        val z1b = treeReduce g z0 right
        val y = g (z1a, x)
        val z = g (z1b, y)
    in z end

Я использовал let-in-end , чтобы более точно дать каждому вычислению имя.

  • Одна вещь, которая кажется мне странной, это то, что z1a и z1b оба основаны на z0.Сравните это с реализацией обхода деревьев в SML для предварительного заказа, по порядку и после заказа, и вы увидите, что вы, вероятно, хотите, чтобы накопленное значение перемещалось по каждому узлу.В вашем случае z1a не переносится в ветку right.

  • Еще одна вещь, которая мне кажется странной, - это подпись типа treeReduce: 

    ('a * 'a -> 'a) -> 'a -> 'a tree -> 'a

    Сравните это с treefold_preorder s: 

    ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b

    и ради этого List.foldl s: 

    ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

    Это позволяет накопительной функции производитьзначения произвольного типа 'b вместо возможности создания значений типа узла дерева 'a.Это, предположительно, случайное изменение вызвано передачей выходных данных g себе: 

    g(g(tree..., x), tree...)

    , заставляя его входное значение (тип узла, 'a) иметь тот же тип, что и его выходное значение.

Что я делаю не так?

Вы неправильно соединяете левый и правый вызовы на treeReduce, и вы получаетеодин вызов g слишком много (при попытке склеить левый и правый вызовы treeReduce), в результате чего он будет иметь тип 'a * 'a -> 'a, если вы хотите, чтобы он имел тип 'a * 'b -> 'b или аналогичный.

Поскольку вы складываете деревья, это может представлять интерес:

...