Как ap может быть составлен?

Там я был, записывая функцию, которая принимает значение как вход, вызывает функцию на этом входе, и если результатом этого является Just x, он должен возвращать x; в противном случае он должен вернуть исходный ввод.

Другими словами, эта функция (которую я не знал, что вызывать):

foo :: (a -> Maybe a) -> a -> a
foo f x = fromMaybe x (f x)

Поскольку это похоже на функцию общего назначения, я задавался вопросом, не было ли это еще не определено, поэтому я спросил в Twitter и Крис Аллен ответил, что он ap fromMaybe.

Это звучало многообещающе, поэтому я активировал GHCI и начал экспериментировать:

Prelude Control.Monad Data.Maybe> :type ap
ap :: Monad m => m (a -> b) -> m a -> m b
Prelude Control.Monad Data.Maybe> :type fromMaybe
fromMaybe :: a -> Maybe a -> a
Prelude Control.Monad Data.Maybe> :type ap fromMaybe
ap fromMaybe :: (b -> Maybe b) -> b -> b

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

Но как это работает?

Функция fromMaybe кажется мне понятной, и, в отдельности, я думаю, что понимаю, что делает ap - по крайней мере, в контексте Maybe. Когда m Maybe, он имеет тип Maybe (a -> b) -> Maybe a -> Maybe b.

Я не понимаю, как ap fromMaybe даже компилируется. Для меня это выражение выглядит как частичное приложение, но, возможно, я ошибаюсь. Однако, если это так, я не понимаю, как совпадают типы.

Первый аргумент ap - m (a -> b), но fromMaybe имеет тип a -> Maybe a -> a. Как это соотносится? Какой экземпляр Monad компилятор заключает, что m есть? Как fromMaybe, который принимает два (карриных) аргумента, превращается в функцию, которая принимает один аргумент?

Может кто-нибудь помочь мне подключить точки?

Ответы

Ответ 1

Извинения за лаконичный и механический ответ. Мне не нравятся вишневые вещи, такие как Аппликативные или Монады, но я не знаю, где вы находитесь. Это не мой обычный подход к обучению Haskell.

Во-первых, ap действительно (<*>) под капотом.

Prelude> import Control.Monad
Prelude> import Data.Maybe
Prelude> import Control.Applicative
Prelude> :t ap
ap :: Monad m => m (a -> b) -> m a -> m b
Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Что это значит? Это означает, что нам не нужно что-то "сильное", как Монада, чтобы описать, что мы делаем. Достаточно аппликативного. Однако Functor не делает.

Prelude> :info Applicative
class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
Prelude> :info Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b

Здесь ap/(<*>) с предположительно монадой/аппликацией:

Prelude> ap (Just (+1)) (Just 1)
Just 2
Prelude> (<*>) (Just (+1)) (Just 1)
Just 2

Первое, что нужно выяснить, - это какой экземпляр класса Applicative, о котором мы говорим?

Prelude> :t fromMaybe
fromMaybe :: a -> Maybe a -> a

Desugaring fromMaybe типа немного дает нам:

(->) a (Maybe a -> a)

Итак, конструктор типа, с которым мы здесь связаны, (->). Что говорит GHCi о (->), также известном как типы функций?

Prelude> :info (->)
data (->) a b   -- Defined in ‘GHC.Prim’
instance Monad ((->) r) -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base’
instance Applicative ((->) a) -- Defined in ‘GHC.Base’

Хмм. Что может быть?

Prelude> :info Maybe
data Maybe a = Nothing | Just a     -- Defined in ‘GHC.Base’
instance Monad Maybe -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
instance Applicative Maybe -- Defined in ‘GHC.Base’

Что случилось с использованием (<*>) для Maybe, было следующее:

