Haskell: implementing Read for a custom dynamic value type

Question

I'm using Haskell to interpret a dynamically-typed language. I have a sum type called Value which can represent some basic objects:

data Value
  = Integer Integer
  | Float Double
  | Char Char
  | List [Value]
  deriving Show

(For now I'm not adding a special case for strings - they'll just be lists of characters.)

I have instantiated Read for it, so that I can parse string inputs into Values as though they're normal Haskell values.

While for this demo I just derived Show using the default implementation, I had to define Read manually, because I don't want the input to need the data constructors prefixed before every element. (I would have to write input as Integer 43 instead of just 43, for example)

I implement readsPrec (which seems a needlessly complex method to have as the minimal typeclass implementation, but it's what Haskell requires...) in terms of Haskell's default implementations for the underlying data types.

readsPrec takes a precedence value, which I just pass on to the readsPrec of other types; it returns a list of possible parses as tuples of (value, restOfString).

The basic algorithm I use is to attempt to parse the input into each type, and choose the first result from each. Unfortunately there's quite a lot of plumbing required to deal with the list of tuples produced by readsPrec.

instance Read Value where
  readsPrec precedence s =
    -- `justs` stops the parsing once all of the read attempts are failing
    justs $ map (foldl orElse Nothing) $ transpose attempts
      where
        -- try to parse the input into each of these types, one at a time
        attempts = [u Integer, u Float, u Char, u List]
        u constructor = maybes [(constructor val, rest) | (val, rest) <- readsPrec precedence s]

This implementation also uses a couple of utility functions:

-- | Create an infinite list of Maybes, where the elements in the input
-- | are `Just`s, and everything after that is a `Nothing`
maybes xs = map Just xs ++ repeat Nothing

-- | Collect the values of all Justs at the start of a list
justs (Just x : xs) = x : justs xs
justs _             = []

I want to know if my code, especially the plumbing around readsPrec, can be made more idiomatic, perhaps using some more builtin functions. Maybe the whole algorithm can be simplified.

I also don't like the fact I'm using a constant-sized list for the attempts. I'd like to be able to just use a tuple, but if I ever wanted to add more data types, I'd have to change things like unzip4 to unzip5, because I can't write it polymorphically over tuple size. (where unzip would be used for tuples, in place of transpose for lists)

I'm not really interested in whether the minutiae of my syntax style are "correct".

Here is an online demo of my code.

Answer 1

Your algorithm is fine. Your Read instance, however, isn't. There are semi-written laws, namely that for any type A that instanciates both Show and Read the following laws hold:

• if I read a value and then show it again, I will end up with the same string (except for whitespace changes):

  srIdentity :: (Read a, Show a) => a -> String -> String
  srIdentity x s = show (read s `asTypeOf` x)
  

• if I show a value and then read it again, I get the same value back:

  rsIdentity :: (Show a, Read a) => a -> a
  rsIdentity = read . show
  

• the process must be repeatable for both variants

  srsrIdentity :: (Show a, Read a) => a -> String -> String
  srsrIdentity x = srIdentity x . srIdentity x
  
  rsrsIdentity :: (Show a, Read a) => a -> a
  rsrsIdentity = rsIdentity . rsIdentity
  

Your Read instance does not hold any of those laws. What you really want is a regular function

parseString :: String -> Value

Usually, you would use one of the (many) parsing libraries for this, like attoparsec or parsec. Many of those parsers are also Monad or even MonadPlus (or Alternative), so you end up with something along

valueP :: Parser Value
valueP =  integerP
      <|> floatP
      <|> charP
      <|> many valueP

I'd like to be able to just use a tuple, but if I ever wanted to add more data types

Adding a new type would then lead to just another alternative:

valueP :: Parser Value
valueP =  integerP
      <|> floatP
      <|> charP
      <|> complexP        -- <----
      <|> many valueP

So have a look at parsers and parsing. And keep in mind: if you derive Show, you should also derive Read. If you feel the need to write the Read instance by hand, don't, instead write a parser.