Understanding this elm url-parser Parser type declaration

Question

Trying to understand evancz/url-parser module, I stumbled upon this type declaration that I struggle to understand: (source)

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

The fact that "Parser" appears as the type name and inside the type definition is particularly troubling.

Could someone make a sentence in English explaining the type annotation ? For instance "Given two abstract types a and b, ... ?"

Many thanks.

Answer 1

There are a few things to unpack here, so let's break it down:

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

type Foo a = Foo a

Type Foo above takes a single type argument and has a single way to create a value of type Foo a, by using its single constructor which happens to share the same name. This lets us define Foos of different types, like so:

fooString : Foo String
fooString = Foo "abc"

fooInt : Foo Int
fooInt = Foo 123

In the above examples, Foo is acting as a container for a string or int value. But that's not all it can hold onto. Since functions are values in Elm, you can have a Foo that holds onto a function. Let's define a function that takes an integer and adds one to it:

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

Now, let's wrap that up in a Foo value:

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

This is completely valid code. A value of type Foo (Int -> Int) is just a wrapper around a function. So now that we're wrapping a function, how can we do something with it? Let's 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 like this runFooIntFunc 3 fooPlusOner, you receive the value 4.

We could generalize this function a little bit to get rid of explicitly using Ints:

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

Now this would work with any function that returns the same type as its input. Let's say we want a Foo function that adds an exclamation mark to any string:

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

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

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

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

Notice that the Parser constructor simply wraps a function of type State a -> List (State b). Unfortunately, the State type is opaque (non-exported) so we can't write code directly against it, but you could define your own state and play around with it.

Without going too far down the implementation details, remember that it's just a wrapper for a certain type of function. So the question could be, why write it this way?

Well, the implementation makes it easier to layer Parsers upon Parsers in a way that hides implementation details, provides a good foundation of primitive parsers, allows an elegant way to layer parsers without having to worry about state. This type of pattern is often seen in functional languages when dealing with parsers and decoders, or anything revolving around state.

It may be helpful to read through this introduction to the State monad inside Haskell. The types are different but many of the underlying concepts are shared.