haskell - Powerset 功能 1-Liner

Question

Learn You a Haskell演示 powerset功能:

The powerset of some set is a set of all subsets of that set.

powerset :: [a] -> [[a]]  
powerset xs = filterM (\x -> [True, False]) xs

并运行它:

ghci> powerset [1,2,3]                    
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

这里发生了什么？我看到了 filterM的签名(如下所示)，但我不明白它是如何执行的。
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
请引导我完成 powerset功能。

Answer 1

powerset ::                                    [a] -> [[a]]  
powerset xs = filterM (\x -> [True, False])    xs
                             -------------            -----
filterM :: Monad m => (a  -> m Bool       ) -> [a] -> m [a]
-- filter  ::         (a ->    Bool       ) -> [a] ->   [a]   (just for comparison)
                             -------------            -----
                             m Bool ~ [Bool]          m ~ []

所以这是 filter “在”非确定性(列表)单子(monad)中。

通常，过滤器只保留其输入列表中谓词所包含的那些元素。

非确定性地，我们获得了保留非确定性谓词可能适用的元素并删除它可能不适用的元素的所有可能性。在这里，任何元素都是如此，因此我们获得了保留或删除元素的所有可能性。

这是一个powerset。

另一个例子(在不同的 monad 中)，建立在 Brent Yorgey's blog post 中的那个之上。评论中提到，

  >> filterM (\x-> if even x then Just True else Nothing) [2,4..8]
Just [2,4,6,8]
  >> filterM (\x-> if even x then Just True else Nothing) [2..8]
Nothing
  >> filterM (\x-> if even x then Just True else Just False) [2..8]
Just [2,4,6,8]

让我们看看这是如何通过代码实际实现的。我们将定义

filter_M :: Monad m => (a -> m Bool) -> [a] -> m [a]
filter_M p []     = return []
filter_M p (x:xs) = p x >>= (\b ->
                if b
                    then filter_M p xs >>= (return . (x:))
                    else filter_M p xs )

写出列表 monad 对 return 的定义并绑定(bind)( >>= )(即 return x = [x] ， xs >>= f = concatMap f xs )，这变成

filter_L :: (a -> [Bool]) -> [a] -> [[a]]
filter_L p [] = [[]]
filter_L p (x:xs) -- = (`concatMap` p x) (\b->
                  --     (if b then map (x:) else id) $ filter_L p xs )
                  -- which is semantically the same as
                  --     map (if b then (x:) else id) $ ... 
   = [ if b then x:r else r | b <- p x, r <- filter_L p xs ]

因此，

-- powerset = filter_L    (\_ -> [True, False])
--            filter_L :: (a  -> [Bool]       ) -> [a] -> [[a]]
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) 
   = [ if b then x:r else r | b <- (\_ -> [True, False]) x, r <- powerset xs ]
   = [ if b then x:r else r | b <- [True, False], r <- powerset xs ]
   = map (x:) (powerset xs) ++ powerset xs    -- (1)
   -- or, with different ordering of the results:
   = [ if b then x:r else r | r <- powerset xs, b <- [True, False] ]
   = powerset xs >>= (\r-> [True,False] >>= (\b-> [x:r|b] ++ [r|not b]))
   = powerset xs >>= (\r-> [x:r,r])
   = concatMap (\r-> [x:r,r]) (powerset xs)   -- (2)
   = concat [ [x:r,r] | r <- powerset xs  ]
   = [ s | r <- powerset xs, s <- [x:r,r] ]

因此我们推导出了 powerset 的两个常用实现。功能。

由于谓词是常数( const [True, False])，因此可以翻转处理顺序。否则，测试将针对相同的输入值一遍又一遍地评估，我们可能不希望这样。