CODEWITHSUNDEEP
haskellrecursion
Gilgamesz
Gilgamesz

Reputation: 5073

newtype and recursive definition

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

Hi, Let's consider above definition: On my eye it is infinite definition- recursive definition. For example I defined tree ( recursive, infinite structures) like:

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

And Tree can be inifinite but we have Leaf and it can "finish" recursive definition. So, let's translate my first definition to data: ( just replace newtype- according to https://wiki.haskell.org/Newtype ) 

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

And it is recursive definition and there is no "finite element" like Leaf. How to understand it?

Upvotes: 0

Views: 264

Answers (1)

Chad Gilbert
Chad Gilbert

Reputation: 36385

Your Parser definition is not actually recursive. On the right of the = sign is constructor. Constructors can have the same name as their type but the two things are separate concepts.

You could call the parser constructor something else without losing any functionality:

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

Your Tree type has two constructors, Leaf and Node. The thing that makes it recursive is that the definition of Node recursively includes two type parameters, both of which are Tree.

Upvotes: 8

Related Questions