рекурсивная распаковка списка через сигнатуры функций - PullRequest
Новая
       5

рекурсивная распаковка списка через сигнатуры функций

0 голосов
/ 04 сентября 2011

Я пытаюсь написать функцию в sml, которая «распаковывает» список гнезд произвольной глубины.Например, распаковка [[[1,2]]] должна дать [1,2].Я пытаюсь что-то вроде:

весело распаковать xs = если nestedp (xs), то распаковать (hd xs) иначе xs;

свесело nestedp [_] = правда |nestedp _ = false;

sml не любит распаковку, определенную таким образом, потому что выводит тип распаковки как «список ->» a.Возврат вызова hd передается обратно в unpack, но теперь он «не видит» список, а только одну переменную.

Возможно ли вообще таким способом распаковать вложенный список?

1 Ответ

1 голос
/ 07 сентября 2011

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

Например, можно подумать, что это было бы возможно с функцией типа 'a list list -> 'a list, а затем применять ее рекурсивно, пока не достигнет базового случая не вложенного списка. Однако вы никак не сможете обнаружить базовый вариант, оставив несоответствующие типы.

Однако вы можете сделать это, если создали свой собственный тип списка: 

datatype 'a nestableList = Cons of 'a * 'a nestableList
                         | NCons of 'a nestableList * 'a nestableList
                         | Nil;

Здесь Cons и Nil будут работать так же, как :: и [], тогда как NCons позволит создать вложенный список.

Как пример: 

(* The list [[1, 2], [[3], [4, 5, 6]]] *)
val nlist = NCons(
              Cons(1, Cons(2, Nil)),
              NCons(
                NCons(
                  Cons(3, Nil),
                  Cons(4, Cons(5, Cons(6, Nil)))
                ),
                Nil
              )
           );

Затем вы можете сгладить этот тип вложенного списка следующим образом: 

fun flatten nls =
let
  fun flatten_ Nil                 = []
    | flatten_ (NCons(head, tail)) = flatten head @ flatten tail
    | flatten_ ( Cons(head, tail)) = head :: flatten tail
in
    flatten_ nls
end;

Который затем можно было бы использовать вот так 

val flattenedNlist = flatten nlist;     (* Yields [1, 2, 3, 4, 5, 6] *)

Здесь у меня есть обычный список, но его можно легко изменить, чтобы он возвращал список того же типа.

...