Прикладной функтор: <*> и частичное применение, как это работает

Ответ 1

Оцените pure (\x y -> (x,y)) <*> item. Второе приложение <*> будет легким, если мы увидим первое:

P (\inp1 -> [(\x y -> (x,y), inp1)]) <*> item 

Мы заменяем выражение <*> своим определением, подставляя операнды выражения для параметров определения.

P (\inp2 -> case parse P (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of
    []              -> []
    [(g, out)]      -> parse (fmap g item) out)

Затем мы делаем то же самое для выражения fmap.

P (\inp2 -> case parse P (\inp1 -> [(\x y -> (x,y), inp1)]) inp2 of
    []              -> []
    [(g, out)]      -> parse P (\inp -> case parse item inp of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]) out)

Теперь мы можем уменьшить первые два выражения parse (мы оставим parse item out позже, так как он в основном примитивен).

P (\inp2 -> case [(\x y -> (x,y), inp2)] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)])

Так много для pure (\x y -> (x,y)) <*> item. Поскольку вы создали первый парсер, подняв двоичную функцию типа a -> b -> (a, b), одно приложение в синтаксический анализатор типа Parser Char представляет собой синтаксический анализатор типа Parser (b -> (Char, b)).

Мы можем запустить этот синтаксический анализатор с помощью функции parse со входом "abc". Поскольку синтаксический анализатор имеет тип Parser (b -> (Char, b)), это должно уменьшаться до значения типа [(b -> (Char, b), String)]. Теперь дайте оценку этому выражению.

parse P (\inp2 -> case [(\x y -> (x,y), inp2)] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]) "abc"

По определению parse это сводится к

case [(\x y -> (x,y), "abc")] of
    []              -> []
    [(g, out)]      -> case parse item out of
                           []              -> []
                           [(v, out)]      -> [(g v, out)]

Очевидно, что шаблоны не совпадают в первом случае, но они выполняются во втором случае. Мы подставляем совпадения для шаблонов во втором выражении.

case parse item "abc" of
    []              -> []
    [(v, out)]      -> [((\x y -> (x,y)) v, out)]

Теперь мы наконец оценим это последнее выражение parse. parse item "abc" ясно сводится к [('a', "bc")] из определения item.

case [('a', "bc")] of
    []              -> []
    [(v, out)]      -> [((\x y -> (x,y)) v, out)]

Опять же, второй шаблон совпадает, и мы делаем замену

[((\x y -> (x,y)) 'a', "bc")]

которая сводится к

[(\y -> ('a', y), "bc")] :: [(b -> (Char, b), String)] -- the expected type

Если вы примените этот же процесс для оценки второго приложения <*> и поместите результат в выражение parse (result) "abc", вы увидите, что выражение действительно сводится к [(('a','b'),"c")].

Ответ 2

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

