Структурное равенство и структурное сравнение в F#

В общем и целом, данные вопросы вряд ли вызывают серьезные затруднения, однако разобраться в некоторых нюансах, как мне кажется, будет интересно.

Структурное равенство

Начнем с простого примера. Создадим консольное приложение на C# и в методе Main напишем простой код

            Console.WriteLine("(new int[] {{ 1,2,3}}) == (new int[] {{ 1, 2, 3 }}) => {0}", (new int[] { 1,2,3}) == (new int[] { 1, 2, 3 }));

Здесь мы создаем два целочисленных массива, инициализированных одним и тем же набором чисел, сравниваем их и, вполне ожидаемо, получаем False. Ожидаемо, поскольку вполне очевидно, что это два разных массива, а сравниваются они по ссылке безотносительно того, какое у них содержимое.

Теперь выполним аналогичную операцию, но уже в проекте F#

    [|1;2;3|] = [|1;2;3|] |> printfn "[|1;2;3|] = [|1;2;3|] => %b"

Здесь это тоже два разных массива, однако результат будет противоположным, что тоже вполне логично: массивы одного типа, одного размера, имеют одинаковое содержимое и выстроенное в одном порядке.  Если в двух словах, то это как раз и есть то, о чем здесь пойдет речь.

Итак, мы выяснили, что массивы структурно равны если они имеют один тип, одну длину и все их элементы, стоящие на одинаковых позициях равны попарно. Аналогичные правила применяются и к спискам. Можно также убедиться, что и с последовательностями это тоже работает, однако, если написать так

let seq1 = [1;2;3] |> Seq.ofList

let seq2 = [1;2;3] |> Seq.ofList

let seq3 = Seq.initInfinite (fun i -> i % 3)

let seq4 = Seq.initInfinite (fun i -> i % 3)

seq1 = seq2 |> printfn "seq1 = seq2 => %b"

seq3 = seq4 |> printfn "seq3 = seq4 => %b"

То результат True мы получим только для первой пары, здесь, я думаю долгие разъяснения не нужны, поскольку равенство бесконечных последовательностей проверить не выйдет. Но сравнивать их тоже можно, просто результат всегда будет False.

Кортеж хоть и не является коллекцией, но у него все элементы строго зафиксированы на своих позициях, так что сравнение двух однотипных кортежей не составляет труда, поскольку у них на одних позициях находятся элементы одного типа.

В записях сравниваются одноименные поля и это тоже не вызывает проблем.

При сравнении размеченных объединений сначала проверяется, принадлежат ли они одному кейсу или нет, для того, чтобы объекты были равны надо чтобы они принадлежали одному кейсу и там уже сравнение происходит по тому же принципу, что и сравнение кортежей.

В F# таким же образом можно сравнивать и структуры. Например, если мы добавим в решение библиотеку классов на C# и создадим в ней структуру со следующим кодом

    public struct CsXyz

    {

        public CsXyz(int x, int y, int z, int secret)

        {

            X = x;

            Y = y;

            Z = z;

            Secret = secret;

        }

        public int X;

        public int Y;

        public int Z;

        private int Secret;

    }

То в F# экземпляры такой структуры можно сравнивать. Причем вот такой код

    CsXyz(1,2,3, 0) = CsXyz(1,2,3, 1) |> printfn "CsXyz(1,2,3, 0) = CsXyz(1,2,3, 1) => %b"

Возвратит False, что указывает на то, что при сравнении проверяются значения не только публичных полей, но и приватных тоже. А в C# попытка сравнить экземпляры этой же структуры вызовут ошибку компиляции.

Для классов по умолчанию поддерживается только ссылочное равенство, а функции вообще не могут проверяться на равенство, это вызовет ошибку компиляции.

Естественно, все описанное является поведением по умолчанию и может быть переопределено. Более подробно об этом можно почитать у Дона Сайма
Equality and Comparison Constraints in F#.

Равенство сложных типов

Несмотря на то, что объекты, сравнивавшиеся ранее, не были экземплярами простых типов, тем не менее интересно рассмотреть ситуацию, когда, например, список содержит не числа, а, скажем, кортежи, элементами которых будут не только объекты простых типов, но и тех же кортежей, списков, записей и т. д. На самом деле здесь все достаточно просто: поскольку, скажем, элементы списка сравниваются почленно, то к членам будут применяться правила сравнения того типа, которому принадлежат эти члены и далее эти правила будут применяться рекурсивно. Однако, пару моментов все-таки следует рассмотреть.

Первый момент – это поведение процесса сравнения в случае, если в структуре типа присутствует тип, поддерживающий только ссылочное равенство. Ну, например, создадим вот такой класс

type FsX(x: int) =

    member this.X = x

И попробуем сделать так

(1, "qww", FsX(1)) = (1, "qww", FsX(1)) |> printfn "Tuples with different FsX => %b"

Ошибки это не вызовет, однако в результате мы получим False, поскольку экземпляры классов будут сравниваться по ссылке, что и приведет к данному результату, хотя объекты инициированы одинаково, но здесь это не играет роли. А вот такой вариант даст вполне положительный ответ

let fsx = FsX(1)

(1, "qww", fsx) = (1, "qww", fsx) |> printfn "Tuples with single FsX => %b"

Что до варианта с функцией или любым другим объектом, не поддерживающим проверку на равенство, то в этом случае компилятор сразу укажет нам, что подобное сравнение недопустимо. Следующий код не скомпилируется.

(1, id) = (1, id) |> printfn "%b"

Таким образом из-за невозможности сравнить 'a -> 'a, мы также не можем сравнивать и int*('a -> 'a), равно как и все, что содержит этот тип. (Строго говоря, так было не всегда, но для текущей версии этот так, а в более ранних версиях сравнение функций тоже возвращало False).

