Haskell: a & # 8594; a -> ... & # 8594; b to [a] & # 8594; b

Question

I am trying to express the following map as a Haskell function:

Given two types a, b , we consider a family of functions F(a, b) consisting of functions of type

 f :: a -> a -> ... -> a -> b 

with n repetitions of a , where n is an integer greater than zero. I want to map each function f in F(a, b) to a function f' :: [a] -> b such that f x1 x2 ... xr = f' [x1, ..., xr] , where r less than the number of arguments f takes (i.e. I'm looking for a function listify :: F(a, b) -> ([a] -> b) ). If there are more elements than f takes arguments, additional elements should be discarded:

 f :: a -> a -> b (listify f xs) == (listify f $ take 2 xs) 

Also, if an empty string is passed, any value is acceptable.

Of course, I can implement this map for functions with a fixed number of arguments (for example: listify :: (a -> a -> b) -> ([a] -> b) , etc.), but I could not find a way to write a function that does this for all f in F(a, b) at the same time. Despite the fact that Template Haskell can probably provide me with the tools I need, I'm not interested in such a solution. I want to find a pure "magic" style.

Does anyone know if this is possible? Can someone point me in the right direction? Or is it a well-known "problem" that has been solved billions of times and I just can't find a solution?

Answer 1

We just have to choose our poison here. If we use less secure pragmas, we can get more output and vice versa; There are a number of combinations.

First : uses overlapping instances, has non-functions as the base code, but cannot handle the polymorphic types a :

 {-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-} class Listify ab where listify :: a -> b instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify br where listify = const instance (Listify fr, r ~ ([a] -> b)) => Listify (a -> f) r where listify f (a:as) = listify (fa) as -- listify (+) [0, 2] -- error -- listify (+) [0, 2 :: Int] -- OK -- listify () [] -- OK 

Second : it uses overlapping instances, has functions as a base register, can process polymorphic types:

 {-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances, FlexibleContexts #-} class Listify ab where listify :: a -> b instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify (a -> b) r where listify f (a:_) = fa instance (Listify (a -> b) r, r ~ ([a] -> b)) => Listify (a -> a -> b) r where listify f (a:as) = listify (fa) as -- listify (+) [0, 2] -- OK -- listify () [] -- error, first arg must be a function 

Third : uses incoherent instances, has values ​​in the base case, can process polymorphic types:

 {-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-} class Listify ab where listify :: a -> b instance {-# INCOHERENT #-} r ~ ([a] -> b) => Listify br where listify = const instance (Listify fr, r ~ ([a] -> b)) => Listify (a -> f) r where listify f (a:as) = listify (fa) as -- listify 0 [] -- OK -- listify (+) [2, 4] -- OK 

Fourth : uses closed-type families with UndecidableInstances as an assistant to resolve the instance, has values ​​in the base case, cannot handle polymorphic types:

 {-# LANGUAGE UndecidableInstances, ScopedTypeVariables, DataKinds, TypeFamilies, MultiParamTypeClasses, FlexibleInstances, FlexibleContexts #-} import Data.Proxy data Nat = Z | S Nat type family Arity f where Arity (a -> b) = S (Arity b) Arity b = Z class Listify (n :: Nat) ab where listify' :: Proxy n -> a -> b instance r ~ (a -> b) => Listify Z br where listify' _ = const instance (Listify nfr, a ~ (a' -> f), r ~ ([a'] -> b)) => Listify (S n) ar where listify' _ f (a:as) = listify' (Proxy :: Proxy n) (fa) as listify :: forall a b. Listify (Arity a) ab => a -> b listify = listify' (Proxy :: Proxy (Arity a)) -- listify (+) [3, 4] -- error -- listify (+) [3, 4::Int] -- OK -- listify () [] -- OK -- listify 0 [] -- error -- listify (0 :: Int) [] -- OK 

On top of my head, these are roughly options that can be seen in the wild, with the exception of INCOHERENT , because it is extremely rare in library code (for good reasons).

I personally recommend the closed family version because UndecidableInstances and family types are the least controversial language extensions, and they still provide a fair amount of usability.

Answer 2

This is actually quite simple, it does not even require overlapping instances:

 {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} class Listifiable fab where listify :: f -> [a] -> b instance Listifiable bab where listify = const instance (Listifiable f) ab => Listifiable (a->f) ab where listify f (x:xs) = listify (fx) xs 

Then you can do

 GHCi> listify ((+) :: Int->Int->Int) [1,2 :: Int] :: Int 3 

But the need for these local explicit types of signatures quite shows the problems you are facing.

(Perhaps you can fix this problem with FunctionalDependencies , but at least not in the literal sense.)