понедельник, 25 мая 2020 г.


Структурное равенство и структурное сравнение в 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

1 комментарий :