Powerset功能1-Liner

Question

了解一下Haskell演示了这个powerset功能:

在powerset某组是一组一组的所有子集.

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中.

通常,过滤器仅保留谓词所在的输入列表中的那些元素.

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

这是一个特权.

另一个例子(在另一个monad中),建立在评论中提到的Brent Yorgey的博客文章中,

  >> 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 )

写出名单单子的定义,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])的事实使得处理的翻转顺序成为可能.否则,将对相同的输入值反复评估测试,我们可能不希望这样.

Answer 2

让我帮你解决这个问题:

• 第一:你必须了解monad列表.如果你还记得,我们有:

  do
    n  <- [1,2]  
    ch <- ['a','b']  
    return (n,ch)
  

  结果将是: [(1,'a'),(1,'b'),(2,'a'),(2,'b')]

  因为:xs >>= f = concat (map f xs)和return x = [x]

  n=1: concat (map (\ch -> return (n,ch)) ['a', 'b'])
       concat ([ [(1,'a')], [(1,'b')] ]
       [(1,'a'),(1,'b')]
  and so forth ...
  the outermost result will be:
       concat ([ [(1,'a'),(1,'b')], [(2,'a'),(2,'b')] ])
       [(1,'a'),(1,'b'),(2,'a'),(2,'b')]
  

• 第二:我们有filterM的实现:

  filterM _ []     =  return []
  filterM p (x:xs) =  do
      flg <- p x
      ys  <- filterM p xs
      return (if flg then x:ys else ys)
  

  让我们举个例子让您更容易理解这个想法:

  filterM (\x -> [True, False]) [1,2,3]
  p is the lambda function and (x:xs) is [1,2,3]
  

  filterM的最内层递归:x = 3

  do
    flg <- [True, False]
    ys  <- [ [] ]
    return (if flg then 3:ys else ys)
  

  你看到了相似之处,就像我们上面的例子一样:

  flg=True: concat (map (\ys -> return (if flg then 3:ys else ys)) [ [] ])
            concat ([ return 3:[] ])
            concat ([ [ [3] ] ])
            [ [3] ]
  and so forth ...
  the final result: [ [3], [] ]
  

  同样:

  x=2:
    do
      flg <- [True, False]
      ys  <- [ [3], [] ]
      return (if flg then 2:ys else ys)
  result: [ [2,3], [2], [3], [] ]
  x=1:
    do
      flg <- [True, False]
      ys  <- [ [2,3], [2], [3], [] ]
      return (if flg then 1:ys else ys)
  result: [ [1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], [] ]
  

• 从理论上说:它毕竟是链接列表monad:

  filterM :: (a -> m Bool) -> [a] -> m [a]
             (a -> [Bool]) -> [a] -> [ [a] ]
  

这就是全部,希望你喜欢:D