Двунаправленные функциональные зависимости - PullRequest
Новая
       56

Двунаправленные функциональные зависимости

9 голосов
/ 02 июня 2019

У меня есть класс типов, который выглядит примерно так: 

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

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

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

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

Моя проблема в том, что зависимость | a -> b не совсем то, что я имею в виду.Я имею в виду не только то, что вы можете найти a из b, но и то, что вы можете найти b из a.То есть каждый тип должен быть членом Foo только с одним другим типом, поэтому мы можем дать одному типу найти другой.Или, другими словами, зависимость является двунаправленной.Такая функциональная зависимость помешала бы мне присутствовать Bool в двух отдельных случаях, потому что первый параметр мог бы быть получен из второго, а второй из первого.

Но я не знаю, каквыразить эту идею компилятору.

Как создать двунаправленную функциональную зависимость?Или, более вероятно, есть ли способ, которым я могу перефразировать свой класс типов, чтобы получить что-то, что могло бы заменить двунаправленную функциональную зависимость?

Ответы [ 3 ]

8 голосов
/ 02 июня 2019

A двунаправленная зависимость между a и b может быть представлена ​​как две функциональные зависимости a -> b и b -> a, например: 

class Foo a b | a -> b<b>, b -> a</b> where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

Здесь a зависит от b, а b зависит от a.

Однако для ваших instance с это, конечно, вызывает ошибку, поскольку теперь вы определили два разных a s для b ~ Bool. Это вызовет ошибку вроде: 

file.hs:6:10: error:
    <b>Functional dependencies conflict</b> between instance declarations:
      instance Foo () Bool -- Defined at file.hs:6:10
      instance Foo ((), ()) Bool -- Defined at file.hs:11:10
Failed, modules loaded: none.

Из-за функциональной зависимости вы можете определить только один a для b ~ Bool. Но это, вероятно, именно то, что вы ищете: механизм, предотвращающий двойное определение Foo для одного и того же a или одного и того же b.

3 голосов
/ 02 июня 2019

(Это скорее комментарий, чем ответ, поскольку он не касается точного вопроса, заданного ОП.)

В дополнение к ответу Виллема: в настоящее время у нас есть другой способ заставить GHC принять этот класс. 

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

Как GHC предлагает в своем сообщении об ошибке, мы можем включить AllowAmbiguousTypes. ОП отметил, что тогда возникнут проблемы, если мы оценим что-то вроде g False и есть два совпадающих экземпляра, например 

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

Действительно, в таком случае g False становится неоднозначным. Тогда у нас есть два варианта.

Во-первых, мы можем запретить использование обоих приведенных выше экземпляров, добавив функциональную зависимость b -> a в класс (как предложил Виллем). Это делает g False однозначным (и нам не нужно расширение в таком случае).

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

Полный код: 

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
    FlexibleInstances, AllowAmbiguousTypes, TypeApplications #-}

class Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

instance Foo () Bool where
  f x = True
  g y = y
  h x y = False

instance Foo ((), ()) Bool where
  f x = True
  g y = not y
  h x y = False

main :: IO ()
main = print (g @() False, g @((),()) False)
1 голос
/ 03 июня 2019

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

class Bar b where
  g :: b -> Bool

class (Bar b) => Foo a b | a -> b where
  f :: a -> Bool
  h :: a -> b -> Bool

Теперь мы все еще разрешаем нам создавать два разных Foo экземпляра с одинаковыми b, но мы больше неполучить неоднозначность, так как g теперь является членом Bar, между ними должен быть один экземпляр.

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

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

class Bar a b | b -> a

class (Bar a b) => Foo a b | a -> b where
  f :: a -> Bool
  g :: b -> Bool
  h :: a -> b -> Bool

Здесь Bar - это действие, заставляющее b зависеть от a, предотвращая нас от двусмысленности.Поскольку Foo требует Bar, а Bar позволяет получить a из b, любой экземпляр Foo позволяет a быть полученным из b.Это в значительной степени то, что я хотел изначально, однако это лишь немного более сложная версия ответа Виллема Ван Онсема.

...