parsing - 如何在 Haskell 中的 Functor 和 Applicative 中打印中间结果

Question

我正在阅读 Graham Hutton 的《Haskell 2nd 编程》一书。
https://www.cs.nott.ac.uk/~pszgmh/pih.html#slides

说到第 13.4 章排序解析器，它包含以下功能:

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

我想了解在幕后评估它们的中间步骤是什么。您可以在此处找到用于解析器的 Functor 和 Applicative 的工作源代码:

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 上进行扩展:”更新的回应)

Is the last substitution correct?

无法回答，因为之前的步骤不正确。

你的展开有几个问题，说明你写的马虎，导致了错误。也可能存在概念问题。

例如，当您内联 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这里只是建立结果与参数相同的关系，而不是任何特定的值。这就是它是一个绑定(bind)变量的意思。

(当你说 (\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 周围加上括号表达，制作 <*> .

此外，您似乎想在此处进行 beta-reduction。 Beta 减少的形式总是 (\v -> E) a ，其中 lambda 直接应用于参数。你不能随便说 ' v等于 a ' 并在表达式中跳来跳去。

例如，如果我们有 f (\x -> x + 1) 3 , 将其减少到 f 4 是否正确?不，因为 lambda 未应用于 3 .

这意味着即使前半部分是正确的，你写的后半部分也是基于一个无意义的步骤，是无关紧要的。

我非常想告诉你如何修复你的减少，但我很遗憾地说我认为你写的东西现在已经无法修复了。如果您想获得正确的归约迹线，请更加注意每个步骤的语法和有效性，并从头开始重新执行所有操作。

作为辅助，您应该检查几件事以查看是否出现问题:

每个步骤都应该在语法上有效。没有未绑定(bind)的变量，没有丢失的括号等。

如果原始表达式类型检查，则每个步骤也必须进行类型检查并具有相同的类型。