Зачем это нужно

Помимо каких-то частных случаев, кода какие-то данные приходят из разных источников и требуется их сравнить, можно выделить несколько и более общих ситуаций. Например, это очень удобно использовать в модульных тестах, когда нужно протестировать некую функцию, если мы знаем какой результат она должна возвратить при передаче ей определенных аргументов, то достаточно сформировать такой же объект и просто сравнить его с тем, что возвратит функция. Обычное использование Assert.AreEqual, там, где я это пробовал, может и не сработать, но можно сделать так
Assert.AreEqual(o1 = o2, true, message)
И это прекрасно работает.

Структурного равенства требуют многие часто используемые функции, например, distinct, groupBy, except. Также любые объекты, поддерживающие структурное равенство могут быть использованы как ключи в различных словарях. Пример с ранее созданными структурой и классом это иллюстрирует

    let dic = Dictionary()

    dic.Add(CsXyz(1,2,3,4), 1)

    dic.ContainsKey(CsXyz(1,2,3,4)) |> printfn "Dictionary contains struct key -> %b"

    let dic2 = Dictionary()

    dic2.Add(FsX(1), 1)

    dic2.ContainsKey(FsX(1)) |> printfn "Dictionary contains class key -> %b"

Пример из мира Судоку (лирическое отступление)

Рассмотрим один из методов, используемых для решения Судоку. Метод называется «Метод открытых пар» или в более расширенном виде вместо пар могут быть тройки, четверки и т. д. Чтобы не путаться назовем его методом открытых групп, где под группами подразумеваются пары, тройки, четверки …

Опишу суть метода. Метод применяется изолированно к строке, столбцу или малому квадрату, опять-таки чтобы не путаться назовем строку, столбец или квадрат – диапазоном. Ячейки диапазона содержат либо найденное число, либо набор возможных кандидатов для этой ячейки, которые в ней остались после исключения тех кандидатов, которые по тем или иным причинам появиться в этой ячейке не могут. Наша задача удалить лишних кандидатов, которых можно выявить данным методом. Начнем с открытых пар. Открытой парой называется набор из двух кандидатов, который появляется в одном диапазоне ровно два раза. Наличие такого набора в диапазоне позволяет исключить этих кандидатов из всех остальных мест этого же диапазона. Ну на самом деле, если, скажем, кандидаты 2 и 5 появляются в ячейках с индексами 4 и 8, то это означает, что, либо 2 разместится в ячейке 4, а 5 – в ячейке 8, либо наоборот, а если одно из этих чисел будет вставлено в другую ячейку, то для этих двух ячеек останется только один кандидат, а это нарушает правила. Для троек правило состоит в том, что набор ровно из трех кандидатов находится ровно в трех местах одного диапазона и это означает, что все три кандидата могут быть исключены из всех остальных наборов диапазона. Для четверок, пятерок и т. д. – принцип тот же.

Здесь нужно сказать, что если четверки еще могут появиться в реальном Судоку, то насчет групп большей длины я сильно сомневаюсь. Но мы будем решать задачу в общем виде и даже если это будет Суперсудоку 100х100 или еще больше, то правила те же. Наша задача найти все открытые группы, независимо от размеров Судоку и удалить лишних кандидатов.

Если предположить, что общее поле игры задано двумерным массивом, то диапазоны можно получать с помощью срезов, при этом, если это квадрат, то его придется малость изменить. Таким образом мы пишем функцию, принимающую одномерный массив, представляющий диапазон, элементами массива при этом будут списки кандидатов. Если список пуст – это ошибка, если там одно число – это найденное число, во всех остальных случаях это списки кандидатов. Также будем предполагать, что из каждого этапа обработки списки выходят отсортированными по возрастанию, так что сортировку на входе мы выполнять не будем.

Для тестирования нашей функции будем использовать следующую структуру данных

let testexamples =

    [

    ([|[1;2];[1;3];[4;5;6];[1;2];[2;4;8;9];[1;5;7];[3;6;8];[2;5;7];[1;2;8;9]|],[|[1;2];[3];[4;5;6];[1;2];[4;8;9];[5;7];[3;6;8];[5;7];[8;9]|])

    ([|[4;5;6];[1;3];[4;5;6];[1;2;7];[2;4;6;8;9];[1;5;7];[4;5;6];[2;5;7];[1;2;4;5]|],[|[4;5;6];[1;3];[4;5;6];[1;2;7];[2;8;9];[1;7];[4;5;6];[2;7];[1;2]|])

    ([|[4;6;8;9];[1;3;4];[4;6;8;9];[1;2;4;8];[4;6;8;9];[1;5;6;7;9];[4;5;6];[2;4;5;6;7;8;9];[4;6;8;9]|], [|[4;6;8;9];[1;3];[4;6;8;9];[1;2];[4;6;8;9];[1;5;7];[5];[2;5;7];[4;6;8;9]|])

    ([|[1;2];[1;3];[4;5;6];[1;2];[2;4;8;9];[4;5;6];[3;6;8];[4;5;6];[1;2;8;9]|],[|[1;2];[3];[4;5;6];[1;2];[8;9];[4;5;6];[3;8];[4;5;6];[8;9]|])

    ]

Здесь мы имеем список кортежей, каждый кортеж состоит из двух элементов, первый из которых – массив, который мы будем передавать функции, а второй – тот массив, который мы ожидаем получить на выходе.

В первом кортеже у нас отрытая пара [1;2] на позициях 0 и 3. Во втором – открытая тройка [4;5;6]. В третьем – открытая четверка [4;6;8;9], в четвертом – открытая пара [1;2] и открытая тройка [4;5;6]

Сама функция

