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

Question

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

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] ]

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

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

Answer 1

Ммм ..

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

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

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

cart = mapM (enumFromTo 0 . subtract 1)

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

Answer 2

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

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) и т. Д. Это преобразует проблему в рекурсию, которая может быть легко решена.

Answer 3

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

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

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

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

Тогда базовый вариант.

cart [] = [[]]

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