hubFS: THE place for F#

Chapter 16 of "Expert F#" shows an example of using LazyList and pattern-matching to implement a recursive descent parser.
Unfortunately LazyList has since been deprecated, and one is advised to use Seq instead.

The question is how to rewrite tryToken using sequences:

type tokenStream = LazyList <token * position * position>

let TryToken (src: tokenStream) =
    
match src with
    
| LazyList.Cons ((tok, startPos, endPos), rest) -> Some(tok, rest)
    
| _ -> None

Seq doesn't play well with Cons/Nil pattern matching. You can use Seq.hd, Seq.take, Seq.skip to break up a sequence but if you use them recursively you'll probably hit a performance snag.

If you can encapsulate the control by calling other methods from the Seq module (rather than pattern-matching), then I would suggest doing that.

But there are other times where you do need this fine control on the consuming end (e.g. a parser that may backtrack, but also wants to throw away data from the stream it has already consumed 'for good'), and in this case you really need LazyList.  We'll keep LazyList around in the power pack (it won't go away), as there are some scenarios like this that seq cannot handle as well.

Here's a handy function that lets you pattern match seqs by converting them to LazyList under the hood.

#r "FSharp.PowerPack.dll"

let rec (|SeqCons|SeqNil|) (s:seq<'a>) =
    match s with
    | :? LazyList<'a> as l ->
        match l with
        | LazyList.Cons(a,b) -> SeqCons(a,(b :> seq<_>))
        | LazyList.Nil -> SeqNil
    | _ -> (|SeqCons|SeqNil|) (LazyList.of_seq s :> seq<_>)
   
   
let rec f s =
    match s with
    | SeqCons(h,t) -> f t
    | SeqNil -> printfn "all done here"

let s = (seq { for i in 0 .. 10000000 do
                 yield i})

(One small caveat is that LazyList.of_seq doesn't dispose its IEnumerator.)

Thanks for the info. I'm glad to see LazyList is staying, I think they fit in nicely in parsing.
Does the fact that LazyList.of_seq does not dispose its IEnumerator mean that resources such as file descriptors used in the seq expression may "leak"?

Yes, though I doubt this is a big issue in practice.  In 1.9.6.2 LazyList never disposes its IEnumerator; in a future release we'll have a fix so it will dispose it if you traverse the LazyList to the end (assuming the underlying seq is not infinite and there is an end), to provide more deterministic behavior when you need it.