Does F# Seq.sort return a copy of the input sequence?

Question

Here is some unexpected (by me) behaviour in F#. I have a simple class that sorts a sequence :

type MyQueue<'a when 'a : comparison> ( values : 'a[] )  = 

    let vals =
        Seq.sort values

    member this.First = Seq.nth 0 vals

    override this.ToString() =
        Seq.fold ( fun s a -> s + a.ToString() + ";" ) "" vals

I have written a slightly contrived unit test (in C#) to test this:

private class TestObject : IComparable
    {
        public TestObject( double Value )
        {
            this.Value = Value;
        }

        public void Update(double NewValue)
        {
            this.Value = NewValue;
        }

        public double Value { get ; private set; }

        public int CompareTo(object Comparable)
        {
            return this.Value.CompareTo( (Comparable as TestObject).Value );
        }

        public override string ToString ()
        {
            return Value.ToString();
        }
    }

    [Test]
    public void TestUpdate_OK()
    {

        var nums = new double[]{7,4,3,12,11,3,8};

        var values = nums.Select( n => new TestObject(n) ).ToArray();

        var q = new MyQueue<TestObject>( values );

        Console.WriteLine ( q.ToString() );

        // update one of the values in the collection - should not re-sort the collection
        values[3].Update( 2.0 );

        Console.WriteLine ( q.ToString() );

        Assert.AreEqual( q.First.Value, 3.0 );
    }

the Seq.sort does sort the sequence, and the first output is correct :

3;3;4;7;8;11;12;

However, updating the test (reference type) object causes the sequence to be re-sorted :

2;3;3;4;7;8;11;

I expected that the vals in the MyQueue object would now be unsorted, since the value in the reference object has changed, but the Seq.sort appears to have been performed again. I don't understand, I thought the object of functional programming was to avoid side effects. Why do I get this behaviour?

Answer 1

The cause of this is the statement let vals = Seq.sort values is not actually sorting the values until some code consumes the vals variable i.e what your Seq.fold does in toString method, it consumes the vals sequence and at that time the sorting happens and whatever values are there in the values array at that time, those values are sorted, so basically the sorting is happening at the time when you call toString method.

Also, I won't call it FP :) as you are basically doing OOPs by creating type with private state and that state is accessed by type members.

Your problem is related to how sequences works and not in general applicable to FP.

Answer 2

Does F# Seq.sort return a copy of the input sequence?

Yes. What else could it do – to change the order of a set of value types you need to copy (true in all .NET languages).

(This includes LINQ operators in C# and VB: the lazy aspect is that the copy is only made when the first copied element is needed, and at that point a complete new collection is created.)

Answer 3

You can actually check this directly in the sourcecode for f# here but in short what it does is call Seq.toArray, sort the array in place and return that array back as the sequence.