4
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ This is good advice, but deriving Show was just for demonstration purposes; I already have a Show implementation which just delegates to the built-in versions for each type (but which I didn't want to bother including to have reviewed). I was trying to avoid rewriting the parser from scratch using a library like you describe, but maybe I'd better bite the bullet. \$\endgroup\$
    – pxeger
    Apr 2 at 17:40
  • 2
    \$\begingroup\$ @pxeger I think the main point isn't really about consistency between read and show, but that read and show are really supposed to be about one particular type of text rendering/parsing, which is Haskell source code format. There is no such thing as "one true way" of representing values as text; there are many others (JSON, XML, nice text for end users, etc), so you write as many functions as you need. Haskell has some built-in support for one of these formats, which is the Show and Read classes. Using those classes but not respecting their purpose can cause difficulties. \$\endgroup\$
    – Ben
    Apr 3 at 0:01
  • 2
    \$\begingroup\$ @pxeger Your language values will have distinct representations when written down in your language's source code than when represented in Haskell code (and these might not always be 1-1 in complex cases; you might e.g. have transparently interned strings but need to treat interned strings differently from regular ones inside your implementation). Being able to easily show the true Haskell-level representation will help you with debugging. This should be separate from how you parse and render values from/to your language. \$\endgroup\$
    – Ben
    Apr 3 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.