Laziness/strictness between data and newtype
algebraic-data-types, haskell, lazy-evaluation, newtype
Solution
As you probably know, the main difference between `data` and `newtype` is that with `data` the data constructors are lazy while with `newtype` the data constructors are strict, i.e. given the following types
data D a = D a
newtype N a = N a
then `D ⊥ `seq` x = x`, but `N ⊥ `seq` x = ⊥`.(where `⊥` stands for "bottom", i.e. undefined value or error)
What is perhaps less commonly known, however, is that when you pattern match on these data constructors, the roles are "reversed", i.e. with
constD x (D y) = x
constN x (N y) = x
then `constD x ⊥ = ⊥` (strict), but `constN x ⊥ = x` (lazy).
This is what's happening in your example.
Parser f <*> Parser x = Parser h where ...
With `data`, the pattern match in the definition of `<*>` will diverge immediately if either of the arguments are `⊥`, but with `newtype` the constructors are ignored and it is just as if you'd written
f <*> x = h where
which will only diverge for `x = ⊥` if `x` is demanded.
Problem
I'm struggling to understand why these two snippets produce different results under the so-called "poor man's strictness analysis". The first example uses `data` (assuming a correct Applicative instance): ``` data Parser t a = Parser { getParser :: [t] -> Maybe ([t], a) } > getParser (pure (,) <*> literal ';' <*> undefined ) "abc" *** Exception: Prelude.undefined ``` The second uses `newtype`. There is no other difference: ``` newtype Parser t a = Parser { getParser :: [t] -> Maybe ([t], a) } > getParser (pure (,) <*> literal ';' <*> undefined ) "abc" Nothing ``` `literal x` is a parser that succeeds consuming one token of input if its argument matches the first token. So in this example, it fails since `;` doesn't match `a`. However, the `data` example still sees that the next parser is undefined, while the `newtype` example doesn't. I've read this, this, and this, but don't understand them well enough to get why the first example is undefined. It seems to me that in this example, `newtype` is more lazy than `data`, the opposite of what the answers said. (At least one other person has been confused by this too). Why does switching from `data` to `newtype` change the definedness of this example? Here's another thing I discovered: with this Applicative instance, the `data` parser above outputs undefined: ``` instance Applicative (Parser s) where Parser f <*> Parser x = Parser h where h xs = f xs >>= \(ys, f') -> x ys >>= \(zs, x') -> Just (zs, f' x') pure a = Parser (\xs -> Just (xs, a)) ``` whereas with this instance, the `data` parser above does not output undefined (assuming a correct Monad instance for `Parser s`): ``` instance Applicative (Parser s) where f <*> x = f >>= \f' -> x >>= \x' -> pure (f' x') pure = pure a = Parser (\xs -> Just (xs, a)) ``` Full code snippet: ``` import Control.Applicative import Control.Monad (liftM) data Parser t a = Parser { getParser :: [t] -> Maybe ([t], a) } instance Functor (Parser s) where fmap = liftM instance Applicative (Parser s) where Parser f <*> Parser x = Parser h where h xs = f xs >>= \(ys, f') -> x ys >>= \(zs, x') -> Just (zs, f' x') pure = return instance Monad (Parser s) where Parser m >>= f = Parser h where h xs = m xs >>= \(ys,y) -> getParser (f y) ys return a = Parser (\xs -> Just (xs, a)) literal :: Eq t => t -> Parser t t literal x = Parser f where f (y:ys) | x == y = Just (ys, x) | otherwise = Nothing f [] = Nothing ```