Haskell: playing with TypeFamilies couldn't get the problem out

I have a game with TypeFamilies and such in Haskell. I am trying to create a simple example where I have a function that takes some type ( Parsers ty

) below, and a function that takes multiple arguments depending on that ty

and outputs some result.

Here's the whole piece of code up:

{-# LANGUAGE UndecidableInstances, TypeFamilies,GADTs #-}


data V a   --"variable"
data S a   --"static"
data C a b --combination

--define data type:
data Parsers ty where
  ParVar :: a -> Parsers (V a)
  ParStatic :: a -> Parsers (S a)
  ParCombine :: Parsers ty1 -> Parsers ty2 -> Parsers (C ty1 ty2)

--basic type alias to below, output set to Bool
type ExtractVars parsers = GetVars parsers Bool

--we want to convert some combination of C/S/V
--types into a function taking, from left to right,
--each type inside S as parameter
type family GetVars parsers output where
  GetVars (S a) output = output
  GetVars (V a) output = a -> output
  GetVars (C a b) output = GetVars a (GetVars b output)

--this function uses the above such that, hopefully,
--the second argument to be provided will be a function
--that will take each S type as an argument and return
--a bool. We then return that bool from the whole thing
getVars :: Parsers p -> ExtractVars p -> Bool
getVars (ParVar s) fn = fn s
getVars (ParStatic _) fn = fn
-- this is the offending line:
getVars (ParCombine a b) fn = getVars b (getVars a fn)

      

        
        
        
      

    

My Parsers ty

type seems to be correct; building things with it results in the types I would expect, for example:

ParVar "hi" 
  :: Parsers (V [Char])
ParCombine (ParVar "hi") (ParStatic "woop")
  :: Parsers (C (V [Char]) (S [Char]))
ParCombine (ParVar 'h') (ParCombine (ParStatic True) (ParVar "hello"))
  :: Parsers (C (V Char) (C (S Bool) (V [Char])))

      

        
        
        
      

    

Likewise, my type family GetVars

seems to be doing the right thing by doing conversions such as:

(C (V a) (V b)) out => a -> b -> out
(V a) out           => a -> out
(S a) out           => out
(C (S a) (V b) out  => b -> out

      

        
        
        
      

    

Basically, choosing the right things with tags V

in the right order and ignoring the S

s

Then my function GetVars

uses this in its type signature:

getVars :: Parsers p -> ExtractVars p -> Bool

      

        
        
        
      

    

To say that regardless p

, expect a function that matches my type alias ExtractVars p

and return a Bool

.

In my function, GetVars

these two definitions cause no problem:

getVars (ParVar s) fn = fn s
getVars (ParStatic _) fn = fn

      

        
        
        
      

    

but the last one:

getVars (ParCombine a b) fn = getVars b (getVars a fn)

      

        
        
        
      

    

Failed to type check with errors:

test.hs:74:42:
    Could not deduce (GetVars ty2 Bool ~ Bool)
    from the context (p ~ C ty1 ty2)
      bound by a pattern with constructor
                 ParCombine :: forall ty1 ty2.
                               Parsers ty1 -> Parsers ty2 -> Parsers (C ty1 ty2),
               in an equation for ‘getVars’
      at test.hs:74:10-23
    Expected type: ExtractVars ty2
      Actual type: Bool
    Relevant bindings include b :: Parsers ty2 (bound at test.hs:74:23)
    In the second argument of ‘getVars’, namely ‘(getVars a fn)’
    In the expression: getVars b (getVars a fn)

test.hs:74:52:
    Could not deduce (GetVars ty1 Bool
                      ~ GetVars ty1 (GetVars ty2 Bool))
    from the context (p ~ C ty1 ty2)
      bound by a pattern with constructor
                 ParCombine :: forall ty1 ty2.
                               Parsers ty1 -> Parsers ty2 -> Parsers (C ty1 ty2),
               in an equation for ‘getVars’
      at test.hs:74:10-23
    NB: ‘GetVars’ is a type function, and may not be injective
    Expected type: ExtractVars ty1
      Actual type: ExtractVars p
    Relevant bindings include
      b :: Parsers ty2 (bound at test.hs:74:23)
      a :: Parsers ty1 (bound at test.hs:74:21)
    In the second argument of ‘getVars’, namely ‘fn’
    In the second argument of ‘getVars’, namely ‘(getVars a fn)’
Failed, modules loaded: none.

      

        
        
        
      

    

(line 74 is ParCombine's failure to define getVars)

I hit my head on the table trying to figure out where I'm going wrong, but I don’t want to, and I want to get a solid assurance that the members of the type family look amazing (the above example is, for example, the ability to expect some type of function depending on input - it will be incredibly cool!)

Can anyone point me in the right direction or fix my possibly very stupid mistake?

Thank!

(PS I am using GHC 7.10.1 and running this in ghci)

Edit . Just to say that this was an example of a few motivated paper types of families, in particular example sprintf here , I may have missed something important, trying to separate what I wanted from him!