Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")?

Question

1. Is there one (or a few) canonical/ specific use cases for "functions returning functions" (beyond "decorators")?

2. What can you do with "functions returning functions" that you cannot (easily or elegantly or expressively) do with functions as variables ("functions taking functions as their arguments") and/or composing functions, as in :(f(g(x)).

Answer 1

A common reason to return a function is when programming with iterators. Specifically, when you have a data structure (such as a list or set) and you want to return an iterator over it.

In a pure functional style, an iterator is an initial state init: S together with a function

next: S -> Option<(A, S)>

where S is the state of the iterator and A is the output type of the iterator. It takes in a current state and returns either None or a value and a new state.

So, if you want to define an iterator over a list, you need to write a function

iterate_over_list: List A -> (S, S -> Option<(A, S)>)

where S is defined appropriately -- depending on your implementation it could either be (List A, int) (the list together with an index into it) or just List A if you consume the list while iterating over it.

There's no way to avoid returning a function here because an iterator is something that you call repeatedly (every time you want a new element, you ask the iterator to generate a new element).

---

To give an even simpler example along the same lines, sometimes you want an iterator over all integers starting at a given integer. Then you would write a function

iterate_starting_from: int -> (S, S -> Option<(int, S)>)

where S in this case would just be int (the state of the iterator is the current integer to be returned). The implementation of this is something like (in pseudocode):

iterate_starting_from(i):
    let init = i
    let next = lambda x: Some((x, x+1))
    return (init, next)

Answer 2

Here is my opinion on the matter:

Take for example, the derivative operator. For clarity, we will denote by $der(f)$ the derivative of $f$ (which is usually written as $f'$).

The derivative function $der$, takes as an input a deriviable function $f$, and returns a different function which is its derivative: $der(f)$.

In a similar way, an integral is a function of functions. Also function composition can be thought of as a function $compose(f,g)=f\circ g$.

Essentially, the main "basic" use of such functions allow us to create certain "traits" or "behaviours" of "regular" functions, that we can define to all functions simultaneously.

That being said, there are more complex and interesting examples, such as linear transfomations in the dual vector space, or other things similar to it - which are much more complex and are useful for other things as well.