Is it possible to match with decomposed sequences in F#?

Question

I seem to remember an older version of F# allowing structural decomposition when matching sequences just like lists. Is there a way to use the list syntax while keeping the sequence lazy? I'm hoping to avoid a lot of calls to Seq.head and Seq.skip 1.

I'm hoping for something like:

let decomposable (xs:seq<'a>) =
   match xs with
   | h :: t -> true
   | _ -> false
seq{ 1..100 } |> decomposable

But this only handles lists and gives a type error when using sequences. When using List.of_seq, it seems to evaluate all the elements in the sequence, even if it is infinite.

score 27 · Accepted Answer · edited May 23 '17 at 12:16

27

If you use the LazyList type in the PowerPack, it has Active Patterns called LazyList.Nil and LazyList.Cons that are great for this.

The seq/IEnumerable type is not particulaly amenable to pattern matching; I'd highly recommend LazyList for this. (See also Why is using a sequence so much slower than using a list in this example.)

let s = seq { 1..100 }
let ll = LazyList.ofSeq s
match ll with
| LazyList.Nil -> printfn "empty"
| LazyList.Cons(h,t) -> printfn "head: %d" h

edited May 23 '17 at 12:16

Community

1
1

answered Nov 17 '09 at 15:29

Brian

117,631
17
236
300

6

link here for anyone who (like me) didn't know what the power pack is: http://fsharppowerpack.codeplex.com/ – gatoatigrado Jun 11 '10 at 19:28
LazyList is now a part of `FSharpx.Collections`: https://fsprojects.github.io/FSharpx.Collections/reference/fsharpx-collections-lazylist-1.html – DharmaTurtle Nov 09 '19 at 15:53

score 11 · Answer 2 · edited Aug 15 '21 at 19:18

11

Seq works fine in active patterns! Unless I'm doing something horrible here...

let (|SeqEmpty|SeqCons|) (xs: 'a seq) = 
  if Seq.isEmpty xs then SeqEmpty
  else SeqCons(Seq.head xs, Seq.skip 1 xs)

// Stupid example usage
let a = [1; 2; 3]

let f = function
  | SeqEmpty -> 0
  | SeqCons(x, rest) -> x
  
let result = f a

edited Aug 15 '21 at 19:18

sdgfsdh

33,689
26
132
245

answered Nov 18 '09 at 16:40

Dan Fitch

2,480
2
23
39

3

One trick for instances where you want a single single-quote: Add another single-quote in a comment at the end of the line: // ' – harms Nov 18 '09 at 16:51
8

Its a neat trick, but more than one reliable source indicates that its not a good pattern since evaluating the sequence is O(n^2): http://stackoverflow.com/questions/1306140/f-why-is-using-a-sequence-so-much-slower-than-using-a-list-in-this-example/1306267#1306267 – Juliet Nov 18 '09 at 17:02
1

True, but the questioner's example is not recursive. This is obviously not good for recursing down the sequence, but if you just want to pattern match on the head or something... – Dan Fitch Nov 18 '09 at 22:12

score 1 · Answer 3 · answered Jun 11 '10 at 19:48

Remember seq has map reduce functions as well, so you might often be able to get away with only those. In the example, your function is equivalent to "Seq.isEmpty". You might try to launch fsi and just run through the tab completion options (enter "Seq." and hit tab a lot); it might have what you want.

Is it possible to match with decomposed sequences in F#?

3 Answers3

Linked