Поливариадные функции в Хаскеле

Question

Прочитав эту статью о написании поливариадных функций на Хаскеле, я попытался написать несколько своих.

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

{-# OPTIONS -fglasgow-exts #-}
module Collapse where
class Collapse a r | r -> a where
  collapse :: (a -> a -> a) -> a -> r
instance Collapse a a where
  collapse _ = id
instance (Collapse a r) => Collapse a (a -> r) where
  collapse f a a' = collapse f (f a a')

Однако компилятору это не понравилось:

Collapse.hs:5:9:
    Functional dependencies conflict between instance declarations:
      instance Collapse a a -- Defined at Collapse.hs:5:9-20
      instance (Collapse a r) => Collapse a (a -> r)
        -- Defined at Collapse.hs:7:9-43

Если я вернулся и добавил тип обертки для конечного результата, это сработало:

module Collapse where
class Collapse a r | r -> a where
  collapse :: (a -> a -> a) -> a -> r
data C a = C a
instance Collapse a (C a) where
  collapse _ = C . id
instance (Collapse a r) => Collapse a (a -> r) where
  collapse f a a' = collapse f (f a a')
sum :: (Num a, Collapse a r) => a -> r
sum = collapse (+)

Как только я сделал это изменение, оно скомпилировалось нормально, и я мог использовать collapse функция в ghci,

ghci> let C s = Collapse.sum 1 2 3 in s
6

Я не уверен, почему тип обертки требуется для конечного результата. Если бы кто-нибудь мог объяснить это, я был бы очень признателен. Я вижу, что компилятор говорит мне, что это какая-то проблема с функциональными зависимостями, но я пока не понимаю правильного использования fundeps.

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

{-# OPTIONS -fglasgow-exts #-}
{-# LANGUAGE UndecidableInstances #-}
module Variadic where
class Variadic a b r | r -> a, r -> b where
  variadic :: ([a] -> b) -> r
data V a = V a
instance Variadic a b (V b) where
  variadic f = V $ f []
instance (Variadic a b r) => Variadic a b (a -> r) where
  variadic f a = variadic (f . (a:))
list :: Variadic a [a] r => r
list = variadic . id
foldl :: (Variadic b a r) => (a -> b -> a) -> a -> r
foldl f a = variadic (Prelude.foldl f a)

Без разрешения UndecidableInstances компилятор пожаловался, что объявления моего экземпляра были незаконными:

Variadic.hs:7:0:
    Illegal instance declaration for `Variadic a b (V b)'
        (the Coverage Condition fails for one of the functional dependencies;
         Use -XUndecidableInstances to permit this)
    In the instance declaration for `Variadic a b (V b)'

Variadic.hs:9:0:
    Illegal instance declaration for `Variadic a b (a -> r)'
        (the Coverage Condition fails for one of the functional dependencies;
         Use -XUndecidableInstances to permit this)
    In the instance declaration for `Variadic a b (a -> r)'

Однако после компиляции я смог успешно использовать его в ghci:

ghci> let V l = Variadic.list 1 2 3 in l
[1,2,3]
ghci> let vall p = Variadic.foldl (\b a -> b && (p a)) True
ghci> :t vall
vall :: (Variadic b Bool r) => (b -> Bool) -> r
ghci> let V b = vall (>0) 1 2 3 in b
True

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

Кроме того, это казалось странным:

ghci> let vsum = Variadic.foldl (+) 0

<interactive>:1:10:
    Ambiguous type variables `a', `r' in the constraint:
      `Variadic a a r'
        arising from a use of `Variadic.foldl' at <interactive>:1:10-29
    Probable fix: add a type signature that fixes these type variable(s)

<interactive>:1:10:
    Ambiguous type variable `a'in the constraint:
      `Num a' arising from the literal `0' at <interactive>:1:29
    Probable fix: add a type signature that fixes these type variable(s)
ghci> let vsum' = Variadic.foldl (+) 
ghci> :t vsum'
(Num a, Variadic a a r) => t -> a -> r
ghci> :t vsum' 0
(Num a, Variadic a a r) => a -> r
ghci> let V s = vsum' 0 1 2 3 in s
6

Я предполагаю, что это выпадение от разрешения UndecidableInstances, но я не знаю, и я хотел бы лучше понять, что происходит.

Answer 1

Идея функциональных зависимостей заключается в том, что в объявлении типа

class Collapse a r | r -> a where
  ...

r -> a немного говорит, что a однозначно определяется r, Итак, вы не можете иметь instance Collapse (a -> r) (a -> r) а также instance Collapse a (a -> r), Обратите внимание, что instance Collapse (a -> r) (a -> r) следует из instance Collapse a a для полной картины.

Другими словами, ваш код пытается установить instance Collapse t t (имя переменной типа, конечно, неважно) и instance Collapse a (a -> r), Если вы замените (a -> r) за t в первой декларации вы получите instance Collapse (a -> r) (a -> r), Теперь это единственный случай Collapse с параметром второго типа, равным (a -> r) что вы можете иметь, потому что объявление класса говорит, что первый параметр типа должен быть выводимым из второго. Тем не менее, в следующий раз вы пытаетесь установить instance a (a -> r), который бы добавил еще один экземпляр Collapse с параметром второго типа (a -> r), Таким образом, GHC жалуется.

Answer 2

Если вы все еще экспериментируете с этим, вот пример построения поливариадной функции из функции, получающей список, без необходимости использования типа оболочки или неразрешимых экземпляров:

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

class Variadic a b r | r -> a where
    variadic :: ([a] -> b) -> r

instance Variadic a b (a -> b) where
    variadic f x = f [x]

instance (Variadic a b (a -> r)) => Variadic a b (a -> a -> r) where
    variadic f x y = variadic (f . (x:)) y

vList :: (Variadic a [a] r) => r
vList = variadic id

vFoldl :: (Variadic b a r) => (a -> b -> a) -> a -> r
vFoldl f z = variadic (foldl f z)

vConcat :: (Variadic [a] [a] r) => r
vConcat = vFoldl (++) []

main = do
    putStrLn $ vConcat "abc" "def" "ghi" "jkl"
    putStrLn $ vList 'x' 'y' 'z'
    if vFoldl (&&) True True True True then putStrLn "Yes" else putStrLn "No"
    if vFoldl (&&) True True False True then putStrLn "Yes" else putStrLn "No"

Недостатки этого подхода в том, что средство проверки типов должно иметь возможность определять тип результата (или вы должны аннотировать его), и что он плохо работает с полиморфными числовыми константами; причины обеих проблем обсуждаются в упомянутой вами статье. Не знаю, найдете ли вы это полезным, но я раньше возился с поливариадными функциями и вспомнил этот вопрос.

Answer 3

Michał Marczyk абсолютно прав в вопросе соответствия функций и экземпляров, и тип обертки кажется простым решением. С другой стороны, если вы уже читаете сайт Олега, вы можете предпочесть пойти глубже в кроличью нору и попытаться написать экземпляр для "любого типа, который не является функцией".

Что касается UndecidableInstances, условие покрытия описывается здесь; должно быть очевидно, почему ваши экземпляры терпят неудачу. Обратите внимание, что слово "неразрешимый" здесь означает неразрешимый в примерно том же смысле, что и в "Проблема остановки неразрешима", то есть вы говорите GHC безрассудно пытаться разрешить код, который может отправить его в бесконечный цикл. основываясь только на вашем утверждении, что все в порядке. Это весело для взлома аккуратных идей, но согласие быть человеком, прошедшим первичную проверку типов для GHC, является бременем, которое я лично считаю утомительным.