haskell - 函数定义在函数 many 中有类型错误

Question

我最近开始学习 Haskell，目前正在研究“用于解析的高阶函数”论文。你可以在这里找到它。

该论文定义了一个名为many.

许多 :: parser * ** -> parser * [**]
many p = ((p $then many p) $using cons) $alt (succeed [])

我正在尝试将其转换为 Haskell。

succeed v inp = [(v, inp)]

fail' inp = []

satisfy p [] = fail' []
satisfy p (x:xs)
  | p x = succeed x xs
  | otherwise = fail' xs

literal x = satisfy (==x)

alt' p1 p2 = \inp -> p1 inp ++ p2 inp

then' p1 p2 = \inp -> [((v1, v2), out2) | (v1, out1) <- p1 inp, (v2, out2) <- p2 out1]

using' p f = \inp -> [(f v, out) | (v, out) <- p inp]

many' p = ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])

我已经单独测试了所有部件，它们工作正常。但是许多人的定义给了我错误。我似乎无法弄清楚是什么问题。我正在按照论文中提到的方式进行操作。

Main.hs:19:56: 错误：
    • 无法将类型“[a0]”与“[(a, b)] -> [(a, b)]' 匹配
      预期类型：t -> [([(a, b)] -> [(a, b)], t)]
        实际类型：t -> [([a0], t)]
    • 在'alt''的第二个参数中，即'(succeed [])'
      在表达式中：
        ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])
      在“许多”的方程式中：
          many' p = ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])
    • 相关绑定包括
        p :: t -> [(a, t)] （绑定在 Stum.hs:19:7）
        many' :: (t -> [(a, t)]) -> t -> [(b, t)] （绑定在 Stum.hs:19:1）
   |
19 | many' p = ((p `then'` (many' p)) `using'` (:)) `alt'` (succeed [])
   |
失败，未加载任何模块。
前奏>

标签： haskell

Answer 1

如果您在所有顶级定义中都有类型，这将更容易理解。

无论如何，我认为问题在于using'和柯里化之间的交互。我注意到then'将两个值解析为一对，并且您正在解析的示例代码适用cons于该对，以从对元素创建一个列表作为列表的头部和尾部。但是(:)是柯里化的——如果你把它应用到一对上，这对只是列表的头部，它仍然期望尾部有第二个参数。您应该决定是否要using'使用柯里化函数。如果您想尽可能靠近您所关注的论文，您将保留 的定义using'，但更改many'为

many' p = ((p `then'` (many' p)) `using'` uncurry (:)) `alt'` (succeed [])

uncurry是一个简单的辅助函数Prelude，恰好恰好解决了这个问题。

注意：所有这些都未选中。这是我可以提供的最好的快速猜测，而无需查看所涉及的类型。

这里有更多解释，试图让这更容易理解：

(:)有类型a -> [a] -> [a]。uncurry (:)（或者等价地，(\(h, t) -> h:t)，以防uncurry一次有点绕你的头）具有类型(a, [a]) -> [a]. 在完成其余工作时，您应该牢记这种差异。

请注意，then'将((v1, v2), out2). 请注意，using'将解析后的值作为一个整体转换为(f v, out). 当它们被链接在一起时，它最终会沿着f (v1, v2). 鉴于many'将如何使用then'，v1将是单个解析结果，并且v2将是后续解析结果的列表。您想将它们组合成一个更大的列表，(v1:v2). 您需要通过f对(v1, v2). 现在回到 和 之间的(:)区别uncurry (:)。当提供为f.

我希望这个扩展的解释能让你更容易看到发生了什么。