Функция Powerset 1-Liner

Ответ 1

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 "в" монаде недетерминизма (списка).

Обычно фильтр сохраняет в своем входном списке только те элементы, для которых содержит предикат.

Недетерминистически, мы получаем все возможности для сохранения элементов, для которых может храниться недетерминированный предикат, и удаления тех элементов, для которых он может не сохраняться. Здесь это так для любого элемента, поэтому мы получаем все возможности сохранить или удалить элемент.

Который является powerset.

Другой пример (в другой монаде), основанный на том, что упоминается в комментариях в блоге 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 и bind (>>=) (т.е. 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]). В противном случае тест будет оцениваться снова и снова для одного и того же входного значения, и мы, вероятно, этого не хотим.

Ответ 2

позвольте мне помочь вам об этом:

• first: вам нужно понять монаду списка. Если вы помните, у нас есть:

  do
    n  <- [1,2]  
    ch <- ['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')] ]
       [(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: у нас есть реализация filterM:

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

  Сделайте пример, чтобы вы поняли эту идею:

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

  Самая внутренняя рекурсия фильтра М: x = 3

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

  Вы видите сходство, как в приведенном выше примере:

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

  Аналогично:

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

• Теоретически: он просто цепляет список монад в конце концов:

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

И все, надеюсь, вам понравится: D

Ответ 3

Лучший способ понять 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

Надеюсь это поможет!