Почему это два эквивалента?

Question

Я не совсем понимаю, почему данные двух списков списков xss :: [[a]] и yss :: [[a]]

liftA2 (++) xss yss

эквивалентны

[xs ++ ys | xs <- xss, ys <- yss]

Answer 1

Причина - прямо здесь в исходном коде.

instance Applicative [] where
    pure x    = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
    liftA2 f xs ys = [f x y | x <- xs, y <- ys]

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

liftA2 f x y = f <$> x <*> y

Так что

liftA2 (++) xs ys
   = (++) <$> xs <*> ys
   = fmap (++) xs <*> ys                  -- definition of <$> 
   = [ f y | f <- fmap (++) xs, y <- ys ] -- definition of <*> above
   = [ (++) x y | x <- xs, y <- ys ]      -- some law about fmap/bind
   = [ x ++ y | x <- xs, y <- ys ]

Вот, что у вас есть.

---

"Какой-то закон о fmap / bind" таков:

fmap f x >>= t = x >>= t . f

, который применяется, если вы понимаете, как разбираются списки. Доказательство:

fmap f x >>= t
    = x >>= pure . f >>= t             -- <a href="/9927590/dolzhny-li-monadlift-liftm-i-funktorialnoe-fmap-byt-ekvivalentnymi">fmap = liftM coherence</a>
    = x >>= (\y -> pure (f y) >>= t)   -- definition of (.)
    = x >>= (\y -> t (f y))            -- left unit monad law
    = x >>= t . f                      -- definition of (.)

Answer 2

Именно поэтому я не люблю использовать функции типа liftA<2..n>. Они являются абстракцией над абстракцией монады. Это так, потому что аппликатив вводится после монад, чтобы упростить контекст монад, которые содержат функциональные значения (функции).

В основном liftA2 (++) xs ys - это (++) <$> xs <*> ys, что имеет больше смысла, так как включает оператор функтора fmapв линейном виде <$>. Как только вы приступите к механике последнего, liftA2 начинает обретать смысл.

fmap просто применяет функцию (++) к элементам списка xs (предположим, что xs равно [[1,2],[3,4]]) и превращает его в аппликативный список (список, содержащий функции), такой как;

[([1,2] ++), ([3,4] ++)] :: Num a => [[a] -> [a]]

, и аппликативный оператор <*> теперь может применять эти функции в нашем списке к другому списку, который содержитнекоторые другие списки, такие как, скажем, [[1,2],[3,4]].

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

[([1,2] ++), ([3,4] ++)] <*> [[1,2],[3,4]]

оказывается

[[1,2,1,2],[1,2,3,4],[3,4,1,2],[3,4,3,4]]

В целом liftA2 (++) просто поднимает простую функцию (++) в монаду списка. Проще говоря, объединяйте внутренние списки друг с другом монадически.

Сказав, что версия для понимания списков - это шутка в Хаскеле. Это избыточно и его следует избегать, по моему честному мнению. Это просто сводит целую абстракцию монады до уровня списка, тогда как монадические подходы применимы для всех типов данных в соответствии с их соответствующими экземплярами монады.