Back to Questions
2.1k
views6
comments
Pattern matching a sequence
f#compiler

I'd like a function that accepts a single parameter p which may or may not be a sequence. If it is a sequence, iterate over each member m, which may or may not be a sequence. If m is a sequence, iterative over each member n, which may or may not be a sequence, and so on. All sequences encountered may have different types, so p may be seq<seq<seq<int>>> or seq<string> or seq<seq<list<'a>>>.

I can't seem to test whether a value is a sequence of an unknown type. A match attempt like,

1
2

  match x with
    | :? seq<'a> -> ...

doesn't work as I would expect. The compiler complains that converting x to seq<'a> involves an indeterminate type. It suggests further type annotations, but I don't know how to remain generic without annotating x with :obj, which forces my pattern to seq<obj>, which doesn't seem to match all sequences!

I find F#'s lack of coercion disturbing... :)

--
Jeff S>

.

I think I figured it out. Here's an example:

1
2
3
4
5
6

let matchSeq x =
  let rec matchSeqInternal (y:obj) =
    match y with
      | :? System.Collections.IEnumerable as s -> IEnumerable.untyped_iter (fun z -> matchSeqInternal (box z)) s;
      | _ -> print_any y in
  matchSeqInternal (box x)

(Would somebody tell me how everybody is pulling off syntax highlighting in this BB?)

The trick was to have an internal function that accepts a typed argument so the outer function doesn't have to.

--
Jeff S.

By on 8/10/2007 8:08 AM ()

Have you tried "boxing" x:

1
2
3
4

let rec f x = if (box x :? seq<_>) then 
                  Seq.iter f x 
              else
                  print_string "not a seq<_>"
By on 8/9/2007 11:44 PM ()

It seems to me F# is not ideal for this part sort problem because everthing is strongly typed and the pattern match instist on knowing the type before you can match, we always leads the wrong type being match. I think I can explain better with some code :)

First I tried this:

1
2
3
4
5
6
7
8

let rec matchSeq x =
    match box x with
    | :? seq<_> as l ->
        let x = Seq.hd l
        matchSeq x
    | _ -> printfn "not a sequence %A" x

matchSeq [1]

This doesn't work because the type of the sequence is excepted to be the same same as the type of sequence you pass in, ie if you pass in an seq<int>, its actually looking for a seq<seq<int>>. This is easier to see when you look at the code decompiled C#:

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

public static void matchSeq<T>(T x)
{
    object obj2;
Label_0000:
    obj2 = x;
    if (!(obj2 is IEnumerable<T>))
    {
        Pervasives.printf<FastFunc<T, Unit>>(new Format<FastFunc<T, Unit>, TextWriter, Unit, Unit>("not a sequence %A")).Invoke(x);
    }
    else
    {
        IEnumerable<T> l = (IEnumerable<T>) obj2;
        x = Seq.hd<IEnumerable<T>, T>(l);
        goto Label_0000;
    }
}

Now the following will work, but because there is no generic parameter the sequence its looking for is typed as obj, which means everything must be typed as obj even sequence elements, if it see a strongly typed sequence it won't match it:

1
2
3
4
5
6
7
8
9
10

let rec matchSeqObj (x : obj) =
    match x with
    | :? seq<_> as l ->
        let x = Seq.hd l
        matchSeq x
    | _ -> printfn "not a sequence %A" x

matchSeqObj (box [1])
matchSeqObj (box [box 1])
matchSeqObj (box [box [box 1]])

Again easier to see exactly whats going when you look at the C#:

1
2
3
4
5
6
7
8
9
10
11
12
13

public static void matchSeqObj(object x)
{
    object obj2 = x;
    if (!(obj2 is IEnumerable<object>))
    {
        Pervasives.printf<FastFunc<object, Unit>>(new Format<FastFunc<object, Unit>, TextWriter, Unit, Unit>("not a sequence %A")).Invoke(x);
    }
    else
    {
        IEnumerable<object> l = (IEnumerable<object>) obj2;
        matchSeq<object>(Seq.hd<IEnumerable<object>, object>(l));
    }
}

Interesting that you seem to have hit on one of very few problems where generics gets in the way rather than helps you out.

Cheers,
Rob

By on 8/10/2007 12:50 AM ()

seq, IEnumerable<T> extend the untyped IEnumerable, so you can just as easily do this:

1
2
3
4
5

let rec matchSeq (x : obj) =
  match x with
  | :? System.Collections.IEnumerable as seq -> 
    IEnumerable.untyped_iter matchSeq seq
  | _ -> printfn "not a sequence %A" x
By on 8/10/2007 4:38 AM ()

seq, IEnumerable<T> extend the untyped IEnumerable, so you can just as easily do this:

1
2
3
4
5

let rec matchSeq (x : obj) =
  match x with
  | :? System.Collections.IEnumerable as seq -> 
    IEnumerable.untyped_iter matchSeq seq
  | _ -> printfn "not a sequence %A" x

I don't want to constrain the type of x, even to obj. If F# did coercion in the right places, that would be fine, but with your code, the following statement produces a runtime error: matchSeq [1;1;1]
--
Jeff S.

By on 8/10/2007 6:12 AM ()

Actually a compile time error. You can instead use "matchSeq (box [1;1;1])".

By on 8/10/2007 6:42 AM ()

    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