I've started learning about Haskell and I'm trying to specify the Haskell type signature of an arbitrary zero-order function with Int type. As far as I understand, with first-order functions it would be something like k :: Int -> Int. Would that mean that the type signature of a zero-order function would be just k :: Int, or is it wrong to assume that? Thank you in advance!
3
votes
2 Answers
6
votes
There are no "zero order" functions in Haskell. Every function in Haskell has an arity of 1: each function takes one argument, and it returns one value. The return value itself could be another function. (A higher-order function is one whose argument and/or return type is itself a function type.)
k :: Int is not a function; it's just an Int.
The closest thing to a function with arity 0 in Haskell is a function of type () -> a for some type a. Because there is only one value of type (), there is only one way to call the function: with ().
k :: () -> Int
k () = 3
(You might notice that there is exactly one function of type () -> a for each value of type a; that's a matter of some theoretical importance, but isn't really relevant to the question here.)
5
votes
There is a certain family of beliefs that start with "every function in Haskell has exactly one argument". Those beliefs are useful: they form the grounding of a very precise way to talk about Haskell and to understand the behavior of Haskell.
But they've always been a bit too strident for my taste. Despite the fact that the -> type former is binary and so technically a function has one argument and one return type, I think it's nevertheless also useful to have a shorthand for talking and thinking about Haskell that allows you to mentally and verbally chunk a type like a -> (b -> c) as "a function with two arguments". The obvious generalization of arity is then to count up how many times you have to go to the right of an arrow before you get to a non-arrow type, so that a -> (b -> c) is arity 2, Bool -> Bool -> Bool -> Bool is arity 3, and Int is arity 0. There's no problem with such definitions.
If you allow yourself that flexibility, then you can also talk more flexibly about order, so that the natural generalization of "order" is to count up how many times you can go to the left of an arrow before you are forced to bottom out at a non-arrow type. So, Bool -> Bool has order 1, (a -> b) -> [a] -> [b] has order 2 (and arity 2), ((Int -> r) -> r) -> Cont r Int has order 3... and in the world where you allow yourself that flexibility, I think it is perfectly natural to talk about Int as being an order-0, arity-0 function. (And, indeed, one can derive that all order-0 functions are arity-0.)
