Поливарианские функции в Haskell

Question

После прочтения this article on writing polyvariadic functions in Haskell, я попытался написать свои собственные.

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

{-# 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 

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

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

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

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

Answer 3

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

{-# 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" 

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