时间戳

首页 > 解决方案 > 递归函数中的Haskell多态推断/使用输入类型签名？

haskell - 递归函数中的Haskell多态推断/使用输入类型签名？

问题描述

data Tree a = Leaf a | Branch (Tree a) (Tree a)

readsTree :: (Read a) => ReadS (Tree a)
readsTree s = [(Branch l r, x) | ("<", t) <- lex s,
                                 (l, u) <- readsTree t,
                                 ("|", v) <- lex u,
                                 (r, w) <- readsTree v,
                                 (">", x) <- lex w ]
                                 ++ [(Leaf x, t) | (x, t) <- reads s]

例如在这个递归函数中，读取 s 需要一个类型签名，例如

k = reads "34a" :: [(Integer, String)] 
readsTree "<3|2>" :: [(Tree Integer, String)] \\works

但是多一层递归失败了readsTree "<3|<1|2>>" :: [(Tree Integer, String)]。这很奇怪，因为reads s似乎在一次递归调用后推断出正确的类型，但不是两次。有没有办法将 readsT​​ree t 的类型设置为基于初始调用的类型签名/更好的方法来做到这一点？

顺便说一句，这个例子直接来自于 Haskell 的 Gentle Introduction to Haskell，有点奇怪，它不起作用。我可能错过了一些东西，但我没有看到它......

标签： haskelltypesoverloading

解决方案

我没有看到任何表明类型推断有问题的地方。相反，我突然想到的是，您假设lex将返回一个单字符串，但它是一个比这更复杂的函数，它试图成为类似 Haskell 语言的词法分析器。当您到达字符串末尾的“>>”时，lex返回[(">>", "")]，并且您的模式匹配失败。由于您实际上不需要任何词法分析，只需编写自己的简单函数来丢弃特定字符：

readsTree :: (Read a) => ReadS (Tree a)
readsTree s = [(Branch l r, x) |
               t <- discard '<' s,
               (l, u) <- readsTree t,
               v <- discard '|' u,
               (r, w) <- readsTree v,
               x <- discard '>' w]
              ++ [(Leaf x, t) | (x, t) <- reads s]
  where discard :: Char -> String -> [String]
        discard t s = case s of
          (c:r) | c == t -> [r]
          _ -> []

然后我们根据需要：

*Main> readsTree "<3|<1|2>>" :: [(Tree Integer, String)]
[(Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2)),"")]

我无法解释为什么您的书包含一个不起作用的功能。可能是因为您正在阅读一份 21 年前的技术文档——也许lex那时的定义不同，我不知道。或者>>当时可能不是 Haskell 中的有效运算符，因此lex在解析第一个>.

推荐阅读