为什么这会循环'数据'而不是'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

这是获得和之间的差异datanewtype的好方法.这里问题的核心实际上是<|>定义的模式匹配.

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

请记住,在运行时,a newtype与它包装的类型变得相同.然后,当a newtype模式匹配时,GHC不做任何事情 - 没有构造函数可以评估为WNHF.

相反,当a 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)
  

• 使用懒惰模式:

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