Вычислите Декартово произведение не
Учитывая два списка, я могу произвести список всех перестановок Декартово произведение этих двух списков:
permute :: [a] -> [a] -> [[a]]
permute xs ys = [ [x, y] | x <- xs, y <- ys ]
Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ]
Как делают я расширяюсь, переставляют так, чтобы вместо того, чтобы брать два списка, это взяло список (длина n) списков и возвратило список списков (длина n)
permute :: [[a]] -> [[a]]
Example> permute [ [1,2], [3,4], [5,6] ]
== [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc
Я ничто не мог найти релевантным на Hoogle.. единственная функция, соответствующая подписи, была transpose, который не производит желаемый вывод.
Править: Я думаю, что версией с 2 списками этого является по существу Декартово произведение, но я не могу перенести голову вокруг реализации Декартова произведения не. Какие-либо указатели?
4 ответа
Prelude> sequence [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
В качестве дополнения к ответу jleedev (не смог отформатировать это в комментариях):
Быстрая неконтролируемая замена функций списка на монадические:
sequence ms = foldr k (return []) ms
where
k m m' = do { x <- m; xs <- m'; return (x:xs) }
....
k m m' = m >>= \x -> m' >>= \xs -> [x:xs]
k m m' = flip concatMap m $ \x -> flip concatMap m' $ \xs -> [x:xs]
k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m
....
sequence ms = foldr k ([[]]) ms
where
k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m
Если вы хотите иметь больше контроля над выводом, вы можете использовать список как аппликативный функтор, например:
(\x y z -> [x,y,z]) <$> [1,2] <*> [4,5] <*> [6,7]
Допустим, вы хотите получить список кортежей:
(\x y z -> (x,y,z)) <$> [1,2] <*> [4,5] <*> [6,7]
И это тоже выглядит круто...
Я нашел статью Эрика Липперта о вычислении декартова произведения с LINQ весьма полезной для улучшения моего понимания происходящего. Вот более или менее прямой перевод:
cartesianProduct :: [[a]] -> [[a]]
cartesianProduct sequences = foldr aggregator [[]] sequences
where aggregator sequence accumulator =
[ item:accseq |item <- sequence, accseq <- accumulator ]
Или с более лаконичными, бессмысленными именами параметров "Haskell-y";)
cartesianProduct = foldr f [[]]
where f l a = [ x:xs | x <- l, xs <- a ]
В конце концов, это очень похоже на опубликованный sclv.