newtype和递归定义

Question

newtype Parser a = Parser (String -> [(a,String)])

嗨,让我们考虑一下上面的定义:在我看来,它是无限定义 - 递归定义.例如,我定义了树(递归,无限结构),如:

data Tree a = Leaf | Node (Tree a) (Tree a).

并且Tree可以是无限的但我们拥有Leaf并且它可以"完成"递归定义.所以,让我们将我的第一个定义翻译为data:(只需替换newtype-根据https://wiki.haskell.org/Newtype)

data Parser a = Parser (String -> [(a,String)])

它是递归定义,没有"有限元"之类的Leaf.怎么理解呢？

Answer 1

您的Parser定义实际上不是递归的.=标志的右边是构造函数.构造函数可以与其类型具有相同的名称,但这两个元素是不同的概念.

您可以在不丢失任何功能的情况下调用解析器构造函数:

data Parser a = Foo (String -> [(a, String)])

你的Tree类型有两个构造函数,Leaf和Node.使其递归的是递归的定义Node包括两个类型参数,两者都是Tree.