Как связать элементы в первом списке со всеми элементами во втором списке в SML?

Question

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

Например, pair ([1,2], [3,4,5])return

[(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)].

Моя работа на данный момент:

-fun pair(a:int list, b:int list) = if null a then nil else if null b then nil else (hd a, hd b)::pair(a, tl b)@pair(tl a, b);

val pair = fn : int list * int list -> (int * int) list

-pair([1,2],[3,4,5]);

val it = [(1,3),(1,4),(1,5),(2,5),(2,4),(2,5),(2,3),(2,4),(2,5)]

Я попытался отследить функцию, чтобы выяснить, почему (2,5), (2,4), (2,5) показываютвверх, но я все еще не вижу это ясно.

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

Спасибо.
Питер

Answer 1

Основная проблема в том, что вы повторяете оба списка.

Если вы посмотрите на ваш пример,

pair ([1,2], [3,4,5]) -> [(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]

, вы увидите, что у него есть два подсписка,

[(1,3), (1,4), (1,5)]
[(2,3), (2,4), (2,5)]

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

Вы можете создать такой список следующим образом:

• Если какой-либо список ввода пуст, результат будет пустым.
• В противном случае:
  1. Возьмите первый элемент a и соедините его с каждым элементомb в списке (подсказка: подумайте о map.)
  2. Рекурсивно создавайте пары из хвоста a и всех b.
  3. Объедините результаты 1и 2.

При сопоставлении с образцом:

fun pair ([], _) = []
  | pair (_, []) = []
  | pair (x::xs, ys) = <something involving x and ys, suitably combined with 'pairs (xs, ys)'> 

Может помочь, если вы напишитешаг 1 как отдельная функция.

Answer 2

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

То, что вы пытаетесь сгенерировать, называется декартовым произведением двух списков.

Ваш текущий подход (отформатированный немного лучше),

fun pair (a, b) =
  if null a then nil else
  if null b then nil else
  (hd a, hd b) :: pair (a, tl b) @ pair (tl a, b);

дает повторяющиеся результаты в дальнейшем, потому что вы пропускаете hd b в pair (a, tl b) и оставляете hd a в pair (b, tl a), но на второй итерации, например, pair (a, tl b), первый элемент a обрабатывается еще раз для каждого оставшегося элемента tl b.

Вы можете избежать этого дублирования работы, обратившись к каждому элементу раз .Я бы порекомендовал вам взглянуть на функции map и concat.Общий подход таков: для каждого элемента x из a сгенерируйте (x,y) для каждого элемента y из b.«Для каждого элемента» это map.И

map (fn x => ...something with (x,y)...) a

производит список результатов, так же, как вы хотите.Но если вы повторите тот же подход с map (fn y => ...) b, что и с ...something with (x,y)..., вы столкнетесь с неудобным сюрпризом, с которым concat может помочь вам.

Вы можете выполнить это упражнение, не используя map и concat и вместо этого используют ручную рекурсию, но вам, возможно, придется разделить работу на две функции, так как вам понадобится одна функция, которая складывается по x из a и, для каждой x, складываетсяодин раз b.Функция map берет часть рекурсии, которую обе эти функции имеют вместе, и позволяет вам писать только то, что у них нет общего.