Как извлечь кортеж из типа данных?

Question

плохо знаком с SML и пытаюсь учиться с помощью серии упражнений.Функция, которую я пытаюсь написать, имеет дело с выравниванием дерева с N детьми.Мой подход состоял в том, чтобы просто взять текущий NTreeNode и добавить его значение в какой-то список, который я бы вернул.Затем возьмите второй аргумент - список детей и добавьте его в другой список, который будет моей очередью.Эта очередь будет служить всеми элементами, которые мне еще предстоит обработать.

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

Однако, когда я пытаюсь обработать NTreeNode из своей очереди, он возвращает мне NTree, и я не могу использовать свои функции first / second для этого, янужен кортеж обратно из очереди.Я просто не понимаю, как вернуть кортеж, я пытался использовать конструктор NTreeNode, но даже это возвращает мне NTree.

Мой вопрос: как мне извлечь кортеж изNTree тип данных, который я определил.

datatype NTree =
NTreeNode of int * NTree list
| EmptyNTree
;

fun first  (a, _) = a;
fun second (_, b) = b;

fun processTree queue finalList  = 
  if null queue
   then finalList
  else processTree ((tl queue)@(second(NTreeNode(hd queue)))) finalList@[first (NTreeNode (hd queue)) ]
;
fun flattenNTree EmptyNTree = []
   | flattenNTree (NTreeNode x) = processTree (second x) [(first x)]
 ;

Пример входного значения:

val t =
  NTreeNode (1, [
    NTreeNode (2, [
      NTreeNode (3, [EmptyNTree]),
      NTreeNode (4, []),
      NTreeNode (5, [EmptyNTree]),
      EmptyNTree
    ]),
    NTreeNode (6, [
      NTreeNode (7, [EmptyNTree])
    ])
  ]);

Answer 1

Гораздо проще разобрать вещи при сопоставлении с образцом, чем возиться с селекторами типа first или tl.

Также более эффективно накапливать список в обратном порядке и исправлять его, когда вы закончите, чем неоднократно добавлять в конец его.

fun processTree [] final = reverse final
  | processTree (EmptyTree::ts) final = processTree ts final
  | processTree ((NTreeNode (v,t))::ts) final = processTree (ts @ t) (v :: final)

Answer 2

Учитывая тип дерева

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

, вы можете сложить его:

fun fold f e0 Leaf = e0
  | fold f e0 (Node (x, ts)) =
    let val e1 = f (x, e0)
    in foldl (fn (t, e2) => fold f e2 t) e1 ts
    end

и сгладить его:

fun flatten t =
    fold op:: [] t

Answer 3

В вашей функции processTree отсутствует регистр для EmptyNTree, и вы, кажется, пытаетесь добавить конструкторы NTree перед вызовом first и second, тогда как вам, скорее всего, нужно удалить их, как вы это делаетев flattenNTree.

Обе проблемы можно исправить, применив сопоставление с шаблоном к началу очереди:

fun processTree queue finalList =
  if null queue
  then finalList
  else case hd queue of
         EmptyNTree => processTree (tl queue) finalList
       | NTreeNode v => processTree (tl queue @ second v) (finalList @ [first v])
;

Можно также рассмотреть реализацию, основанную на функционалах списка (хотя порядокрезультат не тот же):

fun flattenNTree t = case t of
    EmptyNTree => []
  | NTreeNode (n, nts) => n :: (List.concat (List.map flattenNTree nts));