CODEWITHSUNDEEP
haskelltypesoverloading
squirrels
squirrels

Reputation: 313

Haskell polymorphic inference in a recursive function/using the input type signature?

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]

For example in this recursive function, reads s needs a type signature such as

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

but one more level of recursion fails readsTree "<3|<1|2>>" :: [(Tree Integer, String)]. Its strange because reads s appears to infer the right type after one recursive call, but not two. Is there a way to set the type of readsTree t to be based on the type signature of the inital call/a better way to do this?

Btw this example is straight out of Gentle Introduction to Haskell, kind of strange that it doesn't work. I might have missed something but I don't see it...

Upvotes: 0

Views: 65

Answers (1)

amalloy
amalloy

Reputation: 91857

I don't see anything to suggest that type inference is at fault here. Rather, what jumps out to me is that you assume lex will return a single-character string, but it is a much more complicated function than that, trying to be the lexer for a Haskell-like language. When you get to the ">>" at the end of your string, lex returns [(">>", "")], and your pattern match fails. Since you don't in fact want any lexing, just write your own simple function for discarding a specific character:

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

and then we have, as desired:

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

I cannot explain why your book includes a function which does not work. It could be because you are reading a 21-year-old technical document - perhaps the definition of lex was different then, I don't know. Or maybe >> was not a valid operator in Haskell at the time, and so lex stopped after parsing the first >.

Upvotes: 1

Related Questions