($)   ::                    (a -> b) ->   a ->   b
fmap  :: Functor     f =>   (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Итак, с помощью Functor мы применяем функцию к значению внутри "container/context" (т.е. Maybe, List,...), и с помощью Applicative функция, которую мы хотим применить, сама находится внутри "контейнера/контекста",

Функция, которую вы хотите применить, - это (,), а значения, которые вы хотите применить к функции, находятся внутри контейнера/контекста (в вашем случае Parser a).

Используя pure, мы поднимаем функцию (,) в тот же "контекст/контейнер", в котором находятся наши значения (обратите внимание, что мы можем использовать pure, чтобы поднять функцию в любой аппликативный (возможно, список,.):

(,) ::              a -> b -> (a, b)
pure (,) :: Parser (a -> b -> (a, b))

Используя <*>, мы можем применить функцию (,), которая теперь находится внутри контекста Parser, к значению, которое также находится внутри контекста Parser. Одно отличие от примера, предоставленного +1, состоит в том, что (,) имеет два аргумента. Поэтому мы должны дважды использовать <*>:

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

x :: Parser Int
y :: Parser Char

let p1 = pure (,) <*> x :: Parser (b -> (Int, b))
let v1 =      (,)     1 ::         b -> (Int, b)

let p2 = p1 <*> y  :: Parser (Int, Char)
let v2 = v1    'a' ::        (Int, Char)

Теперь мы создали новый синтаксический анализатор (p2), который мы можем использовать, как и любой другой синтаксический анализатор!

., а затем больше!

Посмотрите на эту удобную функцию:

(<$>) :: Functor f => (a -> b) -> f a -> f b

<$> - это просто fmap, но вы можете использовать его, чтобы написать комбинаторы более красиво:

data User = User {name :: String, year :: Int}
nameParser :: Parser String
yearParser :: Parser Int

let userParser = User <$> nameParser <*> yearParser -- :: Parser User

Хорошо, этот ответ был длиннее, чем я ожидал! Надеюсь, это поможет. Возможно, вы также посмотрите на Typeclassopedia, который я нашел бесценным, изучая Haskell, который является бесконечным красивым процессом.,:)

Ответ 3

TL; DR: Когда вы сказали, что "теперь у вас есть парсер с одним параметром" inp1, вы запутались: inp1 - это строка ввода для синтаксического анализатора, но функция (\x y -> (x,y)) - только (,) - применяется к выходным значениям, созданным путем разбора входной строки. Последовательность значений, созданных вашими временными парсерами, следующая:

-- by (pure (,)):
(,)                     -- a function expecting two arguments

-- by the first <*> combination with (item):
(,) x                   -- a partially applied (,) function expecting one more argument

-- by the final <*> combination with another (item):
((,) x) y == (x,y)      -- the final result, a pair of `Char`s taken off the 
                        -- input string, first (`x`) by an `item`, 
                        -- and the second (`y`) by another `item` parser

Работа с помощью эквационального рассуждения может быть проще:

 -- pseudocode definition of `fmap`:
 parse (fmap g p) inp = case (parse p inp) of    -- g :: a -> b , p :: Parser a
    []              -> []                        --        fmap g p :: Parser b
    [(v, out)]      -> [(g v, out)]              -- v :: a ,           g v :: b

(по-видимому, это предполагает, что любой синтаксический анализатор может производить только 0 или 1 результат, так как случай с более длинным списком вообще не обрабатывается, что обычно неодобрительно и не зря);

 -- pseudocode definition of `pure`:
 parse (pure v) inp = [(v, inp)]                 -- v :: a , pure v :: Parser a

(синтаксический разбор с pure v вызывает v без использования ввода);

 -- pseudocode definition of `item`:
 parse (item) inp = case inp of                  -- inp :: ['Char']
    []              -> []
    (x:xs)          -> [(x,xs)]                  -- item :: Parser 'Char'

(синтаксический разбор с item означает, если возможно, один Char с головки входа String); и,

 -- pseudocode definition of `(<*>)`:
 parse (pg <*> px) inp = case (parse pg inp) of    -- px :: Parser a
    []              -> []
    [(g, out)]      -> parse (fmap g px) out       -- g :: a -> b

(<*> объединяет два синтаксических анализатора с типами результатов, которые подходят, создавая новый объединенный парсер, который использует первый синтаксический анализ для синтаксического анализа ввода, затем использует второй синтаксический анализатор для анализа оставшейся строки, объединяя два результата для создания результат нового объединенного анализатора);

Теперь <*> связывается слева, так что вы спросите о

parse ( pure (\x y -> (x,y)) <*> item <*> item ) "abc"
= parse ( (pure (,) <*> item1) <*> item2 ) "abc"             -- item_i = item

самый правый <*> является самым верхним, поэтому мы сначала его расширяем, оставляя вложенное выражение как есть,

= case (parse (pure (,) <*> item1) "abc") of                 -- by definition of <*>
    []              -> []
    [(g2, out2)]    -> parse (fmap g2 item2) out2
                       = case (parse item out2) of           -- by definition of fmap
                            []              -> []
                            [(v, out)]      -> [(g2 v, out)]
                       = case out2 of                        -- by definition of item
                            []              -> []
                            (y:ys)          -> [(g2 y, ys)]

Аналогично, вложенное выражение упрощается как

parse (pure (,) <*> item1) "abc"
= case (parse (pure (\x y -> (x,y))) "abc") of               -- by definition of <*>
    []              -> []
    [(g1, out1)]    -> parse (fmap g1 item1) out1
                       = case (parse item out1) of ....
                       = case out1 of
                            []              -> []
                            (x:xs)          -> [(g1 x, xs)]
= case [((,), "abc")] of                                     -- by definition of pure
    [(g1, out1)]    -> case out1 of
                            []              -> []
                            (x:xs)          -> [(g1 x, xs)]
= let { out1 = "abc" 
      ; g1   = (,)
      ; (x:xs) = out1
      }
   in  [(g1 x, xs)]
= [( (,) 'a', "bc")] 

и, следовательно, получаем

= case [( (,) 'a', "bc")] of
    [(g2, out2)]    -> case out2 of
                            []              -> []
                            (y:ys)          -> [(g2 y, ys)]

Я думаю, теперь вы можете видеть, почему результат будет [( ((,) 'a') 'b', "c")].

Ответ 4

Во-первых, я хочу подчеркнуть одно. Я обнаружил, что суть понимания заключается в том, что он замечает разделение между самим Parser и запуском парсера с помощью parse.

При запуске анализатора вы передаете Parser и строку ввода на parse, и он предоставит вам список возможных анализов. Я думаю, что, возможно, легко понять.

Вы пройдете parse a Parser, который может быть создан с использованием клея <*>. Попытайтесь понять, что при передаче parse Parser, a или Parser, f <*> a <*> b вы передадите ему тот же тип вещей, то есть что-то эквивалентное (String -> [(a,String)]). Я думаю, что это, вероятно, легко понять, но все же это занимает некоторое время до "click".

Тем не менее, я немного расскажу о природе этого аппликативного клея <*>. Прикладной, F a является вычисление, которое дает данные типа a. Вы можете придумать такой термин, как

... f <*> g <*> h

как ряд вычислений, возвращающих некоторые данные, скажем a, затем b, затем c. В контексте Parser вычисление включает f поиск a в текущей строке, а затем передачу оставшейся части строки в g и т.д. Если какой-либо из вычислений/разборки терпит неудачу, весь термин.

Интересно отметить, что любое приложение может быть записано с чистой функцией в начале, чтобы собрать все эти испущенные значения, поэтому мы можем вообще написать,

 pure3ArgFunction <$> f <*> g <*> h

Я лично нахожу ментальную модель испускания и сбора полезной информации.

Итак, с этой длинной преамбулой, на фактическое объяснение. Что делает

parse (pure (\x y -> (x,y)) <*> item <*> item) "abc"

делать? Ну, parse (p::Parser (Char,Char) "abc" применяет синтаксический анализатор (который я переименовал p) в "abc", давая [(('a','b'),"c")]. Это успешный синтаксический анализ с возвращаемым значением ( "a", "b" ) и оставшейся строкой "c".

Хорошо, это не вопрос. Почему парсер работает таким образом? Начиная с:

.. <*> item <*> item

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

fmap (\x y -> (x,y)) $ item <*> item

или

(\x y -> (x,y)) <$> item <*> item

который является моим способом показать, что чистая функция ничего не делает с входной строкой, она просто собирает результаты. Когда я смотрел в этом свете, я думаю, что парсер должен быть легко понят. Очень просто. Слишком легко. Я имею в виду это со всей серьезностью. Не то, чтобы концепция была настолько сложной, но наша нормальная система взглядов на программирование слишком чужда, чтобы она имела смысл вначале.

Ответ 5

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

Я думаю, что вам действительно нужно глубоко понимать Functor и Applicative Functor. После того, как вы поймете эти темы, другие будут легки, как две три (я имею в виду большинство из них ^^).

Итак: что такое Functor, Applicative Functor и их приложения в вашей проблеме?

Лучшие учебники по этим темам:

• Глава 11 "Узнай Хаскелл за отличное": http://learnyouahaskell.com/functors-applicative-functors-and-monoids.

• Более наглядные "Функторы, Применения и Монады в Картах": http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html.

Сначала, когда вы думаете о Functor, Applicative Functor, подумайте о "значениях в контекстах": значения важны, а вычислительные контекстысильные > тоже важны. Вы должны иметь дело с обоими из них.

Определения типов:

    -- Define a new type containing a parser function
    newtype Parser a = P (String -> [(a,String)])

    -- This function apply the parser p on inp
    parse :: Parser a -> String -> [(a,String)]
    parse (P p) inp = p inp

• Значение здесь - это значение типа a, первого элемента кортежа в списке.

• Контекст здесь - это функция или возможное значение. Вы должны предоставить вход для получения окончательного значения.

Parser - это функция, завернутая в конструктор данных P. Поэтому, если вы получили значение b :: Parser Char и хотите применить его к некоторому входу, вам необходимо развернуть внутреннюю функцию в b. Вот почему мы имеем функцию parse, она разворачивает внутреннюю функцию и применяет ее к входному значению.

И, если вы хотите создать значение Parser, вы должны использовать конструктор данных P, обертывающий вокруг функции.

Второй, Functor: что-то, что можно "отобразить", указанное функцией fmap:

    fmap :: (a -> b) -> f a -> f b

Я часто называю функцию g :: (a -> b) функцией normal, потому что, как вы видите, вокруг нее не обтекает контекст. Таким образом, чтобы иметь возможность применить g к f a, нам нужно как-то извлечь a из f a, так что g может применяться только к a. Это "как-то" зависит от конкретного Functor и является контекстом, в котором вы работаете:

    instance Functor Parser where
      fmap g p = P (\inp -> case parse p inp of
        []              -> []
        [(v, out)]      -> [(g v, out)])

• g - это функция типа (a -> b), P имеет тип f a.

• Чтобы развернуть P, чтобы получить значение контекста, мы должны передать некоторое входное значение в: parse p inp, тогда это значение является первым элементом кортежа. Примените g к этому значению, получите значение типа b.

• Результат fmap имеет тип f b, поэтому мы должны обернуть весь результат в том же контексте, что мы имеем: fmap g p = P (\inp -> ...).

В это время вам может показаться, что вы можете иметь реализацию fmap, в которой результатом вместо [(g v, out)] является [(g v, inp)]. И ответ: Да. Вы можете реализовать fmap любым способом, но важно, чтобы это был подходящий Functor, реализация должна подчиняться законам Functor. Законы заключаются в том, что мы реализуем реализацию этих функций (http://mvanier.livejournal.com/4586.html). Реализация должна удовлетворять не менее 2 законам-функторам:

• fmap id = id.
• fmap (f . g) = fmap f . fmap g.

fmap часто записывается как инфиксный оператор: <$>. Когда вы это увидите, посмотрите на 2-й операнд, чтобы определить, с каким функтором вы работаете.

Третий, Applicative Functor: вы применяете завернутую функцию к обернутому значению, чтобы получить другое завернутое значение:

    <*> :: f (a -> b) -> f a ->  f b

• Разверните внутреннюю функцию.
• Отменить 1-е значение.
• Применить функцию и обернуть результат.

В вашем случае:

    instance Applicative Parser where
      pure v = P (\inp -> [(v, inp)])
      pg <*> px = P (\inp -> case parse pg inp of
        []              -> []
        [(g, out)]      -> parse (fmap g px) out)

• pg имеет тип f (a -> b), px имеет тип f a.
• Unwrap g от pg от parse pg inp, g является первым из кортежей.
• Unwrap px и примените g к значению с помощью fmap g px. Внимание, функция результата применяется только к out, в некотором смысле это "bc" not "abc".
• Оберните весь результат: P (\inp -> ...).

Подобно Functor, реализация Applicative Functor должна подчиняться законам Applicative Functor (в уроках выше).

Четвертый, примените к своей проблеме:

    parse (pure (\x y -> (x,y)) <*> item <*> item) "abc"
           |         f1        |    |f2|     |f3|

• Разверните f1 <*> f2, передав ему "abc":
  • Unwrap f1, передав ему "abc", получим [(g, "abc")].
  • Тогда fmap g на f2 и передав ему out="abc":
    • Unwrap f2 get [('a', "bc")].
    • Применить g на 'a' получить результат: [(\y -> ('a', y), "bc")].
• Затем fmap 1-й элемент результата на f3 и передайте ему out="bc":
  • Unwrap f3 get [('b', "c")].
  • Применить функцию на 'b' получить окончательный результат: [(('a', 'b'), "c")].

В заключение:

• Потратьте некоторое время на то, чтобы идеи "погрузились" в вас. В частности, законы приводят к реализации.
• В следующий раз спроектируйте свою структуру данных, чтобы ее легче понять.
• Haskell - один из моих любимых языков, и я уверен, что он скоро будет вашим, поэтому будьте терпеливы, ему нужна кривая обучения, а затем вы идете!

Счастливый хаскелл взломал!

Ответ 6

Хм, я не знаком с Haskell, но моя попытка генерировать экземпляры Functor и Applicative типа Parser была бы следующей:

-- Define a new type containing a parser function
newtype Parser a = P (String -> [(a,String)])

-- This function apply the parser p on inp
parse :: Parser a -> String -> [(a,String)]
parse (P p) inp = p inp

-- A parser which return a tuple with the first char and the remaining string
item :: Parser Char
item = P (\inp -> case inp of
    []     -> []
    (x:xs) -> [(x,xs)])

-- A parser is a functor
instance Functor Parser where
  fmap g (P f) = P (\str -> map (\(x,y) -> (g x, y)) $ f str)

-- A parser is also an applicative functor
instance Applicative Parser where
pure v = P (\str -> [(v, str)])

(P g) <*> (P f) = P (\str -> [(g' v, s) | (g',s) <- g str, (v,_) <- f str])

(P g) <*> (P f) = P (\str -> f str >>= \(v,s1) -> g s1 >>= \(g',s2) -> [(g' v,s2)])

(10x очень полезно для помощи @Will Ness на <*>)

В соответствии с...

*Main> parse (P (\s -> [((+3), s)]) <*> pure 2) "test"
[(5,"test")]

*Main> parse (P (\s -> [((,), s ++ " altered")]) <*> pure 2 <*> pure 4) "test"
[((2,4),"test altered")]