Haskell: Function to apply some function to nested 2-tuples

Question

Say I have a tuple like ('a',(1,("Hello",False)). Just for fun (read: learning), I'd like to create a function that applies some function of the correct form to any such tuple and returns the result. Example usage:

applyFnToTuple ('o',('t','w')) $ \a b c -> [a,b,c] == "otw"
applyFnToTuple ('h','i') $ \a b -> [a,b] == "hi"
applyFnToTuple ("hello",('y','o')) $ \a b c -> a ++ [b,c]

I've done most of it as follows:

type family TupleFn ty out where
    TupleFn (a,b) output = a -> (TupleFn b output)
    TupleFn b output = b -> output

class ApplyFnToTuple a where
    applyFnToTuple :: a -> TupleFn a out -> out

instance ApplyFnToTuple b => ApplyFnToTuple (a,b) where
    applyFnToTuple (a,b) fn = applyFnToTuple b (fn a)

instance ApplyFnToTuple a where
    applyFnToTuple b fn = fn b 

The sticking point is that last instance. I fully expect to need to add {-# OVERLAPPABLE #-} since a is more general than the (a,b). I also struggle to see exactly how GHC could resolve a and the correct version of my TupleFn class and know the correct type sig, but I can easily put that down to my own lack of understanding. But in any case, the actual error GHCI gives me is:

Couldn't match expected type ‘a -> out’
                with actual type ‘TupleFn a out’
    Relevant bindings include
      fn :: TupleFn a out (bound at examples.hs:574:22)
      b :: a (bound at examples.hs:574:20)
      applyFnToTuple :: a -> TupleFn a out -> out
        (bound at examples.hs:574:5)
    The function ‘fn’ is applied to one argument,
    but its type ‘TupleFn a out’ has none
    In the expression: fn b
    In an equation for ‘applyFnToTuple’: applyFnToTuple b fn = fn b
Failed, modules loaded: none.

As far as I can see, no version of my TupleFn returns something with no arguments, so I don't really understand the error. However, I find it can be made to compile simply by changing the last instance to something more concrete eg:

instance ApplyFnToTuple Char where
    applyFnToTuple b fn = fn b

But that means I'd have to define lots of similar instances etc which is undesirable.

What I'd like to know is, is there a relatively easy way to make the more general version work, and why this particular error?

Thankyou :)

PS: I'm running GHC 7.10.1

Answer 1

The problem is that within the definition of the instance ApplyFnToTuple a, there is no access to the information that a isn't a tuple - I guess GHC doesn't consider how the instance might be chosen in deciding whether it is correct as a definition. This means it cannot know that TupleFn gives the right result to use, and so the instance doesn't typecheck.

To fix this, you can add an equational constraint to tell it that TupleFn is correct. Unfortunately since the constraint has to mention the out type, this requires including it as an extra type parameter to the class. At least, the following seems to work (tested with GHC 7.8 only):

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

type family TupleFn ty out where
    TupleFn (a,b) output = a -> (TupleFn b output)
    TupleFn b output = b -> output

class ApplyFnToTuple a out where
    applyFnToTuple :: a -> TupleFn a out -> out

instance ApplyFnToTuple b out => ApplyFnToTuple (a,b) out where
    applyFnToTuple (a,b) fn = applyFnToTuple b (fn a)

instance TupleFn a out ~ (a -> out) => ApplyFnToTuple a out where
    applyFnToTuple b fn = fn b 

Answer 2

As usual you can do this with singletons and type families:

{-# LANGUAGE GADTs, DataKinds, TypeFamilies, TypeOperators #-}

type family Tuple b as where
    Tuple b '[]       = b
    Tuple b (a ': as) = (b, Tuple a as)

type family Function as b where
    Function '[]       b = b
    Function (a ': as) b = a -> Function as b

data SingList as where
    SNil  :: SingList '[]
    SCons :: SingList as -> SingList (a ': as)

applyToTuple :: SingList as -> Tuple a as -> Function (a ': as) b -> b
applyToTuple  SNil       x      f = f x
applyToTuple (SCons as) (x, xs) f = applyToTuple as xs (f x)

main = do
    print $ applyToTuple (SCons (SCons SNil)) ('o',('t','w')) $ \a b c -> [a,b,c] == "otw"
    print $ applyToTuple (SCons SNil)         ('h','i') $ \a b -> [a,b] == "hi"
    print $ applyToTuple (SCons (SCons SNil)) ("hello",('y','o')) $ \a b c -> a ++ [b,c]

Tuple a [b, c, d] reduces to (a, (b, (c, d))).

Function [a, b, c, d] r reduces to a -> b -> c -> d -> r.

Hence if as == [b, c, d], then

Tuple a as -> Function (a ': as) r -> r

reduces to

(a, (b, (c, d))) -> (a -> b -> c -> d -> r) -> r