let findOpen (rng: array) =

    let iv =

        rng

        |> Array.mapi (fun i il -> i, il)

        |> Array.groupBy snd

        |> Array.map (fun (i, li) -> li |> Array.map fst |> List.ofArray, i)

        |> Array.filter (fun (ixl, cndl) -> List.length ixl > 1 && List.length ixl = List.length cndl)

        |> Array.map (fun (ixl, cndl) -> [0..rng.Length] |> List.except ixl |> List.map (fun ix -> ix, cndl))

        |> List.ofArray

        |> List.collect id

        |> List.groupBy fst

        |> List.map (fun (x, y) -> x, y |> List.collect snd)

        |> Map.ofList

    rng

    |> Array.mapi (fun i cl ->

    if iv.ContainsKey i

    then cl |> List.except iv.[i]

    else cl)

А тестировать ее будем следующей строкой кода

testexamples |> List.forall (fun (x,y) -> y = findOpen x) |> printfn "test findOpen result -> %b"

При тестировании мы использовали структурное равенство, когда сравнивали ожидаемый объект с тем, который был возвращен функцией и для этого нам понадобилась одна строка кода, хотя сравнивались достаточно сложные структуры данных (массивы списков чисел). Но дело не только в этом.

Чтобы понять для чего я привел этот пример нужно немного разобраться как работает эта функция.

        rng

        |> Array.mapi (fun i il -> i, il)

Здесь я из первоначального массива получаю массив кортежей, первыми элементами которых является индекс в диапазоне, а вторым – список кандидатов, соответствующих этому индексу.

        |> Array.groupBy snd

В этой строчке элементы массива группируются по списку кандидатов. То есть мы ищем открытые группы, то есть нам нужно найти такие позиции в массиве, где будут находиться одни и те же списки кандидатов. То есть, после такой группировки в первом тестовом примере, где у нас присутствовала открытая пара [1;2] на позициях 0 и 3, у нас получится массив объектов, среди которых нас будет интересовать объект со следующей структурой данных

([1; 2], [|(0, [1; 2]) ; (3, [1; 2])|])

Структура данных здесь оказывается довольно сложной, неудобной, да и одни и те же данные повторяются несколько раз, поэтому мы ее меняем в следующей операции

        |> Array.map (fun (i, li) -> li |> Array.map fst |> List.ofArray, i)

В результате чего элементы нашего массива превращаются в кортежи, в которых первый элемент – это список индексов, а второй список кандидатов. То есть, интересующий нас объект из первого тестового примера на этом этапе принимает вид

([0; 3], [1; 2])

Открытые группы характеризуются тем, что в них количество и кандидатов равно количеству мест, где они находятся, поэтому нам интересны только те объекты, у которых длина первого списка равна длине второго и они должны иметь больше одного элемента

        |> Array.filter (fun (ixl, cndl) -> List.length ixl > 1 && List.length ixl = List.length cndl)

На этом этапе в первом тестовом примере останется только ([0; 3], [1; 2]), а вот, например, в последнем, где у нас две таких группы (пара и тройка) у нас останутся два элемента

[|([0; 3], [1; 2]); ([2; 5; 7], [4; 5; 6]) |]

Мы нашли группы, сопоставили их индексам, в которых эти присутствуют, но нам надо найти индексы, из списков кандидатов которых нужно удалить элементы открытых групп, таким образом списки индексов нам нужно инвертировать, ну то есть в девятиместном массиве индексы 0 и 3 надо заменить на 1 2 4 5 6 7 8. Таким образом мы сопоставим индексы элементам, которые нужно удалить из списков кандидатов, расположенным по этим индексам, сопоставим каждому индексу список кандидатов на удаление и вывалим это все в один общий список.

        |> Array.map (fun (ixl, cndl) -> [0..rng.Length] |> List.except ixl |> List.map (fun ix -> ix, cndl))

        |> List.ofArray

        |> List.collect id

В результате мы получим список кортежей (индекс, список кандидатов), это собственно то, что мы и хотим, только с одной оговоркой. Если в диапазоне встречается более одной открытой группы, то этот список будет содержать повторяющиеся индексы с разными списками, полученными от разных групп. Поэтому нам нужно объединить их таким образом, чтобы каждый индекс встречался только один раз содержал полный список кандидатов на удаление.

        |> List.groupBy fst

        |> List.map (fun (x, y) -> x, y |> List.collect snd)

Сначала мы группируем список по индексу, а потом приводим результат к простому виду.

В заключении, создаем из этого списка карту

        |> Map.ofList

Теперь у нас карта iv содержит индексы диапазона в качестве ключей, и кандидатов на удаление – в качестве значений, и мы можем с помощью функции mapi заменить в диапазоне списки, содержащие лишних кандидатов: если индекс есть среди ключей карты, удаляем из списка кандидатов то, что соответствует этому ключу, в противном случае оставляем список без изменений.

    rng

    |> Array.mapi (fun i cl ->

    if iv.ContainsKey i

    then cl |> List.except iv.[i]

    else cl)

Получилось длинно, но к чему я это все написал? Дело в том, что уже вначале этого кода я воспользовался структурным равенством списков, а именно в том самом месте, где я сделал вот так

    |> Array.groupBy snd

Выполнялась группировка по второму элементу кортежа. Но вторым элементом кортежа у нас был список кандидатов и если бы списки не поддерживали структурного равенства, то их невозможно было бы использовать в качестве ключей группировки. Как мне кажется, этот пример (не самый сложный, кстати) достаточно хорошо показывает, насколько важна та характеристика, о которой мы говорим для решения проблем обработки данных.

Структурное сравнение

Под структурным сравнением (structural comparison) понимается поддержка объектами возможности сравнивать их на предмет «больше-меньше». Тут, естественно, сразу возникает вопрос: а как вообще можно определенно сказать, что, скажем, один массив больше другого? С числами все понятно, можно еще как-то понять сравнение строк (сортируются же они как-то), но вот как быть со сложными объектами? Почему массив [|1;3;2|] больше массива [|1;2;3|] и что это должно означать?

