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