Haskell: a -> a -> ... -> b to [a] -> b [duplicate]

Question

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

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

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

with n repetitions of a, where n is an integer greater than zero. What I want is 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 is smaller than the number of arguments f takes (i.e. I'm looking for the function listify :: F(a, b) -> ([a] -> b)). If there are more elements than f takes arguments, the additional elements should be discarded:

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

Furthermore, if the empty listed is passed, any value is acceptable.

I'm of course able to implement this map for functions with a fixed number of arguments (for example: listify :: (a -> a -> b) -> ([a] -> b), etc.), but I couldn't find a way to write a function that does it for all f in F(a, b) simultaneously. Even though Template Haskell is probably able to provide me with the right tools, I'm not interested in such a solution. I want to find some pure "type magic" way to do it.

Does anyone know if that's even possible? Can someone maybe point me in the right direction? Or is this a known "problem" which has been solved billions of times and I'm just unable to find a solution?

Answer 1

We just have to pick our poison here. If we use less safe pragmas, we can get more inference, and vice versa; there's a number of combinations.

First: uses overlapping instances, has non-functions as base case, but can't handle polymorphic a types:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

class Listify a b where
  listify :: a -> b  

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify b r where
  listify = const

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where
  listify f (a:as) = listify (f a) as

-- listify (+) [0, 2] -- error
-- listify (+) [0, 2 :: Int] -- OK
-- listify () [] -- OK

Second: uses overlapping instances, has functions as base case, can handle polymorphic types:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances, FlexibleContexts #-}

class Listify a b where
  listify :: a -> b  

instance {-# OVERLAPS #-} r ~ ([a] -> b) => Listify (a -> b) r where
  listify f (a:_) = f a

instance (Listify (a -> b) r, r ~ ([a] -> b)) => Listify (a -> a -> b) r where
  listify f (a:as) = listify (f a) as

-- listify (+) [0, 2] -- OK
-- listify () [] -- error, first arg must be a function

Third: uses incoherent instances, has values in base case, can handle polymorphic types:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

class Listify a b where
  listify :: a -> b  

instance {-# INCOHERENT #-} r ~ ([a] -> b) => Listify b r where
  listify = const

instance (Listify f r, r ~ ([a] -> b)) => Listify (a -> f) r where
  listify f (a:as) = listify (f a) as

-- listify 0 [] -- OK
-- listify (+) [2, 4] -- OK

Fourth: uses closed type families with UndecidableInstances as helper for instance resolution, has values in base case, can't 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) a b where
  listify' :: Proxy n -> a -> b

instance r ~ (a -> b) => Listify Z b r where
  listify' _ = const

instance (Listify n f r, a ~ (a' -> f), r ~ ([a'] -> b)) => Listify (S n) a r where
  listify' _ f (a:as) = listify' (Proxy :: Proxy n) (f a) as

listify :: forall a b. Listify (Arity a) a b => 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

From the top of my head, roughly these are the variants one can see in the wild, except for the INCOHERENT one, because that's extremely rare in library code (for good reasons).

I personally recommend the version with the closed type families, because UndecidableInstances and type families are by far the least controversial as language extensions, and they still provide a fair amount of usability.

Answer 2

Actually it's quite simple, doesn't even require overlapping instances:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class Listifiable f a b where
  listify :: f -> [a] -> b

instance Listifiable b a b where
  listify = const

instance (Listifiable f) a b => Listifiable (a->f) a b where
  listify f (x:xs) = listify (f x) xs

Then you can do

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

But the need for those local explicit type signatures quite shows the problems you're getting yourself in.

(It might be possible to alleviate this problem with FunctionalDependencies, but at least not in a straightforward way.)