Чтобы разобраться с тем, как сравниваются коллекции, заглянем в исходники ядерной библиотеки языка, например со строки 1014 мы можем увидеть следующий код

and GenericComparisonObjArrayWithComparer (comp:GenericComparer) (x:obj[]) (y:obj[]) : int  =

    let lenx = x.Length

    let leny = y.Length

    let c = intOrder lenx leny

    if c <> 0 then c

    else

        let mutable i = 0

        let mutable res = 0 

        while i < lenx do

            let c = GenericCompare comp ((get x i), (get y i))

            if c <> 0 then (res <- span=""> c; i <- span=""> lenx)

            else i <- span=""> i + 1

        res

Несложно заметить, что здесь оба массива обходятся поэлементно (как и при сравнении на равенство), но как только обнаруживается пара элементов, не равных друг другу, происходит завершение цикла и возвращается тот самый результат, что вернет сравнение этих, первых попавшихся неравных элементов. (здесь стоит напомнить, что методы типа Compare обычно принимают сравниваемые элементы и возвращают отрицательное число в случае если первый аргумент меньше второго, положительное, если больше и ноль – если аргументы равны).

Таким образом мы выяснили, что массивы, а также (как несложно проверить) другие виды коллекций (списки, последовательности), а кроме того и кортежи, что также легко проверяется сравниваются по тому же принципу, что и строки при упорядочивании их в алфавитном порядке. То есть сравниваются попарно элементы в порядке следования и первая попавшаяся пара, в которой элементы не равны определит какая из коллекций больше или меньше. Здесь стоит добавить (проверено), что если в процессе проверки одна коллекция закончилась раньше, чем были найдены разные элементы, то большей будет считаться та, в которой элементы еще остались.

Мы выяснили, что для выполнения такого сравнения важен не только состав, но порядок следования элементов. Но как быть с объектами, у которых не определен порядок. Например, запись, доступ к ее полям осуществляется по имени, а не по индексу или порядку следования.

Проведем маленький эксперимент. Создадим запись следующего вида

type XyzRecord = {

    X:int

    Y:int

    Z:int

    }

Теперь сравним две таких записи

    {X=1;Y=2;Z=3} < {X=1;Y=3;Z=2} |> printfn "Compare records -> %b"

В результате получаем ответ true. Теперь просто внесем в определение записи маленькое изменение

type XyzRecord = {

    X:int

    Z:int

    Y:int

    }

Все, что мы изменили – это поменяли местами Y и Z, в результате, как несложно заметить, изменился и ответ. Отсюда несложно сделать вывод, что для записи в интересующем нас вопросе имеет значение порядок, в котором были определены поля. Также несложно убедиться, что сравнение записей происходит таким же образом, как и сравнение коллекций или кортежей, а порядок, в котором выполняются проверки полей, определяется порядком, в котором они объявлялись.

Аналогичным же образом несложно проверить, что для размеченных объединений тоже имеет значение порядок, в котором объявлены кейсы. То есть, для типа

type UnionExample =

    | Case1 of int*int

    | Case2 of int*int

    Case1 (2, 2) < Case2 (1, 1) |> printfn "Case1 < Case2 -> %b"

Case1 всегда будет меньше чем Case2, независимо от значений полей. А вот если сравниваются объекты, принадлежащие одному кейсу, то там уже применяется то же правило, что для сравнения кортежей.

С классами и функциями, как мне кажется, все и так понятно, они не поддерживают структурного сравнения (хотя для классов, как и прежде, поведение по умолчанию можно изменить), а вот о структурах следует поговорить отдельно. Для выяснения поведения объявляемых типов (в отличие от кортежей, списков и т. д.) у нас есть возможность просмотреть их код в декомпиляторе (я использую ILSpy, но это не принципиально). Не буду здесь приводить полностью код, который получается при создании записи или другого типа, с поддержкой структурного сравнения и структурного равенства, скажу лишь, что в этих типах реализуется несколько интерфейсов, для примера в XyzRecord объявлен так

[Serializable]
[CompilationMapping(SourceConstructFlags.RecordType)]
public sealed class XyzRecord : IEquatable, IStructuralEquatable, IComparable, IComparable, IStructuralComparable

Далее идет реализация интерфейсов, изучив код которой можно понять нюансы происходящего. В принципе то же самое можно сделать и со структурой, но… Во-первых, менять положение членов в определении структуры бесполезно – это никак не повлияет на порядок сравнения полей. Во-вторых, попытка выяснить, каким образом компилятор определяет порядок мне лично ничего не дала, а стало быть я не понял, как можно на него повлиять. И в-третьих, следует помнить о том, что все эти интерфейсы реализует компилятор F#, а это значит, что если структура создана на другом языке, то поддерживать структурное сравнение она не будет (разве что, если речь идет о каком-нибудь языке, компилятор которого в данном вопросе ведет себя так же, как и компилятор F#, но это точно не C# и, скорей всего, не VB.Net, хотя этого я и не проверил). В результате того, что структуры «из других языков» не реализуют нужных интерфейсов, получается, что проверить их на равенство можно, поскольку это требует лишь проверки одноименных полей, а вот для сравнения на «больше-меньше», где требуется определенный порядок сравнения полей, без реализации интерфейсов в самих структурах, по всей видимости, нельзя гарантировать, что во всех таких случаях порядок сохранится одинаковым. Видимо как-то так.

Что нам все это дает

