Laziness/strictness between data and newtype

Question

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

Answer 1

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.

Answer 2

The difference between data and newtype is that data is "lifted" and newtype isn't. That means the data has an extra ⊥ -- in this case, it means that undefined /= Parser undefined. When your Applicative code pattern-matches on Parser x, it forces a ⊥ value if the constructor.

When you pattern-match on a data constructor, it's evaluated and taken apart to make sure it's not ⊥. For example:

λ> data Foo = Foo Int deriving Show
λ> case undefined of Foo _ -> True
*** Exception: Prelude.undefined

So pattern matching on a data constructor is strict, and will force it. A newtype, on the other hand, is represented in exactly the same way as the type its constructor wraps. So matching on a newtype constructor does absolutely nothing:

λ> newtype Foo = Foo Int deriving Show
λ> case undefined of Foo _ -> True
True

There are probably two ways to change your data program such that it doesn't crash. One would be to use an irrefutable pattern match in your Applicative instance, which will always "succeed" (but using the matched values anywhere later might fail). Every newtype match behaves like an irrefutable pattern (since there's no constructor to match on, strictness-wise).

λ> data Foo = Foo Int deriving Show
λ> case undefined of ~(Foo _) -> True
True

The other would be to use Parser undefined instead of undefined:

λ> case Foo undefined of Foo _ -> True
True

This match will succeed, because there is a valid Foo value that's being matched on. It happens to contained undefined, but that's not relevant since we don't use it -- we only look at the topmost constructor.

---

In addition to all the links you gave, you might find this article relevant.