Рекурсивно добавлять элементы в два набора списков в SML - PullRequest
Новая
       27

Рекурсивно добавлять элементы в два набора списков в SML

0 голосов
/ 08 октября 2018

Я хочу рекурсивно взять список из двух кортежей (например, [(1, 2), (3, 4), (5, 6)]) и превратить его в кортеж из двух списков int (результат: ([1, 3, 5], [2, 4, 6])).Я понимаю, как сделать обратное (взять кортеж из двух списков и превратить его в список кортежей), но я не понимаю, как сделать рекурсивный вызов в том же списке.

Это мой код, такдалеко, я думаю, что я близко: 

fun toTuple [] = ([], [])
| toTuple [((x:int, y:int)::xs)] = (x::[], y::[]) toTuple (xs).

Компилятор выдает мне ошибку: 

Error: operator is not a function [tycon mismatch]
  operator: int list * int list
  in expression:
(x :: nil,y :: nil) unzip

Я считаю, что это означает, что мне нужно поместить оператор между (x :: []), y :: []) и toTuple (xs).Я хочу, чтобы рекурсия поместила элементы кортежа в тот же список, который я создал, и я не знаю оператора, который сделал что-то подобное.

Спасибо.

Ответы [ 2 ]

0 голосов
/ 08 октября 2018

Вот как вы можете сделать это, используя простую рекурсивную функцию: 

fun toTuple [] = ([], [])
  | toTuple ((x,y)::pairs) =
      case toTuple pairs of
        (xs, ys) => (x::xs, y::ys)

Обрабатывает оставшиеся pairs рекурсивно, распаковывает результат как (xs, ys) и добавляет x и y к этому результату впоследствии.Вместо case-of вы можете использовать let-binding: 

fun toTuple [] = ([], [])
  | toTuple ((x,y)::pairs) =
    let val (xs, ys) = toTuple pairs
    in (x::xs, y::ys)
    end

И если вы не выполняли этот тип сопоставления с шаблоном непосредственно в функции toTuple, вам, возможно, придется переместитьраспаковка и повторная упаковка результата в отдельную функцию: 

fun add (x,y) (xs,ys) = (x::xs, y::ys)
fun toTuple [] = ([], [])
  | toTuple (pair::pairs) = add pair (toTuple pairs)

Эти три подхода более или менее эквивалентны.

В ответ на хвост-рекурсивный вариант @ pyon, 

fun loop (xs, ys, nil) = (rev xs, rev ys)
  | loop (xs, ys, (x, y) :: zs) = loop (x :: xs, y :: ys, zs)

fun toTuple xs = loop (nil, nil, xs)

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

Если вы сравните мои три решения с pyon, его решение в чем-то отличается: у него есть вспомогательная функция loopэто рекурсивно, в то время как версия, которую я написал с помощью вспомогательной функции add, add, не является рекурсивной и управляет только распаковкой и повторной упаковкой кортежа.toTuple все еще имеет только один аргумент, но loop имеет еще два, один для хранения временных результатов x :: xs и один для y :: ys.

Когда вы обрабатываете список слева направо,но накапливая результат в аргументе, первый элемент на входе становится первым, который будет добавлен к накопленному результату, что означает, что он заканчивается как последний элемент результата.(Вы можете думать о списке как о стеке.)

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

Во-первых, для моего варианта версии toTuple [(1,2),(3,4),(5,6)]: 

toTuple [(1,2),(3,4),(5,6)]
  ~> case toTuple [(3,4),(5,6)] of
       (xs, ys1) => (1::xs1, 2::ys)
  ~> case (case toTuple [(5,6)] of
             (xs', ys') => (3::xs', 4::ys')) of
       (xs, ys) => (1::xs, 2::ys)
  ~> case (case (case toTuple [] of
                   (xs'', ys'') => (5::xs'', 6::ys'')) of
             (xs', ys') => (3::xs', 4::ys')) of
       (xs, ys) => (1::xs, 2::ys)
  ~> case (case (case ([], []) of
                   (xs'', ys'') => (5::xs'', 6::ys'')) of
             (xs', ys') => (3::xs', 4::ys')) of
       (xs, ys) => (1::xs, 2::ys)
  ~> case (case (5::[], 6::[]) of
             (xs', ys') => (3::xs', 4::ys')) of
       (xs, ys) => (1::xs, 2::ys)
  ~> case (3::5::[], 4::6::[]) of
       (xs, ys) => (1::xs, 2::ys)
  ~> (1::3::5::[], 2::4::6::[]
  ~> ([1,3,5], [2,4,6])

Во-вторых, для версии @ pyon: 

toTuple [(1,2),(3,4),(5,6)]
  ~> loop ([], [], [(1,2),(3,4),(5,6)])
  ~> loop (1::[], 2::[], [(3,4),(5,6)])
  ~> loop (3::1::[], 4::2::[], [(5,6)])
  ~> loop (5::3::1::[], 6::4::2::[], [])
  ~> (rev [5,3,1], rev [6,4,2])
  ~> ...
  ~> ([1,3,5], [2,4,6])

Редактировать: Как указывает @pyon в комментарии, они используют одинаковое количество памяти и времени.Разница заключается в моей версии, использующей неявный стек (вызов), а в его версии - явный стек (аргумент).

0 голосов
/ 08 октября 2018

Я бы сделал это с явными параметрами аккумулятора: 

fun loop (xs, ys, nil) = (rev xs, rev ys)
  | loop (xs, ys, (x, y) :: zs) = loop (x :: xs, y :: ys, zs)

fun toTuple xs = loop (nil, nil, xs)

Оглядываясь назад, можно сказать, что было бы эффективнее: 

fun loop (xs, ys, nil) = (xs, ys)
  | loop (xs, ys, (x, y) :: zs) = loop (x :: xs, y :: ys, zs)

fun toTuple xs = loop (nil, nil, rev xs)
...