Как сделать эту мл процедуру - PullRequest
Новая
       28

Как сделать эту мл процедуру

0 голосов
/ 30 мая 2011

У меня есть этот код: 

datatype 'a tree = Leaf of 'a | Node of 'a * 'a tree * 'a tree | Nil;
val rec tree_sum = fn(f,e,Nil) => e 
                   | (f,e,Leaf(n)) => n 
                   | (f,e,Node(node,right,left)) =>     
                               f(node,tree_sum(f,e,right),tree_sum(f,e,left));

val binnum = Node(5,Leaf(4),Node(2,Leaf(1),Node(8,Nil,Nil)));
tree_sum((fn(a,b,c)=> a+b+c),0,binnum);
val it = 20 : int

Как я могу сделать ту же процедуру treesum, когда у меня есть другой тип данных: 

datatype 'a stree = Leaf of 'a | Brnch of 'a stree list;

treesum(fn(a, b) => a + b, 0, Brnch([Leaf 2, Brnch([Leaf 5, Leaf 3, Leaf 8])]));
val it = 18 : int

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

val rec treesum = 
         fn (f,e,nil) => e 
            | (f,e,Leaf(n)) => n 
            | (f,e,Brnch(h::lst)) => 
                   f(treesum(f,e,h),treesum(f,e,lst));

1 Ответ

1 голос
/ 30 мая 2011

Есть два места, где вы ошиблись.Прежде всего, nil - это не stree, а Brnch nil - это stree.Во-вторых, lst - это не улица, но Brnch lst - это stree.Ваша функция может быть исправлена ​​следующим образом (я переупорядочиваю регистры для удобства чтения): 

val rec treesum = 
         fn (f,e,Leaf(n)) => n 
            | (f,e,Brnch nil) => e 
            | (f,e,Brnch(h::lst)) => 
                   f(treesum(f,e,h),treesum(f,e,Brnch lst));

Еще одна вещь, вы должны написать свою функцию, следуя структуре типа данных.Так что лучше использовать следующую версию, использующую функции List: 

val rec treesum = 
         fn (f,e,Leaf(n)) => n 
            | (f,e,Brnch ls) => 
                   List.foldl (fn (l, acc) => f(treesum(f,e,l), acc)) e ls;
...