Understanding this ad url-parser elm Parser

Question

Trying to understand the evancz / url-parser module, I came across an ad of this type that I am trying to understand: ( source )

type Parser ab = Parser (State a -> List (State b)) 

The fact that "Parser" appears as a type name and inside a type definition is especially troubling.

Can someone make a suggestion in English explaining the type annotation? For example, "For two abstract types a and b, ...?"

Thank you very much.

Answer 1

There are a few things to unpack here, so let them break:

Type names can have constructors with the same name. This is a valid code:

 type Foo a = Foo a 

The type Foo above takes one type argument and has the only way to create a value of type Foo a using its only constructor that has the same name. This allows us to define different types of Foos, for example:

 fooString : Foo String fooString = Foo "abc" fooInt : Foo Int fooInt = Foo 123 

In the above examples, Foo acts like a container for a string value or int. But this is not all that he is capable of. Since functions are values ​​in Elm, you can have Foo that holds the function. Let it define a function that takes an integer and adds to it:

 plusOne : Int -> Int plusOne = (+) 1 

Now leave this in the Foo value:

 fooPlusOner : Foo (Int -> Int) fooPlusOner = Foo plusOne 

This is a perfectly valid code. A value of type Foo (Int -> Int) is just a wrapper around a function. So now that we are completing a function, how can we do something with it? Let us create a function that runs the function inside fooPlusOner , giving an integer as a starting point:

 runFooIntFunc : Int -> Foo (Int -> Int) -> Int runFooIntFunc val (Foo f) = f val 

If you run this function as follows runFooIntFunc 3 fooPlusOner , you get a value of 4 .

We could generalize this function a bit to get rid of the explicit use of Ints:

 runFooFunc : a -> Foo (a -> a) -> a runFooFunc val (Foo f) = f val 

Now this will work with any function that returns the same type as its input. Say we want the Foo function to add an exclamation mark to any line:

 fooShouter : Foo (String -> String) fooShouter = Foo (\s -> s ++ "!") 

Running runFooFunc "wow" fooShouter will return "wow!" .

Now let's break down what happens in the Parser definition:

 type Parser ab = Parser (State a -> List (State b)) 

Note that the Parser constructor simply transfers a function of type State a -> List (State b) . Unfortunately, the State type is opaque (not exported), so we cannot write code directly against it, but you can define your own state and play with it.

Without stopping too far from implementation details, remember that this is just a wrapper for a certain type of function. So maybe the question is, why write like that?

Well, the implementation makes it easy to split Parsers into Parsers in a way that hides implementation details, provides a good foundation for primitive parsers, allows an elegant way to align parsers without worrying about state. This type of pattern is often found in functional languages ​​when working with parsers and decoders or something that revolves around a state.

It may be useful to read this introduction to State monad inside Haskell. The types are different, but many of the basic concepts are separated.

Answer 2

The fact that "Parser" appears as a type name and inside a type definition is especially troubling.

Yes, at first glance this is a bit confusing, but what you really need to understand in this line:

 type Parser ab = Parser (State a -> List (State b)) 

the same word Parser used for convenience.

Let us use different names for a moment:

 type TypeParser ab = DataParser (State a -> List (State b)) 

TypeParser is a type constructor. It takes two arguments and returns a type. It is used, for example, when defining another type:

 type alias Model = { parser : TypeParser Int Int } 

DataParser - constructor data strong>. It was used to create data that will be of type TypeParser ab

 parser = DataParser (\state -> [state]) 

Elm allows you to use the same name for the type and data constructors.

Here is the example you provided in the link to the file:

 map : a -> Parser ab -> Parser (b -> c) c 

here Parser used in type annotation.

It is also used to match patterns by an argument of type Parser ab and to construct a value of type Parser (b -> c) c using the Parser data constructor in the function definition:

 map subValue (Parser parse) = Parser <| \{ visited, unvisited, params, value } -> List.map (mapHelp value) <| parse <| { visited = visited , unvisited = unvisited , params = params , value = subValue }