powerset :: [a] -> [[a]]
powerset xs = filterM (\x -> [True, False]) xs
filterM :: Monad m => (a -> m Bool ) -> [a] -> m [a]
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)
= [ if b then x:r else r | b <- p x, r <- filter_L p xs ]
因此,
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
= [ 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)
= concat [ [x:r,r] | r <- powerset xs ]
= [ s | r <- powerset xs, s <- [x:r,r] ]
我们因此得出了两个通常的 powerset
函数实现。
通过谓词是恒定的 (const [True, False]
),我们可以实现处理顺序的翻转。否则测试将一遍又一遍地对相同的输入值进行评估,这可能不是我们想要的。
m
是什么?如果展开单子操作,filterM
会变成什么? - augustssfilterM
。 - Kevin Meredith