Haskell алгоритм последовательности кортежей в списке списков

Question

Я играл вокруг немного в Haskell, чтобы ознакомиться с ним, но застрял на следующей задаче:

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

*Main> foo 
    [ 
     [ (1,2), (3,4) ], 
     [ (5,6)   ], 
     [ (7,8), (9,10) ] 
    ] 


    = [ 
     [ (1,2), (5,6), (7,8) ], 
     [ (1,2), (5,6), (9,10) ], 
     [ (3,4), (5,6), (7,8) ], 
     [ (3,4), (5,6), (9,10) ] 
    ] 

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

Я пытался написать для этого рекурсивный алгоритм, но не могу обернуть голову вокруг работы с количеством N других списков, чтобы комбинировать кортежи с. Для всего два списка кортежей, я хотел бы написать что-то вроде:

composeList [] _  = [] 
composeList (x:xs) list = composeTuples x list ++ composeList xs list 

composeTuples _ []  = [] 
composeTuples t (x:xs) = [t,x] : composeTuples t xs 

Это дает мне:

*Main Data.List> composeList [(1,2),(3,4)] [(5,6),(7,8)] 

    [ 
     [ (1,2), (5,6) ], 
     [ (1,2), (7,8) ], 
     [ (3,4), (5,6) ], 
     [ (3,4), (7,8) ] 
    ] 

Хотя я не могу положить кусочки вместе и заставить его работать на любом количестве списки, каждый из которых имеет любое (> = 0) количество кортежей.

Я заинтересован в решении этой проблемы с некоторыми предопределенными функциями Haskell (если это возможно), а также с некоторым схожим подходом, как тот, который я собирался в приведенном выше примере.

Заранее благодарен!

Answer 1

Это просто монада-список, выбирая элемент из каждого списка недетерминированным.

Функция вы ищете является sequence :: Monad m => [m a] -> m [a] от Control.Monad

λ. let as = [(1,2),(3,4)] 
λ. let bs = [(5,6)] 
λ. let cs = [(7,8),(9,10)] 
λ. let xss = [as, bs, cs] 
λ. sequence xss 
    [[(1,2),(5,6),(7,8)] 
    ,[(1,2),(5,6),(9,10)] 
    ,[(3,4),(5,6),(7,8)] 
    ,[(3,4),(5,6),(9,10)] 
    ] 

Answer 2

Вот рекурсивное решение

solution :: [[a]] -> [[a]] 
solution (x: xs) = [y: ys | y <- x, ys <- solution xs] 
solution []  = [[]] 

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