Haskell: Function to determine the arity of functions?

Question

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

?

Hemingway

I believe it is possible using clever tricks with the type system. Search for variadic or polyvariadic functions in haskell. – Pneumograph

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? – Misogynist

@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. – Hemingway

Answer 1

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".

Causerie

What for do we need OverlappingInstances? – Pneumograph

@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. – Causerie

@max Does not work for me:arity const gives me Ambiguous type variable 'a0' in the constraint: (Arity a0) arising from a use of 'arity' – Hemingway

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) – Ingunna

Ok after some playing around, the solution is to add the IncoherentInstances LANGUAGE pragma ;) – Oolite

@Oolite - nice to know there's an actual use for Incoherent Instances :) And +1 for this cool answer, it's awesome to see arity foldr produce 3 in ghci. – Nephelinite

@Oolite - buuuut IncoherentInstances gets confused with lambda expressions. arity $ \x y -> 3 produces 0 with Incoherent Instances, 2 without. Perhaps this is an area where IncoherentInstances could be improved? – Nephelinite

@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 – Oolite

The confusion for lambdas does not requireIncoherentInstances. It is confused by default. For example arity (\x -> x) gives 0. In fact this happens whenever the lambda doesn't do something useful to the parameter. If you do something useful like arity (\x -> x + 1), you get 1. If you do something useful to 2 parameters (like adding them up), you get the 2. I think this has something to do with laziness, if the parameter is not used in a useful way, it doesn't count it as an arity. – Zurheide

@Zurheide Sounds like a compiler optimisation is to blame for that 😊 – Blockhouse

Answer 2

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.

Decomposition

+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). – Nephelinite

Alright then, is is possible to recursively find the depth of a tree of functions? – Muskrat

Answer 3

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...

Apocynthion

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. – Shortcake

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. – Hemingway

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 (). – Boll

Answer 4

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.

Apterygial

Answer 5

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?

Ellsworth

There is no actual problem, I'm just curious. – Hemingway

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 *. – Zurheide

Answer 6

How about this:

arity :: a -> Int
arity (b->c) = 1 + arity (c)
arity _ = 0

Muskrat

GHCi complains: Not in scope: "b" – Hemingway