Why does this loops with 'data' but not 'newtype'?

Question

Here is the code :

import Control.Applicative

-- newtype Parser a = Parser { runParser :: String -> [(a, String)] }
data Parser a = Parser { runParser :: String -> [(a, String)] }

instance Functor Parser where
  fmap f (Parser p) = Parser (\s -> [(f x, s') | (x, s') <- p s ] )

instance Applicative Parser where
  pure a = Parser (\s -> [(a, s)])
  Parser q <*> Parser p = Parser (\s -> [(f x, s'') | (f, s') <- q s, (x, s'') <- p s'])

instance Alternative Parser where
  empty = Parser (\s -> [])
  Parser q <|> Parser p = Parser (\s -> q s ++ p s)

item = Parser (\s -> case s of
                  (x:xs) -> [(x, xs)]
                  _ -> []
              )

With the current code, runParser (some item) "abcd" loops, but if Parser is declared as newtype, it works just fine.

What exactly are you asking? Do you have an example you could show of this? — Alec, Jan 15 '17 at 04:19
There is almost no information in this question. We can't guess what's going on if you don't share more details. You should provide a [MCVE](http://stackoverflow.com/help/mcve). — chi, Jan 15 '17 at 08:36

score 6 · Accepted Answer · edited May 23 '17 at 12:24

This is a great way of getting at one of the difference between data and newtype. The heart of the problem here is actually in the pattern matching of the <|> definition.

instance Alternative Parser where
  empty = Parser (\s -> [])
  Parser q <|> Parser p = Parser (\s -> q s ++ p s)

Remember that at runtime, a newtype becomes the same thing as the type it is wrapping. Then, when a newtype is pattern matched, GHC doesn't do anything - there is no constructor to evaluate to WNHF.

On the contrary, when a data is matched, seeing the pattern Parser q tells GHC it needs to evaluate that parser to WNHF. That is a problem, because some is an infinite fold of <|>. There are two ways to solve the problem with data:

Don't have Parser patterns in <|>:

instance Alternative Parser where
  empty = Parser (\s -> [])
  q <|> p = Parser (\s -> runParser q s ++ runParser p s)

Use lazy patterns:

instance Alternative Parser where
  empty = Parser (\s -> [])
  ~(Parser q) <|> ~(Parser p) = Parser (\s -> q s ++ p s)

The first strict pattern is fine, because `<|>` is left-biased. So this could be written `Parser q <|> ~(Parser p) = ...`. But of course the best solution in this case is just to use `newtype`! — dfeuer, Jan 16 '17 at 00:49
Thanks, that helps a lot. I still don't quite understand the relationship between a `data` being evaluated to a WNHF and the problem about `<|>` though. — Procrade, Jan 17 '17 at 01:29

Why does this loops with 'data' but not 'newtype'?

1 Answers1