Haskell Monad - Как работает Monad в списке?

Question

Чтобы понять Монаду, я придумал следующие определения:

class Applicative' f where
 purea :: a -> f a
 app :: f (a->b) -> f a -> f b

class Applicative' m =>  Monadd m where
 (>>|) :: m a -> (a -> m b) -> m b

instance Applicative' [] where
 purea x = [x]
 app gs xs = [g x | g <- gs, x <- xs]

instance Monadd [] where
 (>>|) xs f = [ y | x <-xs, y <- f x]

Работает как положено:

(>>|) [1,2,3,4] (\x->[(x+1)])
[2,3,4,5]

Я не уверен, как это работает, хотя. Например:

[ y | y <- [[1],[2]]]
[[1],[2]]

Как применение (\x->([x+1]) к каждому элементу списка [1,2,3] приводит к [2,3,4], а не [[2],[3],[4]]

Или, скорее всего, мое замешательство, похоже, связано с непониманием того, как на самом деле работает это утверждение [ y | x <-xs, y <- f x]

Answer 1

Wadler , Школа Haskell , LYAH , HaskellWiki , Quora и многие другие описывают список монада.

Сравните:

• (=<<) :: Monad m => (a -> m b) -> m a -> m b для списков с
• concatMap :: (a -> [b]) -> [a] -> [b] для m = [].

В обычном операторе связывания (>>=) аргументы перевернуты, но в остальном это просто инфикс concatMap.

Или, скорее, мое замешательство, похоже, связано с непониманием того, как на самом деле работает это утверждение:

(>>|) xs f = [ y | x <- xs, y <- f x ]

Поскольку понимание списков эквивалентно экземпляру Monad для списков, это определение является своего рода обманом. Вы в основном говорите, что что-то - это Монада в том же смысле, что и Монада, поэтому у вас остались две проблемы: Понимание списочного понимания и все еще понимание Монады.

Понимание списка может быть очищено от сахара для лучшего понимания:

• Удаление синтаксического сахара: понимание списка в Haskell

В вашем случае заявление может быть написано несколькими другими способами:

• Использование нотации:

  (>>|) xs f = do x <- xs
                  y <- f x
                  return y
  

• Обезвожено использование оператора (>>=):

  (>>|) xs f = xs >>= \x ->
               f x >>= \y ->
               return y
  

• Это может быть сокращено (одна перезапись на строку):

    (>>|) xs f = xs >>= \x -> f x >>= \y -> return y -- eta-reduction
  ≡ (>>|) xs f = xs >>= \x -> f x >>= return         -- monad identity
  ≡ (>>|) xs f = xs >>= \x -> f x                    -- eta-reduction
  ≡ (>>|) xs f = xs >>= f                            -- prefix operator
  ≡ (>>|) xs f = (>>=) xs f                          -- point-free
  ≡ (>>|) = (>>=)
  

Так что, используя списочные выражения, вы на самом деле не объявили новое определение, вы просто полагаетесь на существующее. Если вы хотите, вы можете вместо этого определить instance Monadd [], не полагаясь на существующие экземпляры Monad или списки:

• Использование concatMap:

  instance Monadd [] where
    (>>|) xs f = concatMap f xs
  

• Произносим еще немного:

  instance Monadd [] where
    (>>|) xs f = concat (map f xs)
  

• Это даже больше:

  instance Monadd [] where
    (>>|) [] f = []
    (>>|) (x:xs) f = let ys = f x in ys ++ ((>>|) xs f)
  

Класс типа Monadd должен иметь что-то похожее на return. Я не уверен, почему это отсутствует.

Answer 2

Список пониманий похож на вложенные циклы:

   xs >>| foo = [ y | x <- xs, y <- foo x]

--            =   for x in xs:
--                         for y in (foo x):
--                               yield y

Таким образом, мы имеем

[1,2,3,4] >>| (\x -> [x, x+10])
=
[ y | x <- [1,2,3,4], y <- (\x -> [x, x+10]) x]
=
[ y | x <- [1] ++ [2,3,4], y <- [x, x+10]]
=
[ y | x <- [1], y <- [x, x+10]] ++ [ y | x <- [2,3,4], y <- [x, x+10]]  -- (*)
=
[ y |           y <- [1, 1+10]]   ++ [ y | x <- [2,3,4], y <- [x, x+10]]
=
[ y | y <- [1]] ++ [ y | y <- [11]] ++ [ y | x <- [2,3,4], y <- [x, x+10]]
=
[1] ++ [11] ++ [ y | x <- [2,3,4], y <- [x, x+10]]
=
[1, 11] ++ [2, 12] ++ [ y | x <- [3,4], y <- [x, x+10]]
=
[1, 11] ++ [2, 12] ++ [3, 13] ++ [ y | x <- [4], y <- [x, x+10]]
=
[1, 11] ++ [2, 12] ++ [3, 13] ++ [4, 14]

Важный шаг отмечен (*). Вы можете принять это как определение того, что список пониманий .

Особый случай, когда функция foo возвращает одноэлементный список, как в вашем вопросе. Тогда это действительно равносильно отображению , поскольку каждый элемент в списке ввода превращается в один (преобразованный) элемент в списке вывода.

Но понимание списка более мощное. Элемент ввода также можно условно превратить в элементы без (работающие как filter ) или в несколько элементов:

  [ a,          [a1, a2] ++        concat [ [a1, a2],         [  a1, a2,
    b,    ==>   [b1]     ++    ==           [b1],        ==      b1,
    c,          []       ++                 [],
    d ]         [d1, d2]                    [d1, d2] ]           d1, d2  ]

Выше эквивалентно

    concat (map foo [a,b,c,d]) 
    =  
    foo a ++ foo b ++ foo c ++ foo d

для некоторых подходящих foo.

concat - это список монад join, а map - список монад fmap. В общем, для любой монады

    m >>= foo  =  join (fmap foo m)

Суть Монады заключается в следующем: из каждой сущности "в" "структуре", условно создавая новые элементы в той же структуре и объединяя их на месте:

[     a     ,  b   ,  c  ,    d      ]
    /   \      |      |     /   \
[  [a1, a2] , [b1] ,  [] , [d1, d2]  ]  -- fmap foo    = [foo x | x <- xs]
                                        --             =     [y | x <- xs, y <- [foo x]]
[   a1, a2  ,  b1  ,        d1, d2   ]  -- join (fmap foo) = [y | x <- xs, y <-  foo x ]

Answer 3

Монады часто легче понять с помощью «математического определения», чем с помощью методов стандартного класса Haskell. А именно,

class Applicative' m => Monadd m where
  join :: m (m a) -> m a

Обратите внимание, что вы можете реализовать стандартную версию с точки зрения этого, наоборот:

join mma = mma >>= id

ma >>= f = join (fmap f ma)

Для списков, join (он же concat) особенно прост:

join :: [[a]] -> [a]
join xss = [x | xs <- xss, x <- xs]  -- xss::[[a]], xs::[a]
-- join [[1],[2]] ≡ [1,2]

В примере, который вас смущает, вы получите

[1,2,3,4] >>= \x->[(x+1)]
  ≡   join $ fmap (\x->[(x+1)]) [1,2,3,4]
  ≡   join [[1+1], [2+1], [3+1], [4+1]]
  ≡   join [[2],[3],[4],[5]]
  ≡   [2,3,4,5]