Вложенное декартово произведение списков Haskell

Я хотел бы создать метод, в котором я мог бы дать ему список длин, и он вернул бы все комбинации декартовых координат до этих длин. Легче объяснить на примере:

cart [2,5]
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ]

cart [2,2,2]
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ]

Простое понимание списка не будет работать, потому что я не знаю, насколько длинными будут списки. Хотя мне нравится простота Haskell во многих задачах, эту задачу я могу написать процедурно (на C или где-то еще) за 5 минут, тогда как Haskell вызывает у меня аневризму!

Решение этой конкретной проблемы очень помогло бы мне; Я также хотел бы услышать о ваших мыслительных процессах, когда вы занимаетесь подобными вещами.


cartesian-product list-comprehension haskell
person cspyr0    schedule 11.04.2010    source источник
comment
Вау, спасибо Кенни и Дэйву. Я никогда не думал добавить рекурсивный вызов в определение понимания списка - очень круто. Версия с использованием карты и сгиба великолепна. Я стараюсь использовать функции более высокого порядка, когда могу придумать способ, так что это отличный пример для изучения!   -  person cspyr0    schedule 11.04.2010
comment
пока вы используете функции более высокого порядка, знайте, что это не должно быть загадочно. и использование правильных функций поможет вам в этом, sequence — это то, что вам нужно.   -  person yairchu    schedule 11.04.2010
comment
Спасибо, yairchu, за краткое и ясное решение и за то, что познакомил меня с hoogle. Как я без этого обходился?!   -  person cspyr0    schedule 11.04.2010
comment
Еще один интересный инструмент от ndmitchell можно найти на hlint. это предлагает дальнейшее сокращение моего решения, как указал newacct.   -  person yairchu    schedule 12.04.2010

Ответы (3)


arrow_upward
12
arrow_downward

Это можно решить рекурсивно. Во-первых, декартово произведение ничего равно {}:

cart [] = [[]]

(Или определите только 1-элементную форму, если пустой продукт недействителен:

cart [x] = [[i] | i <- [0 .. x-1]]

)

Тогда декартово произведение x:xs можно записать как

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs]

В общем, если вы хотите написать функцию f, которая требует длины списка N, попробуйте придумать способ сделать f(N) зависит от меньших списков, например Только f(N - 1), затем решить базовый случай f(0) или f(1) и т. д. Это преобразует задачу в рекурсия, которая может быть легко решена.

person kennytm    schedule 11.04.2010

arrow_upward
13
arrow_downward

ммм..

cart = sequence . map (enumFromTo 0 . subtract 1)

Разумно ожидать, что функция [[a]] -> [[a]], выполняющая то, что мы ожидаем, уже существует в библиотеке. Поэтому, если кто-то не знаком с sequence, найти его несложно: обманывает это.

Редактировать: как указал newacct:

cart = mapM (enumFromTo 0 . subtract 1)

Это также можно узнать, отправив предыдущее решение в HLint.

person yairchu    schedule 11.04.2010
comment
@newacct: хорошо. кстати, hlint тоже это предлагает :) - person yairchu; 12.04.2010
comment
Вау, забавно, насколько укоренился sequence . map (...) в качестве ответа на такой вопрос, поскольку это была и моя первоначальная реакция. - person Reid Barton; 12.04.2010

arrow_upward
7
arrow_downward

Бьюсь об заклад, ваше процедурное решение будет включать рекурсию. Наше решение на Haskell также будет включать рекурсию.

Итак, рекурсия. Сначала рекурсивный случай.

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart]
  where rcart = cart cs

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

Потом базовый случай.

cart [] = [[]]

Вы можете подумать cart [] = []. Я сделал сначала. Но подумайте о том, что рекурсивный случай требует от базового случая.

person dave4420    schedule 11.04.2010