How can I express a type in F# that optionally recurses on itself (infinitely)

As a learning exercise I am try开发者_如何学Cing to implment a parser for the graphviz dot language (The DOT language) using the functional parser library fparsec (FParsec). The language describes graphs.

Looking at the language definition I was compelled to write down the following definition:

let rec pstmt_list = opt(pstmt .>> opt(pchar ';') >>. opt pstmt_list)

Where pstmt and pchar ';' are parsers, .>> and >>. combine an occurence of the left parser with an occurence of the right parser, and opt parsers an optional occurrence of its argument parser as an option value. However this definition does not work complaining "... the resulting type would be infinite ...".

This example is probably most easily understood by taking a look at the DOT language linked above.

I am aware of the following seemingly linked questions:

• Are Infinite Types (aka Recursive Types) not possible in F#?
• Haskell to F# - declare a recursive types in f#

But my F# knowledge may not be sufficient to translate them yet, if they apply here at all.

---

FParsec provides special combinators for parsing sequences. Normally you should prefer these combinators to reimplementing them with a recursive function. You can find an overview of the available combinators for parsing sequences here: http://www.quanttec.com/fparsec/reference/parser-overview.html#parsing-sequences

In this example pstmt_list is a sequence of statements separated and optionally ended by semicolons, so you could easily define the parser as

let pstmt_list = sepEndBy pstmt (pstring ";")

---

The problem is that your pstmt_list parser produces some values of some type, but when you use it in the definition, you wrap the values of this type with additional option type (using the opt combinator).

The F# compiler thinks that the type of the values returned by the parser e.g. 'a should be the same as the wrapped type option 'a (which is, of course, not possible).

Anyway, I don't think that this is quite what you need to do - the .>> combinator creates a parser that returns the result of the second argument, which means that you'll be ignoring all the results of pstmt parsed so far.

I think you probably need something like this:

let rec pstmt_list : Parser<int list, unit> = 
  parse.Delay(fun () ->
    opt(pstmt .>> pchar ';') .>>. opt pstmt_list
    |>> (function Some(prev), Some(rest) -> prev::rest
                | Some(prev), _ -> [prev]
                | _, Some(rest) -> rest
                | _ -> [] ))

The additional use of Delay is to avoid declaring a value that refers directly to itself.