как напечатать промежуточный результат в Functor и Applicative в Haskell

Question

Я читаю книгу Программирование в Haskell 2-е Грэма Хаттона. https://www.cs.nott.ac.uk/~pszgmh/pih.html#slides

Когда речь идет о главе 13.4 Анализаторы последовательности, он содержит следующие функции:

> parse three "abcdef" 
[((’a’,’c’),"def")] 
> parse three "ab" 
[]

Я хотел бы понять, каковы промежуточные шаги для оцените их за сценой. Вы можете найти рабочий исходный код для Functor и Applicative для Parser здесь:

import Control.Applicative
import Data.Char

-- Basic definitions
newtype Parser a =
  P (String -> [(a, String)])
parse (P p) inp = p inp


item :: Parser Char
item = P (\inp -> case inp of
         [] -> []
         (x:xs) -> [(x, xs)])

-- Sequencing parsers
instance Functor Parser
   -- fmap :: (a -> b) -> Parser a -> Parser b
                                               where
  fmap g p =
    P
      (\inp ->
         case parse p inp of
           [] -> []
           [(v, out)] -> [(g v, out)])
--parse  (fmap toUpper item) "abc"

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

three :: Parser (Char, Char)
three = pure g <*> item <*> item <*> item
  where
    g x y z = (x, z)

Я попытался сделать это, подставив определения из Functor и Applicative следующим образом, но не знаю, как это сделать. далее:

parse three "abc"



three :: Parser (Char,Char) 
three 
= pure g <*> item <*> item <*> item 
=P (\inp -> [(g,inp)]) <*> item <*> item <*> item        (apply pure v)

-----------------------------------------------------------------------------------------------------------
=P (
\inp -> case parse P (\inp -> [(g,inp)]) inp of         (apply pg <*> px)
[] -> [] 
[(g,out)] -> parse (fmap g item) out
)

<*> item <*> item 
-----------------------------------------------------------------------------------------------------------
=P (
\inp -> case (\inp -> [(g,inp)]) inp of             (apply parse (P p) inp = p inp
[] -> [] 
[(g,out)] -> parse (fmap g item) out
)

<*> item <*> item 

-----------------------------------------------------------------------------------------------------------
Here, inp=”abc”,  (\inp -> [(g,inp)]),  inp = [  (f x y z =(x,z), “abc”   )]  
=P (
parse (
fmap g item
) out
)                               (apply \inp -> [(g,inp)] on inp)

<*> item <*> item 

Answer 1

(Это ответ на вопрос «По предложению @Daniel Wagner, я расширяю обновление fmap g p:»)

Верна ли последняя замена?

Невозможно ответить, потому что шаги до этого некорректны.

Есть несколько проблем с вашим расширением, указывающих на то, что вы неаккуратны при записи, что привело к ошибкам. Также могут быть концептуальные проблемы.

Например, когда вы вставили three = P ... в parse three "abc", вы не поставили круглые скобки вокруг P ..., ведя к этой строке:

parse P (parse (P ...)) <*> item <*> item "abc"

Скорее всего, это синтаксически неверно, так как он будет проанализирован как

(parse P (parse (P ...))) <*> item <*> (item "abc")

Хотя вы, вероятно, имели в виду:

parse ((P ...) <*> item <*> item) "abc"

Если вы думаете, ну, я просто делаю это, чтобы сделать проще написать, а потом проверить: эта синтаксическая ошибка также привела к ошибочной работе над частью parse P (parse (P ...)) независимо от <*> item <*> item "abc", что было серьезной ошибкой и сделало большую часть всего, что после этого не имеет значения.

Другое дело так:

Here, inp="abc",  (\inp -> [(g,inp)]),  inp = [  (f x y z =(x,z), "abc"   )]

Эта строка вообще не имеет смысла. Так как вы просто расширяете three, нельзя сказать, что inp - это что-то. Рассмотрим (\x -> x). x здесь просто для установления sh отношения, что результат совпадает с аргументом и не имеет никакого конкретного значения. Это то, что подразумевается под переменной bound .

(И я даже не знаю, о чем вы говорите, когда говорите (\inp -> [(g,inp)]), inp = [ (f x y z =(x,z), "abc" )]. Может быть, вы можете уточнить? )

Это также означает, что следующее не имеет смысла

 (\inp -> case parse item inp of [] -> []; [(v, out)] -> [(g v, out)]))<*> item <*> item “abc”
={substitute inp for "abc"}
 case parse item  "abc" of [] -> []; [(v, out)] -> [(g v, out)]<*> item <*> item 

Здесь есть несколько проблем. Начнем с того, что в первой строке есть дополнительная близкая скобка, что затрудняет понимание того, что вы имеете в виду. Если мы проигнорируем это, то раньше у вас было (\inp ->) <*> item ..., но потом вы не ставили скобки вокруг выражения case, делая <*>.

Также кажется, что вы хотите сделать бета-версию. сокращение здесь. Бета-редукция всегда имеет форму (\v -> E) a, в которой лямбда-выражение непосредственно применяется к аргументу. Вы не можете просто сказать случайным образом, что «v равно a» и прыгать в выражениях.

Например, если у нас есть f (\x -> x + 1) 3, правильно ли уменьшать это значение до f 4? Нет, потому что лямбда не применяется к 3.

Это означает, что даже если первая половина верна, вторая половина того, что вы написали, основана на бессмысленном шаге и не имеет значения.

---

Я бы очень хотел рассказать вам, как исправить ваши сокращения, но мне жаль говорить, что я думаю, что то, что вы написали, уже не подлежит восстановлению. Если вы хотите получить правильную трассировку сокращения, будьте более внимательны с синтаксисом и допустимостью каждого шага и делайте все заново с нуля.

В качестве справки, есть несколько вещей, которые вы должны проверить посмотрите, что пошло не так:

1. Каждый шаг должен быть синтаксически действительным. Отсутствие несвязанных переменных, отсутствие пропущенных символов и т. Д. c.
2. Если проверка типов исходного выражения выполняется, то каждый шаг также должен проверять тип и иметь одинаковый тип.

Answer 2

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

\inp -> case (\inp -> [(g,inp)]) inp of [] -> []; [(g, out)] -> parse (fmap g item) out
=
                                                                parse (fmap g item) out

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

\inp -> case (\inp -> [(g,inp)]) inp of [] -> []; [(g, out)] -> parse (fmap g item) out
= { beta reduction, substituting inp for inp }
\inp -> case [(g, inp)]              of [] -> []; [(g, out)] -> parse (fmap g item) out
= { case reduction, substituting g for g and inp for out }
\inp ->                                                         parse (fmap g item) inp

Если хотите, вы можете уменьшить это до parse (fmap g item). Подключив его обратно к общим частям, которые мы опускали выше, мы имеем:

three
=
P (parse (fmap g item)) <*> item <*> item

Результат можно проверить в ghci:

*Parsing> parse three "abc"
[(('a','c'),"")]

*Parsing> let g x y z = (x,z)

*Parsing> parse (P (parse (fmap g item)) <*> item <*> item) "abc"
[(('a','c'),"")]

В качестве следующих шагов вы можете выполнить три следующих действия: выполните следующее определение-расширение, чтобы включить дальнейший прогресс:

1. Вы можете расширить fmap в fmap g item.
2. Вы можете расширить внутреннее (<*>) в P (...) <*> item .
3. Вы можете расширить внешний (<*>) в (P (...) <*> item) <*> item.

Удачи!