Back to Questions
4.6k
views4
comments
Do pattern matching on sequences
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

type tokenStream = LazyList <token * position * position>

let TryToken (src: tokenStream) =


    

    match src with


    

    | LazyList.Cons ((tok, startPos, endPos), rest) -> Some(tok, rest)


    

    | _ -> None
.

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#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.)

By on 11/3/2008 9:43 AM ()

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"?

By on 11/7/2008 12:33 PM ()

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.

By on 11/7/2008 12:45 PM ()

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.

By on 11/2/2008 10:56 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper