Конфликт функциональной зависимости Haskell

Почему это приводит к конфликту?

class Foo a b | b -> a where
  foo :: a -> b -> Bool

instance Eq a => Foo a a where
  foo = (==)

instance Eq a => Foo a (a -> a) where
  foo x f = f x == x

Обратите внимание, что код будет скомпилирован, если я удалю функциональную зависимость.

У меня создалось впечатление, что функциональные зависимости должны только запрещать такие вещи, как следующее, когда на самом деле он компилируется!

class Foo a b | b -> a where
  foo :: a -> b -> Bool

instance Eq a => Foo a a where
  foo = (==)

instance Eq a => Foo Bool a where
  foo _ x = x == x

Тот же параметр b, но разные параметры a. Если не b -> a запретить это, так как это означает, что a однозначно определяется b?

Ответ 1

Вы пытались использовать вторую версию? Я предполагаю, что, пока экземпляры компилируются, вы начнете получать ошибки неоднозначности и перекрытия при вызове foo.

Самый большой камнем преткновения здесь является то, что fundeps не взаимодействуют с переменными типа так, как вы могли бы ожидать от них - выбор экземпляра на самом деле не ищет решений, он просто слепо совпадает с попыткой объединения. В частности, когда вы пишете Foo a a, a является полностью произвольным и, таким образом, может объединяться с типом типа b -> b. Когда второй параметр имеет форму b -> b, он, таким образом, совпадает с обоими экземплярами, но в файлах с платой указано, что в одном случае первый параметр должен быть b -> b, а в другом должен быть b. Следовательно, конфликт.

Поскольку это, по-видимому, удивляет людей, вот что произойдет, если вы попытаетесь использовать вторую версию:

bar = foo () () приводит к:
```
Couldn't match type `Bool' with `()'
  When using functional dependencies to combine
    Foo Bool a,
```
... потому что fundep говорит через второй экземпляр, что любой тип как второй параметр однозначно определяет Bool как первый. Таким образом, первый параметр должен быть Bool.
bar = foo True () приводит к:
```
Couldn't match type `()' with `Bool'
  When using functional dependencies to combine
    Foo a a,
```
... потому что fundep говорит, в первом случае, что любой тип, поскольку второй параметр однозначно определяет один и тот же тип для первого. Таким образом, первый параметр должен быть ().
bar = foo () True приводит к ошибкам из-за обоих экземпляров, так как на этот раз они согласны с тем, что первый параметр должен быть Bool.
bar = foo True True приводит к:
```
Overlapping instances for Foo Bool Bool
  arising from a use of `foo'
```
... потому что оба экземпляра выполнены и, следовательно, перекрываются.

Довольно весело, да?

Ответ 2

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

Изменить: Первоначально я предложил, чтобы второй пример работал. Это было сделано на ghc 7.0.4, но не имело смысла, что так оно и было, и эта проблема, похоже, была решена в более новых версиях.