Первое, что приходит в голову – это сортировка. Любые объекты, поддерживающие структурное сравнение можно сортировать без использования собственного компоратора. Конечно, может возникнуть вопрос: «А что мне дает такая сортировка, если непонятно, что этот порядок означает для более-менее сложных объектов?». Но зачастую требуется, чтобы объекты выстроились не в каком-то конкретном порядке, а чтобы порядок, в котором они выстраиваются был единообразным для всех объектов такого типа. Простой пример: у нас есть две коллекции сложных объектов, и нам нужно проверить, состоят ли эти коллекции из одинаковых объектов или они различаются. Объекты могут быть расположены как угодно, а также могут повторяться. Имея возможность сравнивать объекты как на равенство, так и на «больше-меньше» мы можем в обеих коллекциях удалить дубликаты, отсортировать их и, если они изначально состояли из одинаковых объектов, то после этих нехитрых операций получить ответ мы можем простым сравнением результатов на равенство.

let list1 = [(1,2,[3;4;5]); (6,7, [8;9;10]); (6,7, [8;9;10]); (1,2,[3;4;5]); (6,7, [8;9;10]); (6,7, [8;9;10])]

let list2 = [(1,2,[3;4;5]); (1,2,[3;4;5]); (6,7, [8;9;10]); (6,7, [8;9;10]);  (1,2,[3;4;5]); (1,2,[3;4;5]);(6,7, [8;9;10]); (6,7, [8;9;10])]

(list1 |> List.distinct |> List.sort) = (list2 |> List.distinct |> List.sort) |> printfn "list1 and list2 contain same items -> %b"

То есть, в данном случае нам было безразлично, что именно означает тот порядок, в котором были выстроены элементы в результате сортировки, поскольку главным было то, что в случае, если элементы из которых состоят коллекции, структурно совпадают, то в результате сортировки их порядок также совпадет, поскольку к ним применяется одинаковая логика сравнения.

Другой простой пример. Допустим у нас есть набор точек, которые мы будем представлять просто кортежами, скажем float*float. И нам нужно получить все отрезки, соединяющие эти точки. Отрезки будут иметь тип (float*float)*( float*float). Первое, что приходит на ум, для получения всех сочетаний, это использование функции allPairs, возвращающей декартово произведение множеств, (или вложенного цикла, это уж кому как удобнее). Но проблема здесь вот в чем. Допустим у нас есть набор точек [a;b;c]. Если мы получим декартов квадрат этого множества, то у нас будут следующие сочетания

aa ab ac ba bb bc ca cb cc

Несложно заметить, что среди вариантов есть aa bb и cc, которые отрезками не являются, поскольку на их концах одна и та же точка и нас это не интересует. Кроме того, очевидно, что отрезки ab и ba,  являются одним и тем же отрезком, просто у них начальная и конечная точка поменялись местами. При наличии возможности сравнения объектов, фильтрация таких вариантов не представляет никакого труда. Достаточно отфильтровать результат, оставив в нем только те пары, в которых первый элемент меньше(или больше, если угодно) второго. Таким образом пары, в которых точки совпадают – сразу отбрасываются, а из остальных будет оставлен только один вариант, поскольку если точки в паре ab не равны, значит либо a < b, либо наоборот. В первом случае будет оставлена пара ab, во втором – ba. И что характерно, любой из вариантов нас устраивает.

Аналогичным образом можно найти все треугольники, образованные набором точек, ну если найти декартов куб и, скажем, отобрать только те результаты, где первая точка меньше второй, а вторая меньше третьей.

let points = [(1.0, 2.0); (3.0, 4.0); (5.0, 6.0)]

let allTrangles =

    points |> List.allPairs points |> List.allPairs points

    |> List.map (fun (a,(b,c)) -> a, b, c) // Выравниваем кортежи

    |> List.filter (fun (a, b, c) -> a < b && b < c)

В данном случае без фильтрации мы получим кучу вариантов, а с фильтром только один треугольник, что вполне очевидно. Можно добавить еще одну точку и получить четыре варианта, а не длиннющий список. Причем все это достигнуто путем предельно простых манипуляций.

Другим важным примером может послужить бинарное дерево поиска, которое может быть построено только из объектов, которые можно сравнивать.

Естественно, это все простые примеры, но и они, на мой взгляд, достаточно убедительно показывают, насколько важны описанные здесь возможности.

CompareAndEquality.zip

Встраиваемые функции и статически разрешаемые параметры типов в F#

Читая документацию по данным вопросам, я ловил себя на мысли, что какие-то важные детали от меня ускользают, причем вовсе даже не потому, что что-то непонятно описано, а потому, что в документации отсутствуют какие-то важные детали. Поэтому решил разобраться в этом более детально.

Куда и как встраиваются функции

В документации читаем: «Встроенные функции — это функции, интегрированные непосредственно в вызывающий код.». Не знаю, может быть это и вполне исчерпывающее определение, но мне непонятно. Поэтому, как говорится, «будем посмотреть» куда они там встраиваются. Смотреть будем при помощи декомпилятора ILSpy.

Создаем проект консольного приложение на F# и вставляем в его главный модуль следующий код

open System

let inline sumandmult x y z = x + y * z

[<EntryPoint>]

let main argv =

    sumandmult 1 2 3 |> printfn "%O"

    sumandmult 1.0 2.0 3.0 |> printfn "%O"

    sumandmult 1I 2I 3I |> printfn "%O"

    0 // return an integer exit code

