读取关联计算树的实例

Question

我有类型

data EvalATree b a = Leaf a | Node ([b] -> a) [EvalATree b a]

我已经编写了 Show 和 Foldable 实例，“编辑：”假设 a = b

instance (Show a, Show a) => Show (EvalATree a a) where
  show :: (Show a, Show a) => EvalATree a a -> String
  show (Leaf a) = "Leaf " ++ show a
  show (Node g trees) = "Node " ++ show (calcNode (Node g trees)) ++ " " ++ show trees

instance Foldable (EvalATree a) where
  foldr f z (Leaf x) = f x z
  foldr f z (Node func subtrees) = foldr (\subtree acc -> foldr f acc subtree) z subtrees

问题

我不知道如何编写 Read 实例。 Node 的函数只是名称，这意味着我必须从字典中获取函数，而我也不能这样做。

树字符串示例

let tree = Node someFunction [Leaf 1, Leaf 2, Leaf 3]
let treeStr = "Node someFunction [Leaf 1, Leaf 2, Leaf 3]"

我尝试编写解析器。

parseEvalATree :: (Read a, Read a) =>  Parser a -> Parser (EvalATree a a)
parseEvalATree parserA = parseLeaf parserA <|> parseNode intFunctionDict parserA

parseLeaf :: (Read a, Read a) => Parser a -> Parser (EvalATree a a)
parseLeaf parserA = Leaf <$> parserA

parseNode :: (Read a, Read a) => Map String ([a] -> a) -> Parser a -> Parser (EvalATree a a)
parseNode dict parserA = do
  string "Node"
  spaces
  funcName <- many1 letter
  spaces
  subtrees <- between (char '[') (char ']') (parseEvalATree parserA `sepBy` char ',')
  let func = case Map.lookup funcName dict of
        Just f -> f
        Nothing -> error "Function not defined"
  return (Node func subtrees)

但我无法应用它们。

Answer 1

我们只需要识别“叶子”或“节点某物”，然后 其余的请遵循元素类型的 Read 实例。

这样的东西可能就足够了。

instance Read a => Read (EvalATree a a) where
  readsPrec _ s =
    case lex s of
      [("Leaf", s')] -> [(Leaf x, s'') | (x, s'') <- reads s']
      [("Node", s')] ->
        case lex s' of
          [(funcName, s'')] ->
            case lookupFunc funcName of
              Nothing -> []
              Just f -> [(Node f ts, s''') | (ts, s''') <- reads s'']
          _ -> []
      _ -> []

我假设

lookupFunc

具有类似的类型

String -> Maybe ([a] -> a)

查找函数名称。 但这种类型只允许像

head

这样的函数在 任何

[a]

。您可能希望允许像

sum

这样的功能 将适用于特定的元素类型。所以函数查找需要是 在课堂上。

class Funcs a where
  lookupFunc :: String -> Maybe ([a] -> a)

instance Funcs Int where
  lookupFunc "sum" = Just sum
  lookupFunc _ = Nothing

并添加 Funcs 约束，例如

instance (Funcs a, Read a) => Read (EvalATree a a) where ...

---

最后一点：如果您确实想使用解析器组合器，请使用 Text.ParserCombinators.ReadP （在基础中）有

readS_to_P

，它可以让您轻松地将 Read 实例用作 解析器的一部分。我不确定其他解析器库是否有 等效。