SML / ML Int в строковое преобразование - PullRequest
Новая
       18

SML / ML Int в строковое преобразование

0 голосов
/ 07 ноября 2010

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

datatype 'a Tree = Empty | LEAF of 'a | NODE of ('a Tree) list;
val iL1a = LEAF 1;
val iL1b = LEAF 2;
val iL1c = LEAF 3;
val iL2a = NODE [iL1a, iL1b, iL1c];
val iL2b = NODE [iL1b, iL1c, iL1a];
val iL3 = NODE [iL2a, iL2b, iL1a, iL1b];
val iL4 = NODE [iL1c, iL1b, iL3];
val iL5 = NODE [iL4];

fun treeToString f Node = let
    fun treeFun (Empty) = ["(:"]
    | treeFun (NODE([])) = [")"]
    | treeFun (LEAF(v)) = [f v]
    | treeFun (NODE(h::t)) = [""] @ ( treeFun (h)) @ ( treeFun (NODE(t)) )
    in
    String.concat(treeFun Node)
end;

treeToString Int.toString iL5;

Когда я запускаю свою функцию, я получаю вывод: «32123) 231) 12)))».

Ответ должен быть "((32 ((123) (231) 12)))".

Я пытался изменить свою функцию, чтобы добавить (в любом месте, где я могу думать, но я не могу понять, где я должен добавить "(".

Редактировать: Я считаю, что мне нужно где-то использовать map или List.filter, но я не уверен, где.

1 Ответ

2 голосов
/ 08 ноября 2010

Похоже, ваш метод рекурсии по хвосту узла списка является проблемой. Вместо treeFun h, добавленного к treefun (NODE(t)), попробуйте использовать это для случая NODE: 

 treeFun (NODE(items)) = ["("] @ List.concat (map treeFun items) @ [")"]

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

| treeFun (NODE(items)) =
  let val subtree_strings : string list list = map treeFun items
      val concatenated_subtrees : string list = List.concat subtree_strings
      in ["("] @ concatenated_subtrees @ [")"]
      end

subtree_strings - это результат взятия всех поддеревьев в данном узле и превращения каждой из них в список строк путем рекурсивного вызова treeFun для каждого поддерева. Поскольку treeFun возвращает список строк каждый раз, когда он вызывается, и мы вызываем его для всего списка поддеревьев, результатом является соответствующий список списков поддеревьев. Так, например, если бы мы позвонили map treeFun [LEAF 1, LEAF 2, LEAF 3], мы бы вернулись [["1"], ["2"], ["3"]].

Это не тот ответ, который нам нужен, поскольку это список списков строк, а не список простых строк. Мы можем исправить это, используя List.concat, который берет список списков и формирует единый список всех базовых элементов. Например, List.concat [["1"], ["2"], ["3"]] возвращает ["1", "2", "3"]. Теперь все, что нам нужно сделать, это поставить круглые скобки вокруг результата, и все готово.

Обратите внимание, что эта стратегия работает так же хорошо для полностью пустых узлов, как и для узлов с одним или несколькими поддеревьями, поэтому она устраняет необходимость во втором случае treeFun в исходном определении. Как правило, в ML это запах кода, если функция одного аргумента не имеет точно один случай для каждого конструктора типа аргумента.

...