[orbifold]

One instance would be function composition. If functions are values in your language, you can define function composition in the language, that is given a function f : a -> b and g : b -> c, you can define their composition g . f : a -> c as

g . f = \x -> g(f(x))

(Here \ denotes lambda)

Why would it be useful to have function composition in your language? Well it gives you similar power as "method chains" in an object oriented language, without being tied to specific classes, especially if the language also supports polymorphic functions. It also interacts nicely with other abstractions usually found in functional languages: For example consider map, of Map-Reduce fame

map : (Functor f) => (a -> b) -> (f a -> f b)

then one has

map (g . f) = map g . map f

Now imagine that map would cause the function to be send to thousands of nodes in a cluster, then the above identity tells you that instead of doing that twice, once for f and once for g, you might aswell take g . f and send it out once. Also say you would for some reason know that f . g = id, the identity function, then

map id = id,

so you would not need to do anything. This might appear trivial, but if you can teach the compiler about those cases, you can do interesting stuff with it. In the case of GHC (the Glasgow Haskell Compiler), it is able to use such rules in its optimization phase, which allows people to write apparently inefficient but declarative code and let the compiler eliminate intermediate values. See for example https://hackage.haskell.org/package/repa.

[Dewie]

Why do you need lambdas/closures in order to have function composition? Don't you just need higher order functions?

The thing about map id = id etc. probably has more to do with equational reasoning (can use equals to substitute terms, since there are no side effects, at least in Haskell), but I don't see the connection to lambdas/closures.

[lmkg]

The function returned by 'compose' is a closure because it captures references to its local environment (the two functions passed to 'compose'). If it did not close over these variables, it would not work. It might be possible to define a limited 'compose' operator in a language without closures that worked at compile-time/define-time, but you wouldn't be able to choose functions to compose at run-time like you could with a capturing 'compose.'

Nitpick: Lambdas and closures are different things. A closure is a semantic notion of a function captures its local environment. A lambda is a mostly-syntactic notion of defining a function without giving a name. Whether a lambda is a closure depends on the language's scoping rules.

[orbifold]

What you need is that functions are values in your language. Lambdas are just a notation for function values. Typed lambda calculus is the internal language of cartesian closed categories and function values are then called internal morphisms. The composition above is then the internal composition of internal morphisms. It would be possible for external composition to be already defined by the language, take the unix shell for example, with its buildin "|" operator. But if you want to be able to define function composition within the language, you need to have something like lambda.

[Dewie]

> What you need is that functions are values in your language.

Well yeah, that's what I meant by higher order functions.

> Lambdas are just a notation for function values.

But regular (named) functions can still be used as function values. So this doesn't explain why you need things like lambdas in order to implement function composition.

> Typed lambda calculus is the internal language of cartesian closed categories and function values are then called internal morphisms. The composition above is then the internal composition of internal morphisms.

Ok bud.

> But if you want to be able to define function composition within the language, you need to have something like lambda.

Well I could implement function composition without the syntactic construct lambda:

(.) g f x = g (f x)

I am not using any lambdas, in the sense of anonymous functions or closures. To implement function composition with a lambda is more of a stylistic choice, in this case. Granted, maybe functions-used-as-values are also lambdas, for all I know.

[dllthomas]

(.) g f x = g (f x)

Interesting. I might say that partial application is a kind of closure. Certainly, it winds up the same - "function carrying some data that it uses internally". I think you are correct that compose and apply does not require closures of any sort.

[orbifold]

Well (.) g f x = g (f x) in Haskell is just sugar for (.) g f = \x -> g (f x), which ultimately is turned into (.) = \g -> \f -> \x -> g (f x)