Is it possible to encode a generic “lift” function

Question

I'm not the biggest fan of varargs, but I always thought both the applicative (f <$> x <*> y) and idiom ([i| f x y |]) styles have too many symbols. I usually prefer going the liftA2 f x y way, but I, too, think that A2 is a little ugly. From this question, I've learned it is possible to implement vararg functions in Haskell. This way, is it possible to use the same principle in order implement a lift function, such that:

lift f a b == pure f <*> a <*> b

I've tried replacing the + by <*> on the quoted code:

class Lift r where 
    lift :: a -> r

instance Lift a where
    lift = id

instance (Lift r) => Lift (a -> r) where
    lift x y = lift (x <*> y)

But I couldn't manage to get the types right...

Answer 1

I assume you would prefer to use lift without type annotations. In this case there are basically two options:

First, if we use OverlappingInstances, polymorphic functions need annotations:

{-# LANGUAGE
  OverlappingInstances,
  MultiParamTypeClasses,
  UndecidableInstances,
  FunctionalDependencies,
  FlexibleInstances,
  TypeFamilies
  #-}

import Control.Applicative

class Applicative f => ApN f a b | a b -> f where
  apN :: f a -> b

instance (Applicative f, b ~ f a) => ApN f a b where
  apN = id

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where
  apN f fa = apN (f <*> fa)

lift :: ApN f a b => a -> b
lift a = apN (pure a)

-- Now we can't write "lift (+) (Just 0) Nothing"
-- We must annotate as follows: 
--   lift ((+) :: Int -> Int -> Int) (Just 0) Nothing
-- Monomorphic functions work fine though:
--   lift (||) (Just True) (Just True) --> results in "Just True"

Second, if we instead use IncoherentInstances, lift will work without annotations even on polymorphic functions. However, some complicated stuff still won't check out, for example (lift . lift) (+) (Just (Just 0)) Nothing.

{-# LANGUAGE 
  IncoherentInstances, MultiParamTypeClasses,
  UndecidableInstances,ScopedTypeVariables,
  AllowAmbiguousTypes, FlexibleInstances, TypeFamilies
  #-}

import Control.Applicative

class Applicative f => ApN f a b where
  apN :: f a -> b

instance (Applicative f, b ~ f a) => ApN f a b where
  apN = id

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where
  apN f fa = apN (f <*> fa)

lift :: forall f a b. ApN f a b => a -> b
lift a = (apN :: f a -> b) (pure a)

-- now "lift (+) (Just 0) (Just 10)" works out of the box

I presented two solutions instead of just the one with IncoherentInstances because IncoherentInstances is a rather crude extension that should be avoided if possible. It's probably fine here, but I thought it worthwhile to provide an alternative solution, anyway.

---

In both cases I use the same trick to help inference and reduce annotations: I try to move information from the instance heads to the instance constraints. So instead of

instance (Applicative f) => ApN f a (f a) where
  apN = id

I write

instance (Applicative f, b ~ f a) => ApN f a b where
  apN = id

Also, in the other instance I use a plain b parameter in the instance head and add b ~ (f a ~ b') to the constraints.

The reason for doing this is that GHC first checks if there is a matching instance head, and it tries to resolve the constraints only after there is a successful match. We want to place the least amount of burden on the instance head, and let the constraint solver sort things out (because it's more flexible, can delay making judgements and can use constraints from other parts of the program).

Answer 2

Notice that you can chain any number of <*>, to get a function of the form

f (a0 -> .. -> an) -> (f a0 -> .. -> f an)

If we have the type a0 -> .. -> an and f a0 -> .. -> f an, we can compute f from this. We can encode this relation, and the most general type, as follows

class Lift a f b | a b -> f where 
  lift' :: f a -> b 

As you may expect, the "recursive case" instance will simply apply <*> once, then recurse:

instance (a ~ a', f' ~ f, Lift as f rs, Applicative f) 
      => Lift (a -> as) f (f' a' -> rs) where  
  lift' f a = lift' $ f <*> a

The base case is when there is no more function. Since you can't actually assert "a is not a function type", this relies on overlapping instances:

instance (f a ~ b) => Lift a f b where 
  lift' = id 

Because of GHCs instance selection rules, the recursive case will always be selected, if possible.

Then the function you want is lift' . pure :

lift :: (Lift a f b, Applicative f) => a -> b
lift x = lift' (pure x) 

This is where the functional dependency on Lift becomes very important. Since f is mentioned only in the context, this function would be ill-typed unless we can determine what f is knowing only a and b (which do appear in the right hand side of =>).

This requires several extensions:

{-# LANGUAGE 
    OverlappingInstances
  , MultiParamTypeClasses
  , UndecidableInstances
  , FunctionalDependencies
  , ScopedTypeVariables
  , TypeFamilies
  , FlexibleInstances
  #-}

and, as usual with variadic functions in Haskell, normally the only way to select an instance is to give an explicit type signature.

lift (\x y z -> x * y + z) readLn readLn readLn :: IO Int

The way I have written it, GHC will happily accept lift which is polymorphic in the arguments to f (but not f itself).

lift (+) [1..5] [3..5] :: (Enum a, Num a) => [a]

Sometimes the context is sufficient to infer the correct type. Note that the argument type is again polymorphic.

main = lift (\x y z -> x * y + z) readLn readLn readLn >>= print 

---

As of GHC >= 7.10, OverlappingInstances has been deprecated and the compiler will issue a warning. It will likely be removed in some later version. This can be fixed by removing OverlappingInstances from the {-# LANGUAGE .. #-} pragma and changing the 2nd instance to

instance {-# OVERLAPS #-} (f a ~ b) => Lift a f b where