Вложенное декартово произведение списков 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 дает мне аневризму!
Решение этой определенной проблемы выручило бы меня много; я также любил бы слышать о Ваших мыслительных процессах при занятии материалом как это.
3 ответа
Эту задачу можно решить рекурсивно. Во-первых, декартово произведение ничего есть {∅}:
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) и т. д. Это превращает задачу в рекурсию, которую можно легко решить.
Ммм ..
cart = sequence . map (enumFromTo 0 . subtract 1)
Разумно ожидать, что функция [[a]] -> [[a]] , выполняющая то, что мы ожидаем, уже существует в библиотеке. Так что, если кто-то не знаком с последовательностью , найти ее - это простой вопрос подделки .
Изменить: , как указал newacct:
cart = mapM (enumFromTo 0 . subtract 1)
Это также можно найти, загрузив предыдущее решение в HLint .
Готов поспорить, ваше процедурное решение потребует рекурсии. Наше решение на Haskell также будет включать рекурсию.
Итак, рекурсия. Сначала рекурсивный случай.
cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart]
where rcart = cart cs
Здесь мы просто говорим, что для каждой возможной начальной координаты и каждой возможной комбинации декартовых координат из оставшихся длин мы делаем очевидную вещь - комбинируем координату с оставшимися координатами.
Тогда базовый случай.
cart [] = [[]]
Вы могли подумать тележка [] = [] . Сначала я это сделал. Но подумайте о том, что рекурсивный случай требует от базового.