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
函数。
发布于 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]
),使得处理的顺序颠倒成为可能。否则,对于相同的输入值,测试将被一次又一次地评估,而我们可能不希望这样。
发布于 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')
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,[] ]
filterM ::(a -> m Bool) -> a -> m a -> a -> [a ]
这就是全部,希望你喜欢:D
发布于 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
复制相似问题