Я хочу сделать функцию maptree со стандартом ML

Question

Я хочу сделать функцию maptree со стандартным ML. Если функция f (x) = x + 1; затем

maptree(f, NODE(NODE(LEAF 1,LEAF 2),LEAF 3)); 

должен сделать результат

NODE(NODE(LEAF 2,LEAF 3),LEAF 4)) 

Я пишу код, как показано ниже.

datatype 'a tree = LEAF of 'a | NODE of 'a tree * 'a tree; 
fun f(x) = x + 1; 
fun maptree(f, NODE(X, Y)) = NODE(maptree(f, X), maptree(f, Y)) 
| maptree(f, LEAF(X)) = LEAF(f X); 

, но когда я исполню этот код, как этот

maptree(f, (NODE(NODE(LEAF 1,LEAF 2),LEAF 3))); 

результата не хочу (NODE (УЗЕЛ (LEAF 2, LEAF 3), LEAF 4))) но NODE (NODE (LEAF #, LEAF #), LEAF 4)). Почему это произошло (не число, а #)?

Answer 1

# используется REPL, когда структура данных, которую он печатает, глубже, чем заданное значение. Если вы увеличите это значение, вы получите результат, который вы исключили. Я предполагаю, что вы используете SML/NJ, который вызывает, что установка print.depth:

sml -Cprint.depth=20 
- maptree(f, (NODE(NODE(LEAF 1,LEAF 2),LEAF 3))); 
val it = NODE (NODE (LEAF 2,LEAF 3),LEAF 4) : int tree 

Вы можете найти больше вариантов, как это, выполнив sml -H. Ищите их в разделе «Настройки печати компилятора»:

compiler print settings: 
    print.depth           (max print depth) 
    print.length          (max print length) 
    print.string-depth       (max string print depth) 
    print.intinf-depth      (max IntInf.int print depth) 
    print.loop            (print loop) 
    print.signatures      (max signature expansion depth) 
    print.opens            (print `open') 
    print.linewidth     (line-width hint for pretty printer) 

Answer 2

Некоторые комментарии:

1. я бы, вероятно, пойти с определением

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

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

2. я бы, вероятно, Карри функцию дерева карты

   fun treemap f Leaf = Leaf 
       | treemap f (Node (l, x, r)) = Node (treemap f l, x, treemap f r) 
   

   , так как вы можете частично применить его, например, как:
   
   

   (* 'abstree t' returns t where all numbers are made positive *) 
   val abstree = treemap Int.abs 
   
   (* 'makeFullTree n' returns a full binary tree of size n *) 
   fun makeFullTree 0 = Leaf 
       | makeFullTree n = 
       let val subtree = makeFullTree (n-1) 
       in Node (subtree, n, subtree) 
       end 
   
   (* 'treetree t' makes an int tree into a tree of full trees! *) 
   val treetree = treemap makeFullTree 
   

3. Вы можете в какой-то момент хотят fold a tree тоже.