F sharp parameterized types - cartesian product

user_2162871 0
Viewed 68

Scott Wlaschin has a great tutorial on parser combinators.

In it is this code:

type Result<'a> =
    | Success of 'a
    | Failure of string

type Parser<'a>  = Parser of (string -> Result<'a * string>)

I understand that the Result type is paramaterized by 'a, and that objects constructed with Parser contain a function from string to Result<'a * string>.

I don't understand the <'a * string>. I know it's the cartesian product, and that Result can be either a Success of 'a or a Failure of string, but the type of Result is Result<'a> not Result<'a * string>.

Clearly I am missing something, and I'd be grateful for some help!

thanks in advance

f# types
2 Answers

Those are not the same 'a. There is one 'a in the definition of Result and a totally different, unrelated 'a in the definition of Parser.

For the purposes of further explanation, I'm going to rename one of them, otherwise it's just going to be verbal spaghetti:

type Result<'a> =
    | Success of 'a
    | Failure of string

type Parser<'b>  = Parser of (string -> Result<'b * string>)

So here, inside the definition of Parser, we use Result, and give it 'b * string as parameter. Therefore, inside the definition of Result, 'a = 'b * string.

Which in turn means that there are two possible values:

  1. Success of ('b * string)
  2. Failure of string

The meaning of this is that a parser can either fail (returning an error as a string) or succeed, in which case it returns the resulting parsed value 'b plus the "remainder" (aka "unconsumed part") of the input text.

From your comments it seems like you may be getting tripped up on the fact that 'a * string seems to mirror Result cases Success of 'a and Failure of string.

This seeming symmetry is a pure coincidence. The Parser type just needed that to be 'a * string for reasons completely unrelated to how the Result type itself is structured.

For further illustration, here are some other equally valid types:

type T = Result<int>
type U = Result<bool list>
type V<'a> = Result<int * 'a * string>
type W = Result<Result<float>>
type F<'q> = 'q -> Result<obj>
type G = Result<string> -> int
type H<'a, 'b, 'c> = Result<'a> -> Result<'b> -> Result<'c>
user_1802860

Perhaps the blog post might explain a little better.

It may be clearer if we replace 'a with a real example. Say you wanted to parse a char, you'd create a Parser<char>. That parser would contain a function string -> Result<char * string>. In the context of Result<'a>, 'a is char * string - it's not the same 'a as Parser<'a>.

The result of that function would, then, either be Success of (char * string) or Failure of string.

In the Success case, char * string is a tuple - the first item is the char parsed, the second item is the remaining string. The idea would be that if parsing "ABC" the result might be Success ('A', "BC").

In the Failure case, string is some error message - e.g. Failure ("Expecting 'A'. Got 'Z'").

user_13208450
Related