Parsing the arrow type with FParsec

Question

I'm trying to parse the arrow type with FParsec. That is, this:

Int -> Int -> Int -> Float -> Char

For example.

I tried with this code, but it only works for one type of arrow (Int -> Int) and no more. I also want to avoid parentheses, because I already have a tuple type that uses them, and I don't want it to be too heavy in terms of syntax either.

let ws = pspaces >>. many pspaces |>> (fun _ -> ())

let str_ws s = pstring s .>> ws

type Type = ArrowType of Type * Type

let arrowtype' =
    pipe2
        (ws >>. ty')
        (ws >>. str_ws "->" >>. ws >>. ty')
        (fun t1 t2 -> ArrowType(t1, t2))

let arrowtype =
    pipe2
        (ws >>. ty' <|> arrowtype')
        (ws >>. str_ws "->" >>. ws >>. ty' <|> arrowtype')
        (fun t1 t2 -> ArrowType(t1, t2)) <?> "arrow type"

ty' is just another types, like tuple or identifier.

Do you have a solution?

Answer 1

Before I get into the arrow syntax, I want to comment on your ws parser. Using |>> (fun _ -> ()) is a little inefficient since FParsec has to construct a result object then immediately throw it away. The built-in spaces and spaces1 parsers are probably better for your needs, since they don't need to construct a result object.

Now as for the issue you're struggling with, it looks to me like you want to consider the arrow parser slightly differently. What about treating it as a series of types separated by ->, and using the sepBy family of parser combinators? Something like this:

let arrow = spaces1 >>. pstring "->" .>> spaces1
let arrowlist = sepBy1 ty' arrow
let arrowtype = arrowlist |>> (fun types ->
    types |> List.reduce (fun ty1 ty2 -> ArrowType(ty1, ty2))

Note that the arrowlist parser would also match against just plain Int, because the definition of sepBy1 is not "there must be at least one list separator", but rather "there must be at least one item in the list". So to distinguish between a type of Int and an arrow type, you'd want to do something like:

let typeAlone = ty' .>> notFollowedBy arrow
let typeOrArrow = attempt typeAlone <|> arrowtype

The use of attempt is necessary here so that the characters consumed by ty' will be backtracked if an arrow was present.

There's a complicating factor I haven't addressed at all since you mentioned not wanting parentheses. But if you decide that you want to be able to have arrow types of arrow types (that is, functions that take functions as input), you'd want to parse types like (Int -> Int) -> (Int -> Float) -> Char. This would complicate the use of sepBy, and I haven't addressed it at all. If you end up needing more complex parsing including parentheses, then it's possible you might want to use OperatorPrecedenceParser. But for your simple needs where parentheses aren't involved, sepBy1 looks like your best bet.

Finally, I should give a WARNING: I haven't tested this at all, just typed this into the Stack Overflow box. The code example I gave you is not intended to be working as-is, but rather to give you an idea of how to proceed. If you need a working-as-is example, I'll be happy to try to give you one, but I don't have the time to do so right now.