数据和新类型之间的懒惰/严格 [英] Laziness/strictness between data and newtype

问题描述

我正在努力理解为什么这两个摘要在所谓的穷人的严格性分析"下产生不同的结果.

I'm struggling to understand why these two snippets produce different results under the so-called "poor man's strictness analysis".

第一个示例使用data(假设正确的Applicative实例):

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

第二个使用newtype.没有其他区别:

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是一个解析器，如果其参数与第一个令牌匹配，则会成功使用一个输入令牌.因此，在此示例中，由于;与a不匹配，因此失败.但是，在data示例中仍然看到下一个解析器是未定义的，而在newtype示例中则没有.

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).

为什么从data切换到newtype会更改此示例的定义?

Why does switching from data to newtype change the definedness of this example?

这是我发现的另一件事:在此Applicative实例中，上面的data解析器输出未定义:

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))

与此实例相比，上面的data解析器不会 not 输出未定义(假设Parser s的Monad实例正确):

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

推荐答案

您可能已经知道，data和newtype之间的主要区别在于，对于data，数据构造函数是惰性的，而对于newtype，数据构造函数很严格，即具有以下类型

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

然后D ⊥ `seq` x = x，但N ⊥ `seq` x = ⊥.^{(其中⊥代表底部"，即未定义的值或错误)}

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

然后constD x ⊥ = ⊥(严格)，但constN x ⊥ = 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 ...

对于data，<*>定义中的模式匹配将立即偏离 的参数是⊥，但是使用newtype时，构造函数将被忽略，它是 就像你写

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

仅在需要x时才会对x = ⊥发散.

which will only diverge for x = ⊥ if x is demanded.

这篇关于数据和新类型之间的懒惰/严格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！