F#: Advanced use of active patterns

Question

Here is my problem: I'm trying to write a parser leveraging the power of active patterns in F#. The basic signature of a parsing function is the following

LazyList<Token> -> 'a * LazyList<Token>

Meaning it takes a lazy list of tokens, and returns the result of the parse and the new list of tokens after parsing, so as to follow functional design.

Now, as a next step, I can define active patterns that will help me match some constructs directly in match expressions, thusly

let inline (|QualName|_|) token_stream =
    match parse_qualified_name token_stream with
        | Some id_list, new_stream -> Some (id_list, new_stream)
        | None, new_stream -> None

let inline (|Tok|_|) token_stream = 
    match token_stream with
        | Cons (token, tail) -> Some(token.variant, tail)
        | _ -> None

and then match parse results in a high level fashion this way

let parse_subprogram_profile  = function
    | Tok (Kw (KwProcedure | KwFunction),
           QualName(qual_name, 
                    Tok (Punc (OpeningPar), stream_tail))) as token_stream ->
        // some code
    | token_stream -> None, token_stream

The problem I have with this code is that every new matched construct is nested, which is not readable, especially if you have a long chain of results to match. I'd like to have the ability to define a matching operator such as the :: operator for list, which would enable me to do the following :

let parse_subprogram_profile  = function
    | Tok (Kw (KwProcedure | KwFunction)) :: 
      QualName(qual_name) :: 
      Tok (Punc (OpeningPar)) :: stream_tail as token_stream ->
        // some code
    | token_stream -> None, token_stream

But I don't think such a thing is possible in F#. I would even accept a design in which I have to call a specific "ChainN" active pattern where N is the number of element I want to parse, but I don't know how to design such a function if it is possible.

Any advice or directions regarding this ? Is there an obvious design I didn't see ?

Answer 1

I had something like this in mind, too, but actually gave up going for this exact design. Something you can do is to use actual lists.

In such case, you would have a CombinedList which is made of (firstly) a normal list acting as a buffer and (secondly) a lazy list.

When you want to match against a pattern, you can do:

match tokens.EnsureBuffer(4) with
| el1 :: el2 :: remaining               -> (el1.v+el2.v, tokens.SetBuffer(remaining))
| el3 :: el4 :: el5 :: el6 :: remaining -> (el1.v-el2.v+el3.v-el4.v, tokens.SetBuffer(remaining))

where EnsureBuffer and SetBuffer may either mutate "tokens" and return it or return it if no change are required or return a new instances otherwise.

Would that solve your problem? François