Prelude> (+1) 1
2
Prelude> (+1) `fmap` Just 1
Just 2
Prelude> Just (+1) <*> Just 1
Just 2
Prelude> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
Prelude> let mFmap = fmap :: (a -> b) -> Maybe a -> Maybe b
Prelude> (+1) `mFmap` Just 1
Just 2
Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
Prelude> let mAp = (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
Prelude> :t (+1)
(+1) :: Num a => a -> a
Prelude> :t Just (+1)
Just (+1) :: Num a => Maybe (a -> a)
Prelude> Just (+1) `mAp` Just 1
Just 2

Хорошо, как насчет функционального типа Functor и Applicative? Одна из сложнейших частей здесь состоит в том, что (->) должен быть частично применен в типе как Functor/Applicative/Monad. Таким образом, ваш f становится (->) a общего (->) a b, где a - тип аргумента, а b - результат.

Prelude> (fmap (+1) (+2)) 0
3
Prelude> (fmap (+1) (+2)) 0
3
Prelude> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
Prelude> let funcMap = fmap :: (a -> b) -> (c -> a) -> c -> b
Prelude> -- f ~ (->) c 
Prelude> (funcMap (+1) (+2)) 0
3

Prelude> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
Prelude> let funcAp = (<*>) :: (c -> a -> b) -> (c -> a) -> (c -> b)
Prelude> :t fromMaybe
fromMaybe :: a -> Maybe a -> a
Prelude> :t funcAp fromMaybe
funcAp fromMaybe :: (b -> Maybe b) -> b -> b
Prelude> :t const
const :: a -> b -> a
Prelude> :t funcAp const
funcAp const :: (b -> b1) -> b -> b

Не гарантируется быть полезным. Вы можете сказать, что funcAp const не интересен только с типом и знает, как работает параметричность.

Изменить: говоря о compose, Functor для (->) a - это просто (.). Аппликация такова, но с дополнительным аргументом. Монада является аппликативным, но с аргументами перевернуты.

Дальнейшая кинетика: Аппликативная <*> для (->) a) равна S, а pure - K вычисления комбинатора SKI. (Вы можете получить я из K и S. Фактически вы можете получить любую программу из K и S.)

Prelude> :t pure
pure :: Applicative f => a -> f a
Prelude> :t const
const :: a -> b -> a
Prelude> :t const
const :: a -> b -> a
Prelude> let k = pure :: a -> b -> a
Prelude> k 1 2
1
Prelude> const 1 2
1

Ответ 2

Но использование ap не относится к Maybe. Мы используем его с функцией fromMaybe, поэтому он в контексте функций, где

ap f g x = f x (g x)

Среди различных экземпляров Monad мы имеем

instance Monad ((->) r)

так что это

ap :: Monad m =>    m  (a       -> b)  ->    m  a  ->    m  b
fromMaybe     ::  r -> (Maybe r -> r)
ap            :: (r -> (a       -> b)) -> (r -> a) -> (r -> b)   
ap                   f                        g        x :: b
ap  fromMaybe ::                          (r -> a) -> (r -> b)  , a ~ Maybe r , b ~ r

потому что -> в типах ассоциируется справа: a -> b -> c ~ a -> (b -> c). Пытаясь подключить типы вместе, мы можем найти только это определение выше.

И с (<*>) :: Applicative f => f (a -> b) -> f a -> f b мы можем записать его как (fromMaybe <*>), если вам нравится этот граффити:

 #> :t (fromMaybe <*>)
(fromMaybe <*>) :: (r -> Maybe r) -> r -> r

Как справедливо отмечено в другом ответе здесь, когда используется с функциями, <*> является только вашим хорошим ole ' S комбинатор. Мы не можем очень хорошо иметь функцию с именем S в Haskell, поэтому <*> - это всего лишь часть стандартного репертуара бесконтактного стиля кодирования. Монадическое связывание (более того, перевернутое), =<<, может быть еще более загадочным, но простодушный кодер просто не волнует и с радостью будет использовать его для кодирования другого, похожего шаблона,

(f =<< g) x = f (g x) x

в combinatory вызовы функций, тайна или нет тайн (zipWith (-) =<< drop 1 приходит на ум).

Ответ 3

Я хочу переопределить аргументы типа для ясности.

ap :: Monad m => m (a -> b) -> m a -> m b
fromMaybe :: c -> Maybe c -> c

Какой экземпляр Monad компилятор заключает, что m является?

((->) r) является Monad. Это все функции, которые имеют тип r в качестве своего аргумента для некоторого конкретного r.

Итак, в типе:

ap :: Monad m => m (a -> b) -> m a -> m b

m ~ (c ->), a ~ Maybe c и b ~ c.

Тип возврата, m a -> m b, расширяется до (c -> Maybe c) -> c -> c - это тип ap fromMaybe.

Ответ 4

Монада, которую вы ищете, это (->) r или r -> _, если вы предпочитаете синтаксис инфикса.

Тогда сигнатура ap расширяется до:

 m (a -> b) -> m a -> m b =
 (r -> (a -> b)) -> (r -> a) -> r -> b = -- now we use the signature of fromMaybe 
 (b -> (Maybe b -> b)) -> (b -> Maybe b) -> b -> b

Теперь, если вы считаете ap fromMaybe как частично примененную функцию и вуаля, вы получите желаемый результат.