Как Haskell выполняет сопоставление с образцом, не определяя Eq для наших типов данных?

Question

Я определил двоичное дерево:

data Tree = Null | Node Tree Int Tree

и реализовали функцию, которая выдаст сумму значений всех его узлов:

sumOfValues :: Tree -> Int
sumOfValues Null = 0
sumOfValues (Node Null v Null) = v
sumOfValues (Node Null v t2) = v + (sumOfValues t2)
sumOfValues (Node t1 v Null) = v + (sumOfValues t1)
sumOfValues (Node t1 v t2) = v + (sumOfValues t1) + (sumOfValues t2)

Работает как положено. У меня была идея также попытаться реализовать это с помощью охранников:

sumOfValues2 :: Tree -> Int
sumOfValues2 Null = 0
sumOfValues2 (Node t1 v t2)
    | t1 == Null && t2 == Null  = v
    | t1 == Null            = v + (sumOfValues2 t2)
    |               t2 == Null  = v + (sumOfValues2 t1)
    |   otherwise       = v + (sumOfValues2 t1) + (sumOfValues2 t2)

но этот не работает, потому что я не реализовал Eq, я считаю:

No instance for (Eq Tree)
  arising from a use of `==' at zzz3.hs:13:3-12
Possible fix: add an instance declaration for (Eq Tree)
In the first argument of `(&&)', namely `t1 == Null'
In the expression: t1 == Null && t2 == Null
In a stmt of a pattern guard for
             the definition of `sumOfValues2':
        t1 == Null && t2 == Null

Тогда возникает вопрос: как Haskell может сопоставлять шаблоны, не зная, когда совпадает переданный аргумент, не прибегая к Eq?

Редактировать

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

f :: Int -> Int -> Int
f 1 _ = 666
f 2 _ = 777
f _ 1 = 888
f _ _ = 999

При запуске f 2 9 не нужно ли будет использовать Eq, чтобы узнать, какая из подфункций является правильной? Все они равны (в отличие от моего первоначального примера Tree, когда у нас было Tree / Node / Null). Или это фактическое определение Int что-то вроде

data Int = -2^32 | -109212 ... | 0 | ... +2^32 

Answer 1

Для сопоставления с образцом Haskell использует структуру значения и используемые конструкторы.Например, если вы оцениваете

sumOfValues (Node Null 5 (Node Null 10 Null))

, он проверяет шаблоны сверху вниз:

• первый, Null, не совпадает, потому что онимеет другую структуру

• второй, (Node Null v Null), не совпадает, потому что последний компонент, Null, имеет структуру, отличную от (Node Null 10 Null) (сопоставление с образцом происходит рекурсивно)

• третий совпадает с v, привязанным к 5, и t2, привязанным к (Node Null 10 Null).

Eq иоператор ==, который он определяет, является несвязанным механизмом;создание Tree экземпляра Eq не изменит работу сопоставления с образцом.

Я думаю, что ваше мышление здесь немного отсталое: сопоставление с образцом - это самый простой способ использования значения в Haskell;за исключением некоторых базовых типов, таких как Int, Eq реализован с использованием сопоставления с образцом, а не наоборот.

сопоставление с образцом и числами

Оказывается, числовые литералы являются особым случаем,Согласно отчету Haskell ( ссылка ):

Сопоставление числового, символьного или строкового литерального шаблона k со значением v успешно, если v == k , где == перегружено в зависимости от типа шаблона.

Answer 2

Единственное, чего вам не хватает, так это того, что вы предполагаете, что Null - это некоторое постоянное значение, как в C или Java.Это не так - это конструктор для типа Tree.

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

Что касается ваших правок об Ints:

Да, Int в основном тип с неприлично большим количеством конструкторов по линиям -2 | -1 | 0 | 1 | 2 | 3 | 4 ….Он немного волнистый, но работает на практике.

Answer 3

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

Answer 4

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

isEmpty :: Tree -> Bool
isEmpty Null = True
isEmpty _ = False

sumOfValues2 :: Tree -> Int
sumOfValues2 Null = 0
sumOfValues2 (Node t1 v t2)
    | isEmpty t1 && isEmpty t2 = v
    | isEmpty t1 = v + (sumOfValues2 t2)
    | isEmpty t2 = v + (sumOfValues2 t1)
    | otherwise = v + (sumOfValues2 t1) + (sumOfValues2 t2)

Кстати, вам не нужны все эти случаи, только это:

sumOfValues :: Tree -> Int
sumOfValues Null = 0
sumOfValues (Node t1 v t2) = v + (sumOfValues t1) + (sumOfValues t2)

Answer 5

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

Так что, если вы перегружаете свой тип данных Fred, который имеет класс Num и имеет конструктор, также называемый Fred, вы можете определить равенство целых чисел, проверив, равен ли данный Integer 1. Теперь в этом странном сценарии, если я не пропускаючто-то, должно работать следующее:

getFred :: Fred -- get a Fred
getFred = Fred -- invoke the Fred constructor

testFred :: Fred -> Bool -- tests if Fred's equality operator considers 1 equal to Fred
testFred 1 = True -- overloaded (==) tests against 1, so should be true
testFred _ = False -- shouldn't happen, then...

isFredOne = testFred $ getFred -- returns True

Answer 6

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

Answer 7

Я оправдываю подобные вещи, говоря, что сопоставление с образцом - это ядро ​​того, что есть в Haskell, а класс типов Eq - нет.

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