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

My eventual solution, for anyone finding this question:

As DanielWagner suggested, I ended up preferring the slightly tweaked formatting (using () at the end of a tuple chain to signify finish). This makes it pretty straightforward like so:

type family TupleFn ty out where
    TupleFn () output = output
    TupleFn (a,b) output = a -> (TupleFn 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 () where
    applyFnToTuple _ fn = fn

and this can be used like:

applyFnToTuple ('a',('b',())) $ \a b -> [a,b] == "ab"
applyFnToTuple ("hello",(12,('r',()))) $ \h n r -> h ++ show n ++ [r] == "hello12r"

I expect the instances can be tweaked; these were just the first I tried that GHC liked :)

Ørjan Johansen's approach (see his answer) is a wee bit more complicated but delivers an even neater end case!

As a side note, where I have wanted to translate some structure into a corresponding function I've actually ended up just using my own data type for the extra power it gives me. The simplest form of that I can come up with (not using DataKinds for now) to use as an example is:

--using DataKinds these could be done slightly neater:
data Cons a b
data Nil

-- the list itself, where the type 'a' is built from the above tags
data MyList a where
    LCons :: itemty -> MyList a -> MyList (Cons itemty a)
    LNil  :: MyList Nil

-- this type family converts that type 'a' to a function signature.
type family MyListFn a output where
    MyListFn (Cons a b) output = a -> (MyListFn b output) 
    MyListFn Nil output = output

-- this function applies items in MyList a to a MyListFn a just
-- like we did with tuples. Note no type family, because
-- no type dependant differences in behaviour needed:
applyFnToMyList :: MyList a -> MyListFn a out -> out
applyFnToMyList (LCons a b) fn = applyFnToMyList b (fn a)
applyFnToMyList LNil fn = fn

with very similar usage as the tuple case:

applyFnToMyList (LCons 'a' (LCons 'b' LNil)) $ \a b -> [a,b] == "ab"
applyFnToMyList (LCons "hello" (LCons 12 (LCons 'r' LNil))) $ \h n r -> h ++ show n ++ [r] == "hello12r"

TL;DR You can create functions that apply a function of whatever parity required over some elements of a polymorphic data structure in a totally type safe way. Awesome stuff, Haskell!

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

Answer 3

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