Typeclass for functions with different numbers of arguments

Question

In my simple Haskell DSL, I have the following functions to call other functions:

callF :: forall a. (Typeable a)
  => (V a) -> (V a)
callF fp@(V (FunP name)) =
  pack $ FunAppl (prettyV fp) []

callF1 :: forall a b. (Typeable a, Typeable b)
  => (V (V a -> V b)) -> V a -> (V b)
callF1 fp@(V (FunP name)) arg =
  pack $ FunAppl (prettyV fp) [prettyV arg]

callF2 :: forall a b c. (Typeable a, Typeable b, Typeable c)
  => (V (V a -> V b -> V c)) -> V a -> V b -> (V c)
callF2 fp@(V (FunP name)) arg1 arg2 =
  pack $ FunAppl (prettyV fp) [prettyV arg1, prettyV arg2]

I would like to generalize this for any number of arguments using typeclasses.

This is what I've tried, but it only works for 0 or 1 arguments, and it doesn't enforce calling functions with the correct number of arguments.

class Callable a b | a -> b where
  call :: V a -> [String] -> b

instance Callable a (V b) where
  call fp@(V (FunP name)) x = pack $ FunAppl (prettyV fp) x

instance (Typeable c, Typeable d) => Callable (V a -> V b) (V c -> V d) where
  call fun@(V (FunP name)) list arg = call fun (list ++ [prettyV arg])

Keep in mind that V a -> V b -> V c is actually V a -> (V b -> V c). You can do this through induction. Base case: V a is callable. Inductive case: given that V a is callable, then V b -> V a is callable. The instance head of the inductive case will have the general form instance Callable k => Callable (m -> k) where. — user824425

Tikhon Jelvis Tikhon Jelvis · Accepted Answer · 2013-05-16T15:59:57

The normal technique for functions with multiple arguments--like printf--is to use a recursive typeclass. For printf, this is done with a class called PrintfType. The important insight is the recursive instance:

(PrintfArg a, PrintfType r) => PrintfType (a -> r)

This basically says that if you can return a PrintfType, your function is also an instance. The "base case" is then a type like String. So, if you want to call printf with one argument, it fires two instances: PrintfType String and PrintfType (a -> r) where r is String. If you want two arguments, it goes: String, (a -> r) where r is String and (a -> r) where r is the previous (a -> r).

However, your problem is actually a bit more complex. You want to have an instance that handles two different tasks. You want your instance to apply to functions of different types (e.g. V (V a -> V b), V (V a -> V b -> V c) and so on) as well as ensuring that the right number of arguments is presented.

The first step to do this is to stop using [String] to pass in arguments. The [String] type loses information about how many values it has, so you can't check that there is an appropriate number of arguments. Instead, you should use a type for the argument lists that reflects how many arguments it has.

This type could look something like this:

data a :. b = a :. b

it is just a type for combining two other types, which can be used like this:

"foo" :. "bar"          :: String :. String
"foo" :. "bar" :. "baz" :: String :. String :. String

Now you just need to write a typeclass with a recursive instance that traverses both the type-level list of arguments and the function itself. Here's a very rough standalone sketch of what I mean; you'll have to adopt it to your particular problem yourself.

infixr 8 :.
data a :. b = a :. b

class Callable f a b | f -> a b where
  call :: V f -> a -> b

instance Callable rf ra (V rb) => Callable (String -> rf) (String :. ra) (V rb) where
  call (V f) (a :. rest) = call (V (f a)) rest

instance Callable String () (V String) where
  call (V f) () = V f

You will also have to enable a few extensions: FlexibleInstances, FucntionalDepenedencies and UndecidableInstances.

You could then use it like this:

*Main> call (V "foo") ()
V "foo"
*Main> call (V (\ x -> "foo " ++ x)) ("bar" :. ())
V "foo bar"
*Main> call (V (\ x y -> "foo " ++ x ++ y)) ("bar" :. " baz" :. ())
V "foo bar baz"

If you pass in the wrong number of arguments, you will get a type error. Admittedly, it's not the prettiest error message in the world! That said, the important part of the error (Couldn't match type `()' with `[Char] :. ()') does point out the core problem (argument lists that don't match), which should be easy enough to follow.

*Main> call (V (\ x -> "foo " ++ x)) ("bar" :. "baz" :. ())

<interactive>:101:1:
    Couldn't match type `()' with `[Char] :. ()'
    When using functional dependencies to combine
      Callable String () (V String),
        arising from the dependency `f -> a b'
        in the instance declaration at /home/tikhon/Documents/so/call.hs:16:14
      Callable [Char] ([Char] :. ()) (V [Char]),
        arising from a use of `call' at <interactive>:101:1-4
    In the expression:
      call (V (\ x -> "foo " ++ x)) ("bar" :. "baz" :. ())
    In an equation for `it':
        it = call (V (\ x -> "foo " ++ x)) ("bar" :. "baz" :. ())

Note that this might be a bit over-complicated for your particular task--I'm not convinced it's the best solution to the problem. But it's a very good exercise in enforcing more complicated type-level invariants using some more advanced typeclass features.

Typeclass for functions with different numbers of arguments

1 Answers