F# sequence comparison

Question

I have implemented a Fibonacci Sequence generator as follows

let getNext upperLimit current= 
        let (e1, e2) = current
        let next = e1 + e2
        if next > upperLimit then None
        else Some (next, (e2,next))

let fib upperLimit = (0,1) |> Seq.unfold (getNext upperLimit) |> Seq.append [0;1] 

and my test code is

[<Test>]
member Spec.``fib not exeeding 20 should be 0,1,1,2,3,5,8,13``()=
    let expected = seq [0;1;1;2;3;5;8;13] 
    let result = fib 20
    let expectedSameAsResult = (expected = result)
    printfn "Expected: %A  Result: %A result length: %d" expected result (Seq.length result) 
    Assert.That expectedSameAsResult

The test failed and the printed result is

Expected: [0; 1; 1; 2; 3; 5; 8; 13] Result: seq [0; 1; 1; 2; ...] result length: 8

When I used a for loop to print every element in result, I got exact same elements in the expected sequence.

So, what is the difference between the expected and result sequence?

Edit: my implementation can be found at https://github.com/weima/EulerProblems/tree/master/EulerProblems

Edit: To answer John Palmer's answer I just wrote a test in F# interactive window

 let a = seq[1;2;3]
 let b = seq[1;2;3]
 let c = a = b;;

The result I got is val a : seq = [1; 2; 3] val b : seq = [1; 2; 3] val c : bool = true

So F# can do structural comparison to sequences too.

Edit to reflect to Gene Belitski's answer I have changed the test to

[<Test>]
member Spec.``fib not exeeding 20 should be 0,1,1,2,3,5,8,13``()=
    let expected = seq [0;1;1;2;3;5;8;13] 
    let result = Problem2.fib 20
    let comparedResult =  Seq.compareWith (fun a b -> a - b) expected result  
    let expectedSameAsResult = (comparedResult = 0)
    Assert.That expectedSameAsResult

And it worked now. Thanks! but I still don't understand why a simple seq[1;2;3]=seq[1;2;3] works, but my test case doesn't.

Answer 1

Whilst you may expect that a=b would compare elements for sequences it infact a=b computes reference equality.

You can see this with something like

seq {1..3} = seq {1..3}

which returns false.

However, in some cases when you use constants you get confusing results, in particular

seq [1;2;3] = seq [1;2;3]

returns true, which is confusing.

To avoid this issue, you need to do something like

 let test a b = Seq.fold (&&) true (Seq.zip a b |> Seq.map (fun (aa,bb) -> aa=bb))

to compare element wise.

Alternatively, you can use Seq.compareWith as outlined in Gene's answer. However, this requires that the elements also implement a comparison operator as well as equality, which may not be the case for some things like discriminated unions which implement = but not comparison.

Answer 2

Adding to John's answer: sequence equality can be determined with Seq.compareWith library function:

let compareSequences = Seq.compareWith Operators.compare

Then sequence equality would be value of the expression

let expectedSameAsResult = (compareSequences expected result = 0)

Answer 3

MSDN for Operators.seq<'T> function says: Builds a sequence using sequence expression syntax. If you look into its implementation you'll see that it is basically just identity function that has special meaning for the compiler only when used with sequence expression syntax. If you call with list - you'll get the same list back (upcasted to seq<_>).

Re structural equality, per F# spec:

by default, record, union, and struct type definitions—called structural types—implicitly include compiler-generated declarations for structural equality, hashing, and comparison. These implicit declarations consist of the following for structural equality and hashing:

override x.GetHashCode() = ...
override x.Equals(y:obj) = ...
interface System.Collections.IStructuralEquatable with 
    member x.Equals(yobj: obj, comparer: System.Collections.IEqualityComparer) = ...
    member x.GetHashCode(comparer: System.IEqualityComparer) = ...

The following declarations enable structural comparison:

interface System.IComparable with 
    member x.CompareTo(y:obj) = ...
interface System.Collections.IStructuralComparable with 
    member x.CompareTo(yobj: obj, comparer: System.Collections.IComparer) = ...

For exception types, implicit declarations for structural equality and hashings are generated, but declarations for structural comparison are not generated. Implicit declarations are never generated for interface, delegate, class, or enum types. Enum types implicitly derive support for equality, hashing, and comparison through their underlying representation as integers

So lists (essentially unions) - support structural equality and sequences - not. To check elements pairwise you can also use Seq.forall2

let isEqual = (s1, s2) ||> Seq.forall2 (=)