Далее собираем (или запускаем) проект, после чего декомпилируем полученную программу и смотрим что получилось. ILSpy декомпилирует в C#. Собственно, код самой функции нам не очень интересен, поскольку функции, как следует из определения встраиваются в вызывающий код, поэтому нам больше интересно посмотреть функцию main, то есть ровно то самое место, где функция вызывалась трижды с аргументами разных типов. И видим мы следующее:

        [<EntryPoint>]

        public static int main(string[] argv)

        {

            int num = 1;

            int num2 = 2;

            int num3 = 3;

            int num4 = num + num2 * num3;

            FSharpFunc<int, Unit> fSharpFunc = ExtraTopLevelOperators.PrintFormatLine(new PrintfFormat<FSharpFunc<int, Unit>, TextWriter, Unit, Unit, int>("%O"));

            int func = num4;

            fSharpFunc.Invoke(func);

            double num5 = 1.0;

            double num6 = 2.0;

            double num7 = 3.0;

            double num8 = num5 + num6 * num7;

            FSharpFunc<double, Unit> fSharpFunc2 = ExtraTopLevelOperators.PrintFormatLine(new PrintfFormat<FSharpFunc<double, Unit>, TextWriter, Unit, Unit, double>("%O"));

            double func2 = num8;

            fSharpFunc2.Invoke(func2);

            BigInteger left = NumericLiterals.NumericLiteralI.FromOne<BigInteger>();

            BigInteger left2 = NumericLiterals.NumericLiteralI.FromInt32<BigInteger>(2);

            BigInteger right = NumericLiterals.NumericLiteralI.FromInt32<BigInteger>(3);

            BigInteger bigInteger = left + left2 * right;

            FSharpFunc<BigInteger, Unit> fSharpFunc3 = ExtraTopLevelOperators.PrintFormatLine(new PrintfFormat<FSharpFunc<BigInteger, Unit>, TextWriter, Unit, Unit, BigInteger>("%O"));

            BigInteger func3 = bigInteger;

            fSharpFunc3.Invoke(func3);

            ExtraTopLevelOperators.PrintFormatLine(new PrintfFormat<Unit, TextWriter, Unit, Unit, Unit>("Hello World from F#!"));

            return 0;

        }

Из этого кода сразу становится ясно, что все вызовы функции были фактически заменены ее кодом, в котором подставлены куда надо как аргументы, так и их реальные типы. Также из этого несложно понять, почему такие функции поддерживают только статически разрешаемые джинерики: раз нет вызовов функции, стало быть и разрешить ее параметры типов во время исполнения невозможно.

Также в документации говорится: «Однако чрезмерное использование встроенных функций может привести к тому, что ваш код будет менее устойчив к изменениям в оптимизации компилятора и реализации библиотечных функций.». Честно говоря, о каких изменениях в оптимизации компилятора идет речь, сказать сложно, однако с реализацией библиотечных функций все более-менее ясно. Рассмотрим ситуацию, когда некая библиотека программы содержит такую функцию и предоставляет ее другим библиотекам. Поскольку вызовы такой функции по сути дела заменяются ее кодом, то получается, что код, единожды определенный в одной функции, оказывается разбросанным по разным библиотекам программы. Теперь если вдруг, в этом коде обнаружились проблемы и его изменили, то программу, вроде как, надо обновить. И теперь получается, что замена одной проблемной библиотеки не даст эффекта, поскольку код из нее был ранее импортирован другими библиотеками и они уже используют свои версии этого кода, не обращаясь к первоисточнику. Что делать? Заменять все библиотеки, ссылающиеся на ту, что исправлена? Но это тоже не гарантирует, что будет заменено все, поскольку встроенная функция может вызываться из другой такой же функции другой библиотеки, а та, в свою очередь, вызываться из третьей библиотеки, не имеющей непосредственной ссылки на первую, но фактически опосредованно импортирующей ее код. А тогда что делать? Переустанавливать всю программу?

 

Статически разрешаемые параметры типов

Снова обратимся к документации и прочитаем: «Статически разрешаемые параметры типа в первую очередь полезны в сочетании с ограничениями элементов, которые являются ограничениями, позволяющими указать, что аргумент типа должен иметь определенный элемент или элементы для использования. Невозможно создать этот тип ограничения с помощью обычного параметра универсального типа.».

Под элементами тут подразумеваются члены (трудности перевода), то есть, говоря по-простому, данный тип джинериков позволяет задать для типа ограничения, требующие наличия у него некоего свойства с заданными именем и типом, метода с заданной сигнатурой или поддержку определенного оператора.

Для понимания того, насколько важно иметь возможность таких ограничений, приведу очень простой пример. Допустим нам нужна простая функция, скажем Add, принимающая два аргумента и возвращающая их сумму. При этом мы хотим, чтобы функция обрабатывала аргументы любых типов, главное, чтобы они поддерживали операцию сложения. Если мы будем реализовывать это на C# или VB.Net, то единственным вменяемым способом это сделать будет отказ от статической типизации.

        static dynamic Add(dynamic x, dynamic y)

        {

            return x + y;

        }

То есть, если в процессе написания кода мы передадим этому методу объекты, к которым нельзя будет применить оператор +, то узнаем мы об этом только во время исполнения, также получим потерю производительности на динамической типизации, и на выходе будет объект неизвестного типа, что также повлечет за собой необходимость выполнения дополнительных телодвижений при использовании результата. Мало того, если вспомнить, что в C# «динамики» появились только в 4-ой версии, то для более ранних версий и этой возможности нет, там только рефлексия спасет, что имеет те же недостатки, только усилия по динамической типизации придется предпринять самостоятельно (в бейсике этой проблемы не было никогда).

Фактически для этих языков данная задача решения не имеет. Это только очень простой пример, на практике же очень часто требуется написать универсальный код, который мог бы обрабатывать объекты разных типов, но не связанных близкородственными связями.

 Проблема заключается в том, что полиморфизм подтипов накладывает на типы избыточные требования. Ведь так, если разобраться, то для чего нужно ограничивать тип параметра функции? В коде функции мы выполняем с аргументами некоторые манипуляции, что порой подразумевает обращение к различным его членам и для того, чтобы это не вызывало ошибок во время исполнения нужно, чтобы все эти члены у объекта присутствовали. Обеспечивает ли полиморфизм подтипов выполнение этого требования? Да, если мы обращаемся к членам некоторого класса или интерфейса, то принадлежность к нему объекта автоматически обеспечивает поддержку им всего, что присуще этому типу. Но, во-первых, интерфейс может содержать десятки членов, а в функции будут использоваться только один-два. Тем не менее, для того, чтобы объект подходил под ограничения реализовать придется все, хотя бы в виде заглушек, правда для того, чтобы все ненужное реализовать в виде заглушек, надо как-то узнать, что именно в коде не используется. Другая проблема в том, что если требуется реализация некоторого интерфейса, то не подойдет ни реализация всех его членов без привязки к интерфейсу, ни, например, реализация другого интерфейса с абсолютно идентичным кодом. А ведь на самом деле не имеет значения, откуда объект получил то или иное свойство или метод – код вполне в состоянии обработать объект, у которого есть в наличии все необходимое.

Таким образом, необходимость в наличии подобных ограничений, как мне кажется, вполне очевидна.

 

Привязка к членам в теле функции

Здесь, как выясняется, не все так гладко как хотелось бы. Следующий код не скомпилируется

let inline printName< ^a when ^a: (member Name: string)> (x: ^a) =

    x.Name |> printfn "%s"

И хотя, казалось бы, мы заявили, что тип параметра x должен содержать свойство Name, тем не менее компилятор пишет, что невозможно сделать такое с неизвестным типом. В документации по этому поводу ничего внятного я не нашел, так что пришлось разбираться.

На странице документации Статически разрешаемые параметры типов есть пример кода, в котором мы находим следующее

    // default implementation of replace

    static member inline replace< ^a, ^b, ^c, ^d, ^e when ^a :> CFunctor and (^a or ^d):

(static member fmap: (^b -> ^c) * ^d -> ^e) > (a, f) =

        ((^a or ^d) : (static member fmap : (^b -> ^c) * ^d -> ^e) (konst a, f))

    // call overridden replace if present

    static member inline replace< ^a, ^b, ^c when ^b: (static member replace: ^a * ^b -> ^c)>(a: ^a, f: ^b) =

        (^b : (static member replace: ^a * ^b -> ^c) (a, f))

let inline replace_instance< ^a, ^b, ^c, ^d when (^a or ^c): (static member replace: ^b * ^c -> ^d)> (a: ^b, f: ^c) =

    ((^a or ^c): (static member replace: ^b * ^c -> ^d) (a, f))

Здесь в телах функций и методов мы видим странные конструкции, описаний которых в документации я не нашел, но понять, что они означают – совсем несложно.  Выражение в скобках состоит из двух частей: в первой синтаксис совпадает с синтаксисом ограничений джинериков на наличие у объекта члена (в данном случае статического метода), во второй – кортеж объектов, как несложно догадаться, это аргументы, передаваемые методу.  В частности

(^b : (static member replace: ^a * ^b -> ^c) (a, f))

Это означает, что у типа ^b находим статический метод replace c заданной сигнатурой и передаем ему аргументы a и f. Данное выражение будет возвращать ровно то, что возвратит этот метод. Также тут есть варианты, когда нужный метод ищется у одного из двух типов, но все это, как уже было сказано, совпадает с синтаксисом ограничений и не нуждается в дополнительных разъяснениях. Здесь же мы разберемся в тех вопросах, которые из данных примеров не вполне ясны.

Для начала было бы неплохо выяснить, как обращаться к методам экземпляра, поскольку все три примера из документации обращаются к статическим методам. В сети довольно сложно найти по этому поводу внятную информацию, но мне удалось найти пример, из которого я выяснил, что для методов экземпляра в таком выражении ссылку на экземпляр надо передавать во втором кортеже на первой позиции и только потом аргументы. То есть, если мы хотим у строки mystring вызвать метод Substring с одним параметром, то выглядеть это должно следующим образом:

let inline endOfStr mystring index = (^a: (member Substring: int -> ^a) (mystring, index))

С получением значения свойства тоже все довольно просто. Например, нам нужно вывести на консоль значение свойства Length: int у любого объекта, у которого есть такое свойство.

let inline printLength obj = (^a: (member Length: int) (obj)) |> printfn "%i"

Далее можно выводить, скажем, длину массивов вот так. Но проблема в том, что с присвоением значения свойству все не так просто. Если мы попробуем сделать как-то так

(^a: (member MyProp: int) (obj)) <- 5

То ничего не получится, поскольку данная конструкция фактически является вызовом метода, а присвоение значения вызванному методу не имеет смысла.

Решение этой проблемы состоит в прямом обращении к сеттеру свойства. Как известно, акцессоры свойства создают обычные методы с именами типа get_ИмяСвойства и set_ИмяСвойства. Таким образом, если у нас есть класс A со свойством Prop, вот такой

type A() =

    member val Prop = 0 with get, set

То мы можем написать вот такую функцию, с помощью которой будем присваивать значение свойству Prop

let inline setProp obj newVal = ( ^a: (member set_Prop: ^b -> unit) (obj, newVal))

И далее так

let a = A()

setProp a 24

a.Prop |> printfn "%i"

Этот код выведет 24, что означает, что значение свойству было присвоено. Кроме того, получить значение свойства мы можем двумя способами

( ^a: (member Prop: ^b) (obj)

( ^a: (member get_Prop: unit -> ^b) (obj))

То есть можно обратиться как к свойству, так и к его геттеру.

Далее возникает вопрос, как работать с полями. Ну с получением значения вроде все ясно, там так же, как и со свойствами, но вот как насчет присвоения нового значения, ведь у полей нет акцессоров и по идее, обращение к ним не должно возыметь эффекта. Но на самом деле тут все предусмотрено и с полями можно работать точно так же, как и со свойствами, обращаясь к их как бы существующим акцессорам (ну по крайней мере с сеттером все работает, с геттером не проверял).

С событиями дело обстоит также, как и со свойствами. Каждое событие порождает пару методов, с помощью которых можно подписаться на событие и отписаться от него, методы имеют имена add_ИмяСобытия и remove_ИмяСобытия. Принимают они EventHandler того типа, которому принадлежит само событие. Для примера можно создать проект, добавить ссылки на System.Windows.Forms.dll и System.Drawing.dll и в главном модуле разместить следующий код

open System

open System.Windows.Forms

let inline addClick ctrl =

    let eh = EventHandler(fun o e -> MessageBox.Show("Object clicked") |> ignore)

    (^a:(member add_Click: EventHandler -> unit) (ctrl, eh))

let showForm ()=

    use f = new Form()

    use btn = new Button()

    btn.Text <- "Click me"

    f.Controls.Add(btn)

    addClick btn

    f.ShowDialog() |> ignore

[<EntryPoint>]

let main argv =

    printfn "%A" argv

    showForm ()

    0 // return an integer exit code

Здесь у нас функция addClick добавляет к объекту ctrl неизвестного типа обработчик события Click типа System.EventHandler который в окне сообщений выводит текст “Objekt clicked”. А функция ShowForm создает форму, добавляет на нее кнопку, устанвливает текст кнопки и передает ее функции addClick, после чего отображает форму. При запуске приложения можно убедиться, что форма появляется и при клике по кнопке появляется окошко сообщений с указанным текстом.

Думаю, об отписке от события подробно писать нет смысла, но есть еще пара вопросов, которые следовало бы рассмотреть.

Как ни странно, данная конструкция немного расширяет возможности ограничений типа. В частности, в декларации параметров типа нельзя потребовать от типа наличия у него параметризированного конструктора, но с помощью данной привязки это ограничение можно обойти, хотя и не без проблем.

Во всех предыдущих примерах мы не указывали параметры типа в декларациях функций, вместо этого параметры типов и их ограничения выводила система выведения типов, опираясь на привязки, использованные в теле функции. Выясняется, что вызвать параметрический конструктор с помощью такой привязки тоже возможно, что автоматически создаст такое ограничение для параметра типа, что невозможно, если явно прописывать такое ограничение в декларации.

Создадим класс B со следующим кодом.

type B<'a>(i) =

    member this.I:'a = i

    override this.ToString() = sprintf "B: {I: %A}" this.I

Класс имеет конструктор с одним параметром, ридонли свойство I, возвращающее то, что получил конструктор (тип параметра конструктора и свойства определен параметром типа 'a), также в нем переопределен метод ToString для лучшего отображения на консоли.

Можно теперь написать что-то типа такого

let inline getXList x il = x::[for i in il -> (^a:(new: ^b -> ^a) (i))]

Здесь мы получаем объект x неизвестного типа и коллекцию элементов другого типа. На базе всего этого создаем коллекцию объектов того же типа, что и x, причем создаем их, вызвав параметрический конструктор этого типа и передавая ему элементы коллекции il как аргументы. И в начало списка пришпандериваем сам объект x. Это прекрасно работает в частности с классом B и, скажем, списком целых чисел, дробных чисел или строк

    [3;5;8;12] |> getXList (B(4)) |> printfn "%A"

    [3.0;5.0;8.0;12.0] |> getXList (B(4.0)) |> printfn "%A"

    "est" |> getXList (B('T')) |> printfn "%A"

Результат будет таким

[B: {I: 4}; B: {I: 3}; B: {I: 5}; B: {I: 8}; B: {I: 12}]

[B: {I: 4.0}; B: {I: 3.0}; B: {I: 5.0}; B: {I: 8.0}; B: {I: 12.0}]

[B: {I: 'T'}; B: {I: 'e'}; B: {I: 's'}; B: {I: 't'}]

Но есть небольшая проблема. В данном примере мы явно передаем экземпляр целевого типа в функцию, а поскольку код функции таков, что по этому экземпляру можно легко понять, что требуется вызывать конструктор этого же типа, то проблемы нет. Другой вопрос, если мы хотим, чтобы функция создавала экземпляр и при этом не требовала другой экземпляр. Например, такая

let inline createB i = (^a:(new: ^b -> ^a) (i))

Как в данном случае сообщить функции при вызове, что нужно создавать именно экземпляр класса B? В обычных условиях можно при вызове явно задать параметры типа. Но под обычными условиями я понимаю те, при которых параметры типа объявлены явно. Но в данном случае мы явно ничего не объявляли, а если бы мы объявили явно параметры типа, то и ограничения для них пришлось бы писать явно, поскольку в этом случае система выведения типа не работала бы. Но указать явно такое ограничение мы не можем, поскольку это не предусмотрено.

Фактически, если мы сделаем вот так

createB<_, B<_>> 5 |> printfn "%A"

То компилятор будет ругаться, и сообщит нам о том, что раз параметры не заданы явно в декларации, то и при вызове их явно задавать нельзя. Тем не менее этот код и скомпилируется, и выполнится правильно.  Естественно, в ситуации, где выводится много параметров с разными ограничениями, вызов таких функций может оказаться делом совсем непростым, поскольку надо точно расположить аргументы типа, опираясь на то, как их расположила система выведения типов. Тем не менее, несмотря на все сложности, данный подход работает и если уж «кровь из носу» надо, то можно его использовать, хотя бы ограниченно.

Ну и, конечно же, индексаторы. К сожалению, получить к ним доступ мне не удалось, поскольку при попытке достучаться до get_Item, компилятор мне сообщил, что это не поддерживается. Способа обхода этого ограничения я не нашел.

 Во вложении проект с примерами из статьи.

 inlineAndGeneric.zip