Реализация ЛифтМ2 в Хаскеле

Question

Для упражнения я пытался реализовать liftM2, используя только функции ap и liftM. Функции определены как:

ap :: IO (a -> b) -> IO a -> IO b
liftM :: (a -> b) -> IO a -> IO b

liftM2 :: (a -> b -> c) -> IO a -> IO b -> IO c

Я легко могу сделать liftM2 используя нотацию do, но не знаю, как это сделать, просто используя ap и liftM. Я думал о том, что результат будет выглядеть примерно так:

liftM2 f a b = liftM (_) (ap _ a)

Я запутался в том, как связываться с f, который (a -> b -> c) таков, что я могу просто повернуть a к b и b к c. Спасибо.

Answer 1

Я думаю, стоит отметить, что ваше первоначальное предположение,

liftM2 f a b = liftM (_) (ap _ a)

не так уж далеко. Но ap не совсем то место, с которого нужно начинать. Скорее рассмотрим

pairIO :: IO a -> IO b -> IO (a, b)
pairIO m n = do
  a <- m
  b <- n
  return (a, b)

Теперь вы можете написать

liftM2 :: (a -> b -> c) -> IO a -> IO b -> IO c
liftM2 f m n = liftM _ (pairIO m n)

GHC скажет вам, что ему нужно

_ :: (a, b) -> c

и вы сможете заполнить это очень легко.

Это фактически отражает распространенную альтернативную формулировку понятия «аппликативный функтор»:

class Functor f => Monoidal f where
  pur :: a -> f a
  pair :: f a -> f b -> f (a, b)

Этот класс по мощности эквивалентен стандартному Applicative классу.

---

Оказывается, что вы действительно можете комбинировать действия различными способами, благодаря Monoidal ассоциативному закону. Это выглядит как

xs `pair` (ys `pair` zs) = jigger <$> ((xs `pair` ys) `pair` z's)
   where
     jigger ((x, y), z) = (x, (y, z))

Answer 2

С ap :: IO (a -> b) -> IO a -> IO b у нас есть оба

  IO (a -> b)         {- and -}       IO (a -> b -> c)
  IO  a                               IO  a
  -----------                         ----------------
  IO       b                          IO      (b -> c)

, таким образом, мы можем объединить два значения IO с двоичной функцией IO через

ap2 :: IO (a -> b -> c) -> IO a -> IO b -> IO c
ap2 mf mx my = ap mf mx `ap` my

             IO (a -> b -> c)
             IO  a
             ----------------
             IO      (b -> c)
             IO       b
             ----------------
             IO            c

или с чистой двоичной функцией,

liftM2 :: (a -> b -> c) -> IO a -> IO b -> IO c
liftM2 f mx my = ap2 (return f) mx my
               = ap (return f) mx `ap` my
               = (ap . return) f mx `ap` my

А какой тип ap . return?

> :t ap . return
ap . return :: Monad m => (a -> b) -> m a -> m b

Почему это тип liftM! (здесь более конкретный (a -> b -> c) -> IO a -> IO (b -> c))

              = liftM f mx `ap` my

Answer 3

Общая картина трансформируется

liftMn f a1 ... an

в

f <$> a1 <*> ... <*> an
-- i.e., more precisely
(... ((f <$> a1) <*> a2) ... <*> an)

, где <$> равно liftM (AKA fmap) и <*> равно ap.

Следовательно, для n=2 получаем

(f `liftM` a1) `ap` a2
-- i.e.
ap (liftM f a1) a2

Проверка типов:

f :: t1 -> t2 -> r
liftM f :: IO t1 -> IO (t2 -> r)
a1 :: IO t1
liftM f a1 :: IO (t2 -> r)
ap (liftM f a1) :: IO t2 -> IO r
a2 :: IO t2
ap (liftM f a1) a2 :: IO r

Ключевой идеей здесь является чтение f :: t1 -> t2 -> r как f :: t1 -> (t2 -> r), так что следует liftM f :: IO t1 -> IO (t2 -> r). Обратите внимание на тип функции внутри IO. Затем мы можем «распределить» IO по ->, используя ap, чтобы мы могли применить a2 :: IO t2.