Как объявить класс типов с двумя параметрами так, чтобы компилятор понимал тип первого по типу второго?

Question

[Василий Дёмин]

Есть класс типов, объявленный следующим образом:

newtype Fix f = Fix { unFix :: f (Fix f) }

class Functor f => Fixable t f where
    toFix :: t -> Fix f
    fromFix :: Fix f -> t

Следующие типы данных являются его экземплярами:

-- Сам тип Fix
instance Functor f => Fixable (Fix f) f where
    toFix = id
    fromFix = id

-- И список
data ListF a b = Nil | Cons a b deriving (Eq, Functor)

instance Fixable [a] (ListF a) where
    toFix = apo go
      where go (x:xs) = Cons x (Right xs)
            go _ = Nil
    fromFix = cata go
      where go (Cons x xs) = x:xs
            go _ = []

В данном куске кода возникает ошибка:

main :: IO ()
main = putStrLn $ someFunc [\a b -> a ++ b, \a b -> a ++ b ++ a] "str1" "str2"
  where someFunc cs = para go cs

Из контекста понятно, что cs - список функций типа:
String -> String -> String

Но компилятор выводит слишком общий тип, а именно:

someFunc :: Fixable t (ListF (String -> String -> String)) -> (String -> String -> String)

В связи с чем возникает ошибка типизации, и компилятор требует использование расширения FlexibleContexts. Если же указать тип функции явно:

someFunc :: [String -> String -> String] -> (String -> String -> String)

код компилируется без ошибок. Как сделать так, чтобы компилятор сам выводил нужный тип?

Answer 1

[wiz]

Есть два способа - классический через FunctionalDependencies и неоклассический - через TypeFamilies.

Функциональные зависимости сделаны специально для классов с несколькими параметрами:

{-# LANGUAGE FunctionalDependencies #-}
class Collects e ce | ce -> e where
  empty  :: ce
  insert :: e -> ce -> ce
  member :: e -> ce -> Bool
  toList :: ce -> [e]

usage :: Collects e ce => ce -> Maybe e

Семейства типов более общие и могут работать отдельно от классов. Но внутри классов можно определять так называемые "ассоциированные типы". Тогда у класса не будет этого параметра, но экземпляр должен будет предоставить функцию из себя в ассоциированный тип:

{-# LANGUAGE TypeFamilies #-}
class Collects ce where
  type Elem ce
  empty  :: ce
  insert :: Elem ce -> ce -> ce
  member :: Elem ce -> ce -> Bool
  toList :: ce -> [Elem ce]

usage :: Collects ce => ce -> Maybe (Elem ce)

Больше подробностей есть на wiki.

Comments

[Василий Дёмин]

Способ с семействами типов сработал, но, к сожалению, теперь вместо типа функции приходится включать в файле с ней расширение для семейств типов (можно ли как-нибудь это исправить?). Способ с функциональными зависимостями вызывает ошибку из-за конфликта инстансов для Fix f и [a].

Functional Dependencies

Functional dependencies conflict between instance declarations:
instance [safe] Functor f => Fixable (Fix f) f
-- Defined at src/Data/Fix.hs:39:10
instance Fixable [a] (ListF a)
-- Defined at src/Data/Fix/Base.hs:10:10

[wiz]

Василий Дёмин, в расширениях нет ничего плохого. Они почти все довольно безопасные.

А что за ошибка?

[Василий Дёмин]

wiz, Я её уже скидывал.

spoiler

Functional dependencies conflict between instance declarations:
instance [safe] Functor f => Fixable (Fix f) f
-- Defined at src/Data/Fix.hs:39:10
instance Fixable [a] (ListF a)
-- Defined at src/Data/Fix/Base.hs:10:10

В расширениях нет ничего плохого, согласен. Просто мне не очень нравится мысль, что библиотека будет заставлять их использовать.

[wiz]

Василий Дёмин, посмотрел ещё раз внимательно. Действительно, если есть инстанс для любого f, то он будет по факту единственным, а все типы-функторы будут обязаны фикситься именно таким образом.

А вообще это всё подозрительно напоминает содержимое пакета recursion-schemes.

[Василий Дёмин]

wiz, Так и есть. Я хотел лучше разобраться со схемами рекурсии и не хотел тянуть в проект recursion-schemes, так как у него слишком много не нужной мне функциональности и зависимостей.

[wiz]

Василий Дёмин, есть ещё его обрезанный форк - micro-recursion-schemes.

Но обычно большая часть этих зависимостей уже и так есть транзитивно в любом нетривиальном проекте. Если ты не публикуешь библиотеку, то можно про это не беспокоиться.

[Василий Дёмин]

wiz, Мой проект достатосно тривиален. Спасибо за форк, я про него не знал, буду использовать именно его.