Powerset函数1-线条
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函数。
回答 3
Stack Overflow用户
发布于 2014-08-25 14:21:49
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 "in“非确定性(列表)单子。
通常，filter只在其输入列表中保留谓词有效的那些元素。
在不确定的情况下，我们可以保留不确定谓词可能适用的元素，并删除不确定谓词可能不适用的元素。在这里，任何元素都是如此，所以我们得到了保留或删除元素的所有可能性。
这是一个动力装置。
另一个例子(在不同的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 )写出return和bind (>>=) (即return x = [x]，xs >>= f = concatMap f xs)的列表monad定义，如下所示
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])，使得处理的顺序颠倒成为可能。否则，对于相同的输入值，测试将被一次又一次地评估，而我们可能不希望这样。
Stack Overflow用户
发布于 2017-07-14 22:10:39
让我来帮你解决这个问题：
你必须理解list monad。如果你还记得，我们有：
N <- 1，2ch <- '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')]等等...最外面的结果是: concat ([ [ (1，'a')，(1，'b')，(2，'a')，(2，'b') ]) (1，'a')，(1，'b')，(2，'a')，(2，'b')
- second：我们有filterM的实现：
filterM _ [] = filterM [] return p (x: xs ) = do flg <- p x ys <- filterM p xs return (如果flg则x:ys否则y)
让我们举一个例子，让你更容易掌握这个概念：
filterM (\x ->真，假)1，2，3p是λ函数，(x:xs)是1,2,3
filterM的最里面的递归:x=3
是否返回flg <- True，False ys <- [] ] (if flg则3:ys else ys)
你可以看到相似之处，就像我们上面的例子：
flg=True: concat (map (\ys -> return (if flg then 3:ys else ys)) [ [] ]) concat ([ return 3:[] ]) concat ([ [3] ]) [3]等等...最终结果：[ 3，[] ]
同样：
x=2: do flg <- True，False ys <- [ 3，[] ] return (if flg then 2:ys else ys)结果：[ 2,3，2,3，3，[] ] x=1: do flg <- True，False ys <- [ 2,3，2，3，3，[] ] return (if flg then 1:ys else ys)结果：[ 1, 2，3，1,2，1,3，2，3，2，3，3，[] ]
- theoretically：毕竟它只是一个链表monads：
filterM :：(a -> m Bool) -> a -> m a -> a -> [a ]
这就是全部，希望你喜欢:D
Stack Overflow用户
发布于 2019-04-29 01:26:32
理解list monad的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的定义，您就可以很容易地理解为什么在您的示例中生成power-set。
为了完整起见，您可能还会对如何定义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希望这能有所帮助！
https://stackoverflow.com/questions/25476248
复制相似问题