CODEWITHSUNDEEP
recursionfunctional-programming
Troskyvs
Troskyvs

Reputation: 8087

FP: What does "order" mean in "high order" functions? Does recursive function a "high order" function?

I have doubt about what's the real meaning of "order" when we say "high order" functions? E.g., I've got an embedded function call like:

f.g.h

So is it called a "3 order" function?

Is "High order" function a concept of static function accumulation? Then when I have a recursive function f, and in runtime its calling stack is like f.f.f.f. can we say f is high order function?

Thanks a lot.

Upvotes: 2

Views: 248

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109613

An example (javaish)

Function<Double, Double> oneOf(Function<Double, Double>... fs) {
     return fs[new Random().nextInt(fs.length)];
}

double y = oneOf(cos, sin, atan).applyTo(1.23);

This is order 2 for two reasons: parameter type and especially the result type are functions.

Upvotes: 1

Bergi
Bergi

Reputation: 665517

The order is basically the nesting level of arrows in the type.

This lecture slide on Functional Programming defines

The order of data

  • Order 0: Non function data
  • Order 1: Functions with domain and range of order 0
  • Order 2: Functions with domain and range of order 1
  • Order k: Functions with domain and range of order k-1

So basically a zeroth-order function is no function, a first-order normal function that only operates on data, and everything else is a higher-order function.

(These slides seem to have an off-by-one error)

Let's get to some (Haskell) examples:

-- no arrow, clearly some plain data
x :: Int
x = 0

-- one arrow, so it's a first-order function:
add2 :: Int -> Int
add2 = (+ 2)

-- still one arrow only:
add :: (Int, Int) -> Int
add = uncurry (+)

-- and this is a first-order function as well:
add4 :: Int -> Int
add4 = add2 . add2

As you can see, it doesn't matter whether you are using function composition (a higher-order function) to define your functions, only their result type matters. Therefore your f.g.h and f.f.f.f examples are only first-order functions (given that f is one).

Simple examples of higher-order functions are multivariate functions:

-- two arrows! Looks like a second-order function
plus :: Int -> Int -> Int
plus = (+)

The type of the curried function is actually Int -> (Int -> Int) where we can clearly see that it's a function that has a first-order function as the result, so it is of order 2. The lower order of the input (0) doesn't really matter.

We can see the same in a more interesting example, function composition:

compose :: ((b -> c), (a -> b)) -> a -> c
compose (f, g) x = f (g x)

Here both of the parameters and the result are each a first-order function, so compose is of order 2.

Another example is the fixpoint combinator fix :: (a -> a) -> a which does have a first-order function as the input and a zeroth-order result, making it second order overall.

And the curried composition operator as we know it

(.) :: (b -> c) -> ((a -> b) -> (a -> c))

would even be considered a third-order function.

Upvotes: 5

Related Questions