Powerset功能1-班轮 [英] Powerset Function 1-Liner

问题描述

学习你一个Haskell 演示 powerset 函数：

lockquote
某些集合的 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 函数。

解决方案

  powerset :: [a]  - > [[a]] 
 powerset xs = filterM（\ x  - > [True，False]）xs 
 ------------- ----- 
 filterM :: Monad m => （a  - > m Bool） - > [a]  - > m [a] 
  -  filter ::（a  - > Bool） - > [a]  - > [a]（仅供比较）
 ------------- ----- 
m Bool〜[Bool] m〜[] 
  
 
 $ b 
所以这是过滤器在非确定性（列表）monad中。
 
 
 
通常情况下，过滤器只保留其谓词所保留的输入列表中的元素。
 
 
 
非确定性地，我们得到保留非确定性谓词可能持有的元素的所有可能性，以及删除可能不适用的元素的可能性。在这里，任何元素都是如此，所以我们可以获得保留或删除元素的所有可能性。
 
 
 
这是一个powerset。
 
 
 
 
 
 
另一个例子（在不同的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 even x then Just True else Just False）[2..8] 
只是[2,4,6,8] 
  
 
 
 
 
 
 
让我们看看如何通过代码实现它。我们将定义 
 
 
  filter_M :: Monad m => （a  - > m Bool） - > [a]  - > [$] b 
 
 
 $ b $返回[] 
 filter_M p（x：xs）= px>> =（\ b  - > 
如果b 
然后filter_M p xs>> =（return。（x :)）
 else filter_M p xs）
  
写出monad对 return 和bind（>> = ）的定义即 return x = [x] ， xs>> = f = concatMap f xs ）， / p> 
 
 
  filter_L ::（a  - > [Bool]） - > [a]  - > [b] 
 filter_Lp [] = [[]] 
 filter_Lp（x：xs） -  =（`concatMap` px）（\b-> 
  -  - （如果b然后映射（x :) else id）$ filter_L p xs）
  - 语义上与
  -  map相同（如果b则（x :) else id）$。 .. 
 = [如果b则x：r else r | b < -  px，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）
  - 结果排序：
 = [如果b则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] ）。否则，对于相同的输入值，测试会一遍又一遍地被评估，而且我们可能不会那么想。  
Learn You a Haskell demonstrates the powerset function:

  
The powerset of some set is a set of all subsets of that set.


powerset :: [a] -> [[a]]  
powerset xs = filterM (\x -> [True, False]) xs
And running it:
ghci> powerset [1,2,3]                    
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
What's going on here? I see filterM's signature (shown below), but I don't understand how it's executing.


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

Please walk me through this powerset function.
解决方案
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 ~ []
So this is filter "in" the nondeterminism (list) monad.

Normally, filter keeps only those elements in its input list for which the predicate holds.

Nondeterministically, we get all the possibilities of keeping the elements for which the nondeterministic predicate might hold, and removing those for which it might not hold. Here, it is so for any element, so we get all the possibilities of keeping, or removing, an element.

Which is a powerset.



Another example (in a different monad), building on the one in Brent Yorgey's blog post mentioned in the comments,
  >> 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]




Let's see how this is actually achieved, with code. We'll define
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 )
Writing out the list monad's definitions for return and bind (>>=) (i.e. return x = [x], xs >>= f = concatMap f xs), this becomes
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 ]
Hence, 
-- 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] ]
and we have thus derived the two usual implementations of powerset function. 

The flipped order of processing is made possible by the fact that the predicate is constant (const [True, False]). Otherwise the test would be evaluated over and over again for the same input value, and we probably wouldn't want that. 

                        
这篇关于Powerset功能1-班轮的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！