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

这只是列表monad,非确定性地从每个列表中选择一个元素.

你正在寻找的功能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)]
  ]