Конфликт функциональной зависимости 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, но не имело смысла, что так оно и было, и эта проблема, похоже, была решена в более новых версиях.