Back to Questions
1.2k
views5
comments
How to check seq for idenity?
f#

How do you check seq for identity?

The following snippet spits out "NOT EQUAL":

1
2
3
4
5
6
7
8

 

if { for x in 1..3 -> x } = { for y in 0..2 -> y + 1 } 

then print_endline "equal"

else print_endline "NOT EQUAL"

Thank you in advance.

.

Hi Slavomir,
comparing two seq values is an interesting problem (and I agree that in your example one would expect the use of identity comparison).

In F#, values cunstructed using 'seq' are just objects that implement seq<'a> interface (alias for .NET IEnumerable<T>), so they don't define any advanced comparison behavior (like for example the F# list type) and instead perform basic .NET reference comparison. The best way to perform an identity comparison is either to convert the value to some other type - array (using Seq.to_array) or F# list (using Seq.to_list) or implement your own function to do this. The comparision using a lists can be written like this:

1
2
3
4

 
if ({ for x in 1..3 -> x } |> Seq.to_list) = ({ for y in 0..2 -> y + 1 } |> Seq.to_list)
then print_endline "equal"
else print_endline "NOT EQUAL"

A function to perform the comparison directly using the seq<'a> interface looks like this:

1
2
3
4
5
6
7
8
9
10
11

let compareSeq (a:seq<'a>) (b:seq<'a>) = 
  let ea = a.GetEnumerator()
  let eb = b.GetEnumerator()
  let rec compAux () = 
    let an = ea.MoveNext()
    let bn = eb.MoveNext()
    if (an && bn && (ea.Current = eb.Current)) then compAux () else (not an) && (not bn)
  compAux ()

if (compareSeq { for x in 1..3 -> x } { for y in 0..2 -> y + 1 })
  // ...

I think the main reason why the F# doesn't perform identity comparison by default is that it causes evaluaion of the entire sequence (which may be infinite or may cause any side effects).

By on 9/25/2007 4:34 PM ()

As an aside, your compareSeq function can be written more idiomatically in several different ways. Firstly, I would look for a for_all2 or for_all and combine functions following OCaml. Seq provides the latter, so you can do:

1
2
3

> let compareSeq a b =
    Seq.combine a b |> Seq.for_all (fun (a, b) -> a=b)
val compareSeq : #seq<'b> -> #seq<'b> -> bool

I would avoid writing iterators, IEnumerables and so forth by hand unless you're planning on exporting this functionality from F# to a non-functional language. These kinds of things are just written much more simply and elegantly using ordinary functional constructs.

By on 9/25/2007 8:17 PM ()

Hi,
yes, I agree that iterators should be written explicitly very rarely - and since the comparison function can be implemented using Seq.compare there is no reason for writing an interator in this case.
The reason why I didn't want to use Seq.combine & Seq.for_all is that it would throw an exception for two sequences of different lengths, which can be a problem.

By on 9/26/2007 6:31 AM ()

Thanks for the answers. I just find it hard to remember when = means structural when it means object identity.

How do you manage? Is there a table for which types = is structural identity and for which is object identity?

By on 9/26/2007 8:57 AM ()

Ahh, I just noticed that similar function is already implemented in the F# library (for some reason I missed it when writing the first answer). You can simplify the code and use Seq.compare, which compares sequences element-wise. It takes a function to compare single element as a first argument, so we can use the builtin F# function compare, which works on any F# type:

1
2
3
4
5
6

 
// eq will be '0' when the sequences are identical
let eq = Seq.compare compare { for x in 1..3 -> x } { for y in 0..2 -> y + 1 }

// A function 'compareSeq' (from my previous post) can be written as following:
let compareSeq a b = (Seq.compare compare a b) = 0
By on 9/25/2007 4:41 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