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
Strictness analysis Optimising compilers like GHC try to reduce the cost of laziness using strictness analysis, which attempts to determine which function arguments are always evaluated by the function, and hence can be evaluated by the caller instead.
In Haskell, the newtype declaration creates a new type from an existing one. For example, natural numbers can be represented by the type Integer using the following declaration: newtype Natural = MakeNatural Integer. This creates an entirely new type, Natural, whose only constructor contains a single Integer.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With