CODEWITHSUNDEEP
typeselm
AlexHv
AlexHv

Reputation: 1734

Understanding this elm url-parser Parser type declaration

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.

Upvotes: 7

Views: 927

Answers (2)

Chad Gilbert
Chad Gilbert

Reputation: 36375

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.

Upvotes: 9

Igor Drozdov
Igor Drozdov

Reputation: 15045

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

Yes, on a first glance it's a bit confusing, but what's actually needed to be understood in this line:

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

same word Parser is used for convenience.

Let's use different names for a moment:

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

TypeParser is a type constructor. It takes two arguments and returns a type. It's used, for example, when you define another type:

type alias Model = { parser : TypeParser Int Int }

DataParser is a data constructor. It's used to build data, which is going to be of type TypeParser a b

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

Elm allows using the same name for type and data constructors.

There's an exhaustive example in the file link to which you've provided:

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

here's Parser is used in the type annotation.

And also is used to pattern-match on the argument of type Parser a b and to build a value of type Parser (b -> c) c using Parser data constructor in the definition of the function:

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

Upvotes: 3

Related Questions