为什么这会循环'数据'而不是'新类型'？

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"循环，但如果分析器被声明为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)