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 (=)

Answer 4

For anyone finding this answer who just wants an easy way to compare two sequences, there's an alternative to Seq.compareWith:

There's a .NET method Enumerable.SequenceEqual. I use this all the time when testing.

Example usage:

let sequenceA = seq { 1..5 }
let sequenceB = seq { 1..5 }

Enumerable.SequenceEqual (sequenceA, sequenceB) // True

Answer 5

The reason:

Structural equality is not supported for sequences.

If you think of a seq as a .NET IEnumerable<T> perhaps this makes more sense? Here seq [1;2;3] = seq [1;2;3] is an unfortunate coincidence. Consider a non-pure seq:

let rnd = System.Random()
let x = seq { yield rnd.Next() }
printfn "x is %A" x
printfn "x is %A" x

Result:

x is seq [372511654]
x is seq [1026368248]

val rnd : System.Random
val x : seq<int>

The obvious answer:

Use list instead of seq here.

[<Test>]
member Spec.``fib not exeeding 20 should be 0,1,1,2,3,5,8,13``()=
    let expected = [0;1;1;2;3;5;8;13] 
    let result = fib 20 |> Seq.toList
    let expectedSameAsResult = (expected = result)

The details:

See the other answers.