Как определить деревья с более чем одним типом в языке программирования ML - PullRequest
Новая
       15

Как определить деревья с более чем одним типом в языке программирования ML

4 голосов
/ 21 декабря 2010

Что ж, меня просят сделать следующее:

Чтобы определить двоичное дерево, которое может содержать 2 различных типа: ('a,' b) abtree, и это требования:

  1. Любая внутренняя вершина (не лист) должна иметь тип 'a или' b, и у листьев нет значения.

  2. Для каждого пути в дереве все значения должныпоявляются перед значением 'b: примеры путей: 

    'a->'a->'a-'b (legal)
'a->'b->'b (legal)
'a->'a->'a (legal)
'b->'b->'b (legal)
'a->'b->'a (ILLEGAL)

, а также мне нужно определить другое дерево, подобное описанному выше, но теперь у меня есть также' c иво втором требовании говорится, что для каждого пути I 'значения появляются перед значениями' b, а все значения 'b отображаются перед значениями' c.

Во-первых, я не уверен, как определить двоичные деревьяиметь более 1 типа в них.Я имею в виду простейшее двоичное дерево: 

datatype 'a tree =
          leaf
         | br of 'a * 'a tree * 'a tree;

И также, как я могу определить дерево, чтобы иметь эти требования.

Любая помощь будет оценена.

Спасибо.

ОК, спасибо большое.Итак, вы имеете в виду что-то вроде этого: 

datatype 'b bTree = 
          leaf
        | bBranch of 'b * 'b bTree * 'b bTree
;
datatype ('a,'b) abTree = 
          leaf
        | aBranch of 'a * ('a, 'b) abTree * ('a,'b) abTree
        | bBranch of 'b * 'b bTree * 'b bTree
;

, и это то, что я сделал для случая, когда это дерево 3 типов, как я упоминал выше: 

datatype 'c cTree =  
    leaf
    | cBranch of 'c * 'c cTree * 'c cTree
;


datatype ('b, 'c) bcTree = 
            leaf
    | bBranch of 'b * ('b, 'c) bcTree * ('b,'c) bcTree
    | cBranch of 'c * 'c cTree * 'c cTree

;

datatype ('a, 'b, 'c) abcTree = 
    leaf
            | aBranch of 'a * ('a, 'b, 'c) abcTree * ('a, 'b, 'c) abcTree
            | bBranch of 'b * ('b, 'c) bcTree * ('b, 'c) bcTree
    | cBranch of 'c * 'c cTree * 'c cTree
;

Я прав?

Кроме того, что означает требование листьев?Тот, который говорит, что листья не должны иметь значения?

1 Ответ

3 голосов
/ 21 декабря 2010

Во-первых, я не уверен, как определить двоичные деревья, чтобы в них было более 1 типа. 

datatype ('a, 'b) twotypetree = ...

А также, как я могу определить дерево дляимеют следующие требования.

Определите twotypetree как abranch, который содержит значение 'a и два ('a, 'b) twotypetree s, или bbranch, который содержит 'b tree.

Поскольку 'b tree не может содержать никаких 'a с, у bnode не может быть дочерних узлов, содержащих 'a с, поэтому требование выполняется.

...