Read instance for Associative Computations Tree

Question

I have type

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

I have written Show and Foldable instances, 'Edited:' taking that 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

Problem

I can't realize how to write Read instance. Functions for Node are just names, which means i have to take functions from dictionary, and i can't do this either.

example of tree string

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

I tried writing parsers.

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)

But i couldn't apply them.

Answer 1

We only really need to identify "Leaf" or "Node something" and then defer to the Read instance of the element type for the rest.

Something like this might be good enough.

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'']
          _ -> []
      _ -> []

I've assumed lookupFunc with a type like String -> Maybe ([a] -> a) to look up the function names. But this type will only allow for functions like head that work on any [a]. You probably want to allow functions like sum that will work on particular element types. So function lookup needs to be in a class.

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

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

And add the Funcs constraint like

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

---

Final note: if you do want to use parser combinators, Text.ParserCombinators.ReadP (in base) has readS_to_P which lets you easily use Read instances as part of parsers. I'm not sure if other parser libraries have an equivalent.