23

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

?

Frank S. Thomas
  • 4,725
  • 2
  • 28
  • 47
  • I believe it is possible using clever tricks with the type system. Search for variadic or polyvariadic functions in haskell. – scravy Dec 03 '11 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? – Frerich Raabe Sep 21 '12 at 15:19
  • 1
    @Frerich At the time of this question I was reading [Elements of Programming](http://www.elementsofprogramming.com/) 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. – Frank S. Thomas Sep 23 '12 at 10:47

6 Answers6

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.

Ingo
  • 36,037
  • 5
  • 53
  • 100
  • 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 Dec 03 '11 at 21:53
  • 5
    Alright then, is is possible to recursively find the depth of a tree of functions? – John F. Miller Dec 05 '11 at 07:38
18

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

max taldykin
  • 12,459
  • 5
  • 45
  • 64
  • What for do we need OverlappingInstances? – scravy Dec 03 '11 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. – max taldykin Dec 03 '11 at 17:05
  • @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'` – Frank S. Thomas Dec 03 '11 at 17:09
  • 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)` – Sjoerd Visscher Dec 03 '11 at 17:35
  • 3
    Ok after some playing around, the solution is to add the `IncoherentInstances` LANGUAGE pragma ;) – is7s Dec 03 '11 at 19:15
  • @is7s - 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. – Dan Burton Dec 03 '11 at 21:58
  • @is7s - 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? – Dan Burton Dec 03 '11 at 22:07
  • 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 Dec 03 '11 at 22:32
  • The confusion for lambdas does not require`IncoherentInstances`. 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. – CMCDragonkai Aug 21 '15 at 12:30
  • @CMCDragonkai Sounds like a compiler optimisation is to blame for that – jsdw Aug 23 '15 at 12:51
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...

sth
  • 222,467
  • 53
  • 283
  • 367
  • 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 Dec 03 '11 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`. – Frank S. Thomas Dec 03 '11 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 Dec 03 '11 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.

newacct
  • 119,665
  • 29
  • 163
  • 224
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?

dave4420
  • 46,404
  • 6
  • 118
  • 152
  • 5
    There is no actual problem, I'm just curious. – Frank S. Thomas Dec 03 '11 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 `*`. – CMCDragonkai Aug 21 '15 at 12:15
1

How about this:

arity :: a -> Int
arity (b->c) = 1 + arity (c)
arity _ = 0
John F. Miller
  • 26,961
  • 10
  • 71
  • 121