如何在Functor中打印中间结果，在Haskell中打印Applicative

Question

我正在读Graham Hutton的《Haskell第二版编程》一书。https://www.cs.nott.ac.uk/~pszgmh/pih.html#幻灯片

当谈到第13.4章测序解析器时，它包含以下功能：

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

我想了解在幕后评估它们的中间步骤是什么。你可以在这里找到函数的工作源代码和解析器的应用程序：

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"

如果你认为，好吧，我这样做只是为了让写起来更容易，那么请检查一下：这个语法错误还导致你错误地独立于<*> item <*> item "abc"处理parse P (parse (P ...))部分，这是一个严重的错误，并使后面的大部分内容变得无关紧要。

另一件事是：

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

这一行毫无意义。由于您只是在扩展three，所以说inp是任何东西都是无效的。以(x -> x)为例。这里的x只是为了建立结果与自变量相同的关系，而不是任何特定的值。这就是它是一个绑定的变量的含义。

(我甚至不知道你说(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 

这里有多个问题。首先，第一行有一个非常接近的paren，这使得很难理解你的意思。如果我们忽略这一点，那么在你有(inp ->) <*> item ...之前，但之后你没有在case表达式周围加上parens，从而生成<*>。

此外，你似乎想在这里做一个测试版缩减。β归约的形式总是(v -> E) a，其中lambda直接应用于参数。你不能随便说"v等于a"，然后在表达式中跳来跳去。

例如，如果我们有f (x -> x + 1) 3，那么将其减少为f 4是正确的吗？否，因为lambda没有应用于3。

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

---

我很想告诉你如何修复你的减少，但很抱歉，我认为你写的东西现在已经无法修复了。如果你想有一个正确的还原跟踪，请更加小心每个步骤的语法和有效性，并从头开始做所有事情。

作为一种帮助，有几件事你应该检查一下，看看是否出了问题：

1. 每个步骤都应该在语法上有效。没有未绑定的变量，没有缺少paren等
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

如果您愿意，您可以将其eta减少为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 g item中扩展fmap
2. 您可以在P (...) <*> item中展开内部(<*>)
3. 您可以在(P (...) <*> item) <*> item中扩展外部(<*>)

祝你好运！