Вложенные декартовы произведения списков 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

Это можно решить рекурсивно. Во-первых, Cartesian product of nothing является {∅}:

cart [] = [[]] 

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

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

)

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

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

---

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

Answer 2

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

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

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

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

Тогда базовый кейс.

cart [] = [[]] 

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

Answer 3

Умм ..

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

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

Edit:, как newacct отметил:

cart = mapM (enumFromTo 0 . subtract 1) 

Это также может быть найден путем подачи предыдущего решения HLint.