12

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...

3
  • 3
    What type are you trying to lift it to? I see <*> in the code, but I don't see any mention of Applicative in the type signatures... Either way, I suspect the Lift a instance is going to be a problem, since it overlaps with every other possible instance (including Lift (a -> r)). Jan 17, 2015 at 19:10
  • Nevermind my code, I have tried a ton of things (most probably nonsense), just posted some random snapshot for the sake of it. I'm really confused with this concept, because, for example, lift (pure (+)) (Just 1) (Just 2) - here, (pure (+)) has a different type than Just 1, but the structure provided is hardcoded for a single type Integer... I also need a way to encode an instance for "any type that is not a function", as sort of a termination condition for the type unrolling.
    – MaiaVictor
    Jan 17, 2015 at 19:12
  • Wrote a blog post on the topic. Dec 17, 2019 at 0:19

2 Answers 2

21

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 
4
  • Oh my, that is purely awesome. No wonder I was so lost, I don't have half of the knowledge required to implement that. Is there a book with in-depth explanations of those complexities of the type system, or you learned it by experience? Thank you! Edit: I guess you need "TypeFamilies" and "FlexibleInstances" too...
    – MaiaVictor
    Jan 17, 2015 at 20:35
  • 1
    I always forget those extensions exist because I have them always turned on. I'll include that. The details of the GHC type system extensions are found mainly in the user guide. It is not very in-depth, however, and sometimes cryptic, but useful for understanding what each extensions does, not so much how to use it. Most of the really gritty type-hackery and tricks I know I've learned experience, and Oleg. Jan 17, 2015 at 21:26
  • 1
    Why the TypeFamilies extension? I don't see where you are using them... it's probably possible to use type families instead of functional dependency, but I don't see why both would be required... A, wait. you need that for the type constraints?
    – Bakuriu
    Jan 18, 2015 at 8:42
  • @Bakuriu Yes, you need either GADTs or TypeFamilies to use the type equality constraint ~. Jan 18, 2015 at 17:26
7

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).

1
  • That is a great answer, perhaps even more complete than the first one. I wasn't expecting two answers to something I consider quite complex. Thank you!
    – MaiaVictor
    Jan 18, 2015 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.