DrRacket Объединение списков

Question

Я надеялся, что кто-то может направить меня в правильном направлении: я ищу два, которые производят все возможные комбинации элементов в двух списках:
Пример:
С учетом списков '(symbol1 symbol2) и' (1 2), Я хочу произвести:
(список (список 'symbol1 1) (список' symbol1 2) (список 'symbol2 1) (список symbol2 2))

Пока мой код:

    (define (combiner list1 list2)
    (list
      (foldr (lambda (a b) (foldr (lambda (c d) (list a c)) empty list1)) empty list2)
      (foldr (lambda (a b) (foldr (lambda (c d) (list b d)) empty list1)) empty list2)))

Это явно не работает, равно как и несколько других методов, которые я пробовал.У меня возникают проблемы при работе с неявной рекурсией в двух списках - есть идеи?

Answer 1

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

Answer 2

Я думал о другом возможном способе решения проблемы. Вот подсказка:

(define (combiner list1 list2)
  (define (combine l1 l2)
    (cond ((empty? l1) empty)
          ((empty? l2) XXX)
          (else (cons YYY
                      ZZZ))))
  (combine list1 list2))

В приведенном выше фрагменте кода вам нужно будет найти ответ на три вопроса:

• XXX Как продвигать рекурсию, когда вы завершили итерацию по второму списку, но в первом списке все еще есть элементы, а также вы хотите продвинуть один элемент в первом списке?
• YYY Как бы вы объединили элемент из первого списка с элементом из второго списка?
• ZZZ Как вы продвигаете рекурсию, когда в обоих списках все еще остаются элементы, но на данный момент вы заинтересованы только в продвижении по второму списку?

Последний совет: обратите внимание, что в какой-то момент вам необходимо «перезапустить» второй список, для этого вы можете обратиться к исходному list2, который не изменился вообще.

Надеюсь, это поможет вам, я не хочу давать вам прямой ответ (пока) - я хочу, чтобы вы сами нашли решение.

Answer 3

Кажется, что одна вещь, которая может добавить здесь путаницу, это либеральное использование list. Я собираюсь начать подходить к вашей проблеме, используя нотацию Haskell для типов. :: означает «имеет тип», а [Foo] означает «список Foo».

list1 :: [Symbol]
list2 :: [Number]
type Pair = (Symbol, Number)
(combiner list1 list2) :: [Pair]

Теперь похоже, что вы хотите решить эту проблему с помощью foldr over list2.

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr требует step :: a -> b -> b и start :: b. Поскольку мы хотим, чтобы конечный результат был [Pair], это означает, что b = [Pair]. start, вероятно, будет пустым списком. Поскольку list2 заполняет слот [a], это означает, что a = Number. Поэтому для нашей задачи step :: Number -> [Pair] -> [Pair]

combiner :: [Symbol] -> [Number] -> [Pair]
combiner list1 list2 = foldr step start list2
  where step :: Number -> [Pair] -> [Pair]
        step a b = undefined
        start = []

Пока это то же самое, что и foldr, который вы написали, за исключением того, что я еще не определил step. Так, какова функция шага? От типа мы знаем, что оно должно взять Number и [Pair] и произвести [Pair]. Но что означают эти данные? Ну, вход Number будет некоторым элементом list2. И вход [Pair] будет «результатом сгиба». Итак, мы хотим взять наши Number и сделать что-то , чтобы создать для него Pair, а затем наложить их на результат. Это Точка, в которой мой код начинает отличаться от вашего.

step a b = append (doSomething a) b
doSomething :: Number -> [Pair]
doSomething a = undefined

Поскольку вы, используя Racket, вероятно, определите doSomething как анонимную функцию, это означает, что list1 находится в области видимости. (Так как он находится в предложении where функции в Haskell, он находится в области видимости). Вы, вероятно, будете использовать этот список для генерации комбинаций.

doSomething a = ... a ... list1 ...

Реализация doSomething оставлена ​​как упражнение для читателя, так же как и перевод обратно в Racket. Обратите внимание, что сигнатура типа для функции Haskell, которую я здесь определяю, combiner, может быть обобщена до [a] -> [b] -> [(a,b)].