幂集函数1行代码

Question

幂集函数1行代码

30

Learn You a 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函数。

- Kevin Meredith

9

也许你应该自己尝试一下？在这个例子中，m是什么？如果展开单子操作，filterM会变成什么？ - augustss

10

http://byorgey.wordpress.com/2007/06/26/deducing-code-from-types-filterm/ - DaoWen

2

好观点 @augustss。好链接，DaoWen。我现在要尝试实现 filterM。 - Kevin Meredith

1

这里有一个关于此事的讨论在 Reddit 上。 - Will Ness

3个回答

8

让我来帮助你解决这个问题：

first: you have to understand the list monad. If you remember, we have:

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

The result will be: [(1,'a'),(1,'b'),(2,'a'),(2,'b')]

Because: xs >>= f = concat (map f xs) and 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')]

second: we have the implementation of filterM:

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

Let do an example for you to grasp the idea easier:

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

The innermost recursion of filterM: x = 3

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

You see the similarity, like the example above we have:

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], [] ]

Likewise:

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], [] ]

theoretically: it's just chaining list monads after all:

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

希望这些内容对您有所帮助：D

- Vũ Tô

1

理解列表单子中的filterM（就像您的示例中一样）最好的方法是考虑以下替代伪代码式的filterM定义：

filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]
filterM p [x1, x2, .... xn] = do
                  b1 <- p x1
                  b2 <- p x2
                  ...
                  bn <- p xn
                  let element_flag_pairs = zip [x1,x2...xn] [b1,b2...bn]
                  return [ x | (x, True) <- element_flag_pairs]

使用这个filterM的定义，您可以轻松地看到为什么在您的示例中生成了幂集。

为了完整起见，您可能还会对如何像上面那样定义foldM和mapM感兴趣。

mapM :: Monad m => (a -> m b) -> [a] -> m [ b ]
mapM f [x1, x2, ... xn] = do
                   y1 <- f x1
                   y2 <- f x2
                   ...
                   yn <- f xn
                   return [y1,y2,...yn]

foldM :: Monad m => (b -> a -> m b) -> b -> [ a ] -> m b
foldM _ a [] = return a
foldM f a [x1,x2,..xn] = do
               y1 <- f a x1
               y2 <- f y1 x2
               y3 <- f y2 x3
               ...
               yn <- f y_(n-1) xn
               return yn

希望这能帮到你！

- smilingbuddha

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Will Ness · Accepted Answer

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是在不确定性（列表）单子中的。

通常情况下，filter保留其输入列表中谓词成立的元素。

在不确定情况下，我们得到了保留可能满足不确定谓词的元素和删除可能不满足该谓词的元素所有可能性。对于任何元素都是如此，在这里我们得到保留或删除元素的所有可能性。

这就是一个幂集。

另一个例子（在不同的单子中），建立在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和绑定(>>=)的定义(即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])，我们可以实现处理顺序的翻转。否则测试将一遍又一遍地对相同的输入值进行评估，这可能不是我们想要的。