Polyvariadic Functions in Haskell
haskell, polymorphism, polyvariadic
Solution
The idea behind functional dependencies is that in a declaration like
class Collapse a r | r -> a where
...
the `r -> a` bit says that `a` is uniquely determined by `r`. So, you can't have `instance Collapse (a -> r) (a -> r)` and `instance Collapse a (a -> r)`. Note that `instance Collapse (a -> r) (a -> r)` follows from `instance Collapse a a` for the complete picture.
In other words, your code is trying to establish `instance Collapse t t` (the type variable's name is of course unimportant) and `instance Collapse a (a -> r)`. If you substitute `(a -> r)` for `t` in the first instance declaration, you get `instance Collapse (a -> r) (a -> r)`. Now this is the only instance of `Collapse` with the second type parameter equal to `(a -> r)` that you can have, because the class declaration says that the first type parameter is to be deducible from the second. Yet next you try to establish `instance a (a -> r)`, which would add another instance of `Collapse` with the second type parameter being `(a -> r)`. Thus, GHC complains.
Problem
After reading this article on writing polyvariadic functions in Haskell, I tried to write some of my own. At first I thought I'd try to generalize it - so I could have a function that returned variadic functions by collapsing arguments as given. ``` {-# 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') ``` However, the compiler didn't like that: ``` 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 ``` If I went back and added a wrapper type for the final result, however, it worked: ``` 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 (+) ``` Once I made this change, it compiled fine, and I could use the `collapse` function in `ghci`. ``` ghci> let C s = Collapse.sum 1 2 3 in s 6 ``` I'm not sure why the wrapper type is required for the final result. If anyone could explain that, I'd highly appreciate it. I can see that the compiler's telling me that it's some issue with the functional dependencies, but I don't really grok the proper use of fundeps yet. Later, I tried to take a different tack, and try and define a variadic function generator for functions that took a list and returned a value. I had to do the same container trick, and also allow `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) ``` Without allowing `UndecidableInstances` the compiler complained that my instance declarations were illegal: ``` 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)' ``` However, once it compiled, I could successfully use it in 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 ``` I guess what I'm looking for is an explanation of why the container type for the final value is necessary, as well as why all the various functional dependencies are necessary. Also, this seemed odd: ``` 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 ``` I'm guessing that's fallout from allowing `UndecidableInstances`, but I don't know, and I'd like to better understand what's going on.