3

我还有另一个关于从各种来源生成东西列表的问题。

更新：简化示例

我有一个变量列表

["a", "b", "c"]

和布尔值

[False, True].

现在我想要一个列表，其中变量列表的所有子序列与值列表交叉，因此对于每个条目，变量的子序列列表具有一组与每个可能值的对。

对于上面的列表，我会得到这个（这个场景的完整列表）。由于空列表不会与另一个列表配对得很好，我不在乎它是否是结果列表的一部分（以后可以轻松添加）。

[
    [], 
    [("a", False)], 
    [("a", True)], 
    [("b", False)], 
    [("b", True)], 
    [("c", False)], 
    [("c", True)],
    [("a", False), ("b", False)],
    [("a", False), ("b", True)],
    [("a", True), ("b", False)],
    [("a", True), ("b", True)],
    [("a", False), ("c", False)],
    [("a", False), ("c", True)],
    [("a", True), ("c", False)],
    [("a", True), ("c", True)],
    [("b", False), ("c", False)],
    [("b", False), ("c", True)],
    [("b", True), ("c", False)],
    [("b", True), ("c", True)],
    [("a", False), ("b", False), ("c", False)],
    [("a", False), ("b", False), ("c", True)],
    [("a", False), ("b", True), ("c", False)],
    [("a", False), ("b", True), ("c", True)],
    [("a", True), ("b", False), ("c", False)],
    [("a", True), ("b", False), ("c", True)],
    [("a", True), ("b", True), ("c", False)],
    [("a", True), ("b", True), ("c", True)],
]

如果只是排列，则调用排列结合理解就足够了，但我不知道如何轻松获取子序列的列表。我可以在不同大小的列表上使用“调用排列+理解”方法，但这听起来不太优雅。

有没有直接的解决方案？

4

4 回答 4

3 
import Control.Monad (forM)
import Data.List (subsequences)

solution :: [a] -> [b] -> [[(a, b)]]
solution variables values = do
    sequence <- subsequences variables
    forM sequence $ \variable -> do
        value <- values
        return (variable, value)

证明它有效：

>>> mapM_ print $ solution ["a", "b", "c"] [False, True]
[]
[("a",False)]
[("a",True)]
[("b",False)]
[("b",True)]
[("a",False),("b",False)]
[("a",False),("b",True)]
[("a",True),("b",False)]
[("a",True),("b",True)]
[("c",False)]
[("c",True)]
[("a",False),("c",False)]
[("a",False),("c",True)]
[("a",True),("c",False)]
[("a",True),("c",True)]
[("b",False),("c",False)]
[("b",False),("c",True)]
[("b",True),("c",False)]
[("b",True),("c",True)]
[("a",False),("b",False),("c",False)]
[("a",False),("b",False),("c",True)]
[("a",False),("b",True),("c",False)]
[("a",False),("b",True),("c",True)]
[("a",True),("b",False),("c",False)]
[("a",True),("b",False),("c",True)]
[("a",True),("b",True),("c",False)]
[("a",True),("b",True),("c",True)]
于 2013-08-09T16:25:21.297 回答
1 
solution :: [a] -> [b] -> [[(a, b)]]
solution variables values = do
  as <- subsequences variables
  bs <- forM as $ const values
  zip as bs

为了证明它有效：

Data.List Control.Monad Prelude> :{
Data.List Control.Monad Prelude| let solution :: [a] -> [b] -> [[(a, b)]]
Data.List Control.Monad Prelude|     solution variables values = do
Data.List Control.Monad Prelude|       as <- subsequences variables
Data.List Control.Monad Prelude|       bs <- forM as $ const values
Data.List Control.Monad Prelude|       return $ zip as bs
Data.List Control.Monad Prelude| :}
Data.List Control.Monad Prelude> solution [ "a", "b", "c" ] [ False, True ]
[[],[("a",False)],[("a",True)],[("b",False)],[("b",True)],[("a",False),("b",False)],[("a",False),("b",True)],[("a",True),("b",False)],[("a",True),("b",True)],[("c",False)],[("c",True)],[("a",False),("c",False)],[("a",False),("c",True)],[("a",True),("c",False)],[("a",True),("c",True)],[("b",False),("c",False)],[("b",False),("c",True)],[("b",True),("c",False)],[("b",True),("c",True)],[("a",False),("b",False),("c",False)],[("a",False),("b",False),("c",True)],[("a",False),("b",True),("c",False)],[("a",False),("b",True),("c",True)],[("a",True),("b",False),("c",False)],[("a",True),("b",False),("c",True)],[("a",True),("b",True),("c",False)],[("a",True),("b",True),("c",True)]]
Data.List Control.Monad Prelude> forM_ it print
[]
[("a",False)]
[("a",True)]
[("b",False)]
[("b",True)]
[("a",False),("b",False)]
[("a",False),("b",True)]
[("a",True),("b",False)]
[("a",True),("b",True)]
[("c",False)]
[("c",True)]
[("a",False),("c",False)]
[("a",False),("c",True)]
[("a",True),("c",False)]
[("a",True),("c",True)]
[("b",False),("c",False)]
[("b",False),("c",True)]
[("b",True),("c",False)]
[("b",True),("c",True)]
[("a",False),("b",False),("c",False)]
[("a",False),("b",False),("c",True)]
[("a",False),("b",True),("c",False)]
[("a",False),("b",True),("c",True)]
[("a",True),("b",False),("c",False)]
[("a",True),("b",False),("c",True)]
[("a",True),("b",True),("c",False)]
[("a",True),("b",True),("c",True)]
于 2013-08-09T20:37:53.300 回答
0

生成给定列表的所有子序列（不考虑性能）的简单解决方案是：

subs :: [a] -> [[a]]
subs []      =  [[]]
subs (x:xs)  =  subs xs ++ map (x:) (subs xs)
于 2013-08-09T12:18:31.693 回答
0

实际上这里没有必要使用 monad。下面的内容一开始可能有点吓人，但我会在后面解释。注意：映射和折叠有助于编译器更快地编写代码。

solution :: [a] -> [b] -> [[(a, b)]]
solution variables values = foldr (<*>) [[]]
  $ map (\variable -> id : map (\value -> (:) (variable, value) ) values)
  $ variables

它需要Control.Applicative.

这个想法是选择子序列并将所有可能的值分配为一个过程。该函数(\value -> (:) (variable, value) ) :: b -> [(a,b)]->[(a,b)]接受一个值，与一个变量组成一对，并生成一个函数，将该对附加到一个变量值对列表中。

通过将它映射到所有值的列表，我们得到一个函数列表map (\value -> (:) (variable, value) ) values :: [[(a,b)]->[(a,b)]]。外部列表括号用于非确定性，内部用于绑定列表。

我们添加了另一个选项：不分配值。这是由 完成的id :: [(a,b)]->[(a,b)]，它被添加到可能性列表中。

下一个 lambda-abstraction-and-map 构造将不同的变量考虑在内：我们希望为每个变量提供一个可能更改的列表。

map (\variable -> (id : map (\value -> (:) (variable, value) ) values)) variables

具有类型[[[(a,b)]->[(a,b)]]]，其中最外层列表用于要绑定的变量，中间层用于不确定性，内部列表用于已绑定的变量。

然后终于来了大事：折叠！折叠适用于最外层的列表层（为每个变量做某事），这种列表级别消失了。结合了所有不确定性，这是之前列表的(<*>)中间层，是结果的外层。内层不受影响。折叠的起始值为[[]]::[[(a,b)]]。

如果您习惯了不Alternative确定性的界面，您可能更喜欢

solution :: Alternative f => [a] -> f b -> f[(a, b)]
solution variables values = foldr (<*>) (pure [])
  $ map (\variable -> pure id <|> pure (\value -> (:) (variable, value)) <*> values)
  $ variables

因为现在列表操作(:)和map用于变量列表，而与非确定性有关的所有内容都由应用程序/替代接口处理。

于 2013-08-13T15:57:54.547 回答