Not saying it's wrong, but "foo is a second-order function" is a distinctly minority opinion.
To a useful first approximation, Haskell works as a cartesian-closed category, which basically means we have tuples and that tuples harmonize with functions so that foo behaves just like
uncurry foo :: (a,b) -> c
which is a first-order function.
So the majority opinion calls foo a first-order arity-2 function.
Here's a bar function that's truly second-order:
bar :: (a -> b) -> c
In general, the order of a function is the count of parens nesting the leftmost innermost arrow. It is invariant to currying/uncurrying as well as permutation of arguments.
The same counting principle applies to other invariants such as ranks and kinds.
"How high can the order of a function go?" is the question explored in this blog post [0]. Note how the author's definition of order -- essentially the same given here -- got left and right mixed up.
To a useful first approximation, Haskell works as a cartesian-closed category, which basically means we have tuples and that tuples harmonize with functions so that foo behaves just like
which is a first-order function.So the majority opinion calls foo a first-order arity-2 function.
Here's a bar function that's truly second-order:
In general, the order of a function is the count of parens nesting the leftmost innermost arrow. It is invariant to currying/uncurrying as well as permutation of arguments.The same counting principle applies to other invariants such as ranks and kinds.
"How high can the order of a function go?" is the question explored in this blog post [0]. Note how the author's definition of order -- essentially the same given here -- got left and right mixed up.
[0] http://math.andrej.com/2006/03/21/interesting-higher-order-f...