haskell - 为什么这个循环使用 'data' 而不是 'newtype' ？

Question

这是代码:

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)]
                  _ -> []
              )

使用当前代码，runParser (some item) "abcd" 会循环，但如果 Parser 声明为 newtype，它就可以正常工作。

Answer 1

这是获取the difference between data and newtype 之一的好方法。 。这里问题的核心实际上是 <|> 的模式匹配。定义。

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

请记住，在运行时， newtype变得与它所包装的类型相同。然后，当 newtype模式匹配，GHC 不执行任何操作 - 没有构造函数来评估 WNHF。

相反，当 data已匹配，看到模式 Parser q告诉 GHC 它需要将该解析器评估为 WNHF。这是一个问题，因为some是 <|> 的无限折叠。有两种方法可以解决 data 的问题:

• 没有Parser <|> 中的模式:

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

• 使用lazy patterns :

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