24

Is it possible to write a function arity :: a -> Integer to determine the arity of arbitrary functions, such that

> arity map
2
> arity foldr
3
> arity id
1
> arity "hello"
0

?

3
  • I believe it is possible using clever tricks with the type system. Search for variadic or polyvariadic functions in haskell.
    – scravy
    Commented Dec 3, 2011 at 16:45
  • I think this is an interesting question, and I'm amazed by max taldykin's answer, but I do wonder - what would you use such a function for? Commented Sep 21, 2012 at 15:19
  • 1
    @Frerich At the time of this question I was reading Elements of Programming by Stepanov and McJones where they introduced the type attribute Arity(F) that returns the number of inputs of F. I was curious if I could implement some of the functions they defined in Haskell. Commented Sep 23, 2012 at 10:47

6 Answers 6

26

Yes, it can be done very, very easily:

arity :: (a -> b) -> Int
arity = const 1

Rationale: If it is a function, you can apply it to exactly 1 argument. Note that haskell syntax makes it impossible to apply to 0, 2 or more arguments as f a b is really (f a) b, i.e. not f applied to a and b, but (f applied to a) applied to b. The result may, of course, be another function that can be applied again, and so forth.

Sounds stupid, but is nothing but the truth.

2
  • 6
    +1 for stupid truth. All Haskell functions have arity 1, because it's OK for functions to produce functions. a -> b -> c is just sugar for a -> (b -> c).
    – Dan Burton
    Commented Dec 3, 2011 at 21:53
  • 5
    Alright then, is is possible to recursively find the depth of a tree of functions? Commented Dec 5, 2011 at 7:38
19

It's easy with OverlappingInstances:

{-# LANGUAGE FlexibleInstances, OverlappingInstances #-}

class Arity f where
  arity :: f -> Int

instance Arity x where
  arity _ = 0

instance Arity f => Arity ((->) a f) where
  arity f = 1 + arity (f undefined) 

Upd Found problem. You need to specify non-polymorphic type for polymorphic functions:

arity (foldr :: (a -> Int -> Int) -> Int -> [a] -> Int)

Don't know how to solve this yet.

Upd2 as Sjoerd Visscher commented below "you have to specify a non-polymorphic type, as the answer depends on which type you choose".

10
  • What for do we need OverlappingInstances?
    – scravy
    Commented Dec 3, 2011 at 17:00
  • 2
    @scravy, instance Arity x is more general than instance Arity ((->) a f). So without extensions GHC can't choose which of this two instances to use for functions. OverlappingInstances instructs GHC that a) such instances are allowed; b) she need to choose most specific one. Commented Dec 3, 2011 at 17:05
  • 1
    It makes sense that you have to specify a non-polymorphic type, as the answer depends on which type you choose, f.e.: arity (foldr :: (a -> (Int -> Int) -> Int -> Int) -> (Int -> Int) -> [a] -> Int -> Int) Commented Dec 3, 2011 at 17:35
  • 3
    Ok after some playing around, the solution is to add the IncoherentInstances LANGUAGE pragma ;)
    – is7s
    Commented Dec 3, 2011 at 19:15
  • 1
    @DanBurton I'm not really sure what's happening here, but I think lambda expressions have different internal representations than normal functions which are causing this. They might be optimised somehow. For example arity (\x y z -> (x,y,z)) is 3, arity (\x y z -> x)` is 0, arity (\x y z -> (x,y) is 2 and arity (\x y z -> (x,z)) is surprisingly 1. What's to be noticed here is that if all variables on the left side occur on the right side then the result is correct, however if not all of them occur on the right side the result does not make sense. We need some GHC expert :D
    – is7s
    Commented Dec 3, 2011 at 22:32
12

If id has arity 1, shouldn't id x have arity 0? But, for example, id map is identical to map, which would has arity 2 in your example.

Have the following functions the same arity?

f1 = (+)
f2 = (\x y -> x + y)
f3 x y = x + y

I think your notion of "arity" is not well defined...

3
  • Can't you simply say that id x has the arity of x's arity? I mean, it's reasonable if you look at id :: a -> a.
    – Tarrasch
    Commented Dec 3, 2011 at 16:47
  • 1
    My definition of arity: Count the number of -> in a function's type which are not enclosed in parentheses. So the arity of id x depends on x. Commented Dec 3, 2011 at 17:01
  • 1
    I define arity as the number of times you can apply an argument to a term. If the argument's type is not specified, use ().
    – fuz
    Commented Dec 3, 2011 at 17:07
3

In Haskell, every "function" takes exactly one argument. What looks like a "multi-argument" function is actually a function that takes one argument and returns another function which takes the rest of the arguments. So in that sense all functions have arity 1.

2

It's not possible with standard Haskell. It may be possible using the IncoherentInstances or similar extension.

But why do you want to do this? You can't ask a function how many arguments it expects and then use this knowledge to give it precisely that number of arguments. (Unless you're using Template Haskell, in which case, yes, I expect it is possible at compile time. Are you using Template Haskell?)

What's your actual problem that you're trying to solve?

2
  • 5
    There is no actual problem, I'm just curious. Commented Dec 3, 2011 at 16:56
  • I found a usecase, I want to lift normal functions into equivalent enumeratee or tranducer coroutines. It would be useful to know how many parameters a function can take until it gives back an instance of type of kind *. Commented Aug 21, 2015 at 12:15
1

How about this:

arity :: a -> Int
arity (b->c) = 1 + arity (c)
arity _ = 0
1
  • GHCi complains: Not in scope: "b" Commented Dec 5, 2011 at 21:09

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.