Scala Higher-Order Functions — Functions as Values

What a function value is on the JVM

Scala's standard library declares twenty-three traits, Function0 through Function22, each with a single abstract apply method of the matching arity. The literal (x: Int) => x * 2 is a Function1[Int, Int]; the type ascription Int => Int is sugar for exactly that. Because it is an object, a function can be assigned to a val, stored in a field, put in a Map, returned from a method, and passed to another method - which is the only thing "first-class" means here.

The important consequence is erasure. Function1[T1, R] is generic, so the method that actually lands in the class file is apply(Object): Object. A (Int, Int) => Int therefore boxes both arguments and its result at the call boundary unless something rescues it, and the something is a specialized subtrait discussed further down. The generic apply is also the reason a function value can never be overloaded, take a by-name parameter, take an implicit parameter, declare its own type parameters, or have default arguments: there is exactly one apply signature and it is fixed by the trait.

Scala 2.12 added a second target shape. Any Java interface with a single abstract method is a valid lambda target, so val r: Runnable = () => log("tick") compiles without an explicit new, and Java APIs that take a functional interface accept Scala lambdas directly rather than through an implicit conversion.

How a lambda is compiled - the invokedynamic story

Through Scala 2.11 every lambda produced a class file. A single method with three lambdas in it emitted Outer$$anonfun$1, $anonfun$2 and $anonfun$3, each extending AbstractFunction1. Large codebases paid for that in artifact size, class-loading time and permgen/metaspace pressure, and the -Ydelambdafy:method flag existed precisely to lift the bodies out of those classes.

From 2.12 onward - which is also the release that made Java 8 the floor - the compiler emits the lambda body as a private static method in the enclosing class and replaces the lambda expression with an invokedynamic instruction bootstrapped by the JDK's LambdaMetafactory. No anonymous class exists in the jar. The implementing class is spun at first linkage of that call site, once per site for the life of the JVM.

This is the detail that decides the allocation story, and it splits cleanly:

• Non-capturing lambda - xs.map(_ + 1). The metafactory has nothing to close over, so it can hand back the same instance forever. The lambda allocates zero objects per evaluation after the call site is linked.
• Capturing lambda - xs.map(_ + n) where n comes from the enclosing scope. Captured values become constructor arguments, so one object is allocated each time the lambda expression is evaluated. Inside a loop, that is one allocation per iteration.

The practical rule falls straight out: hoisting a capturing lambda out of a loop into a val is a real optimisation, and doing the same to a non-capturing one changes nothing.

Methods are not functions, and eta-expansion is the bridge

A def does not have a function type. It has a method type, which is not first-class and cannot be the type of a value - the type-level reasoning for that separation is developed in the Scala type system article and is not repeated here. What matters at this level is what the bridge emits.

Converting a method to a function value is eta-expansion, written m _ in Scala 2 and performed automatically by Scala 3 wherever a function type is expected (m _ is deprecated there; m(_) remains the way to spell partial application when the arity is ambiguous). The conversion is not free and it is not a no-op:

def scale(f: Double, x: Double): Double = f * x

val g = scale _              // a Function2[Double, Double, Double] object
val h = scale(2.0, _: Double) // a Function1, with 2.0 captured

xs.map(scale(2.0, _))        // eta-expansion at every evaluation of the arg

g is a wrapper object whose apply forwards to the static method; it goes through the same invokedynamic path as a lambda, so a wrapper over a static or module method can be linked to a cached singleton, while obj.m _ must capture obj and therefore allocates. The forwarding apply also re-introduces boxing that the direct method call did not have, because the wrapper's erased signature is apply(Object): Object.

Two consequences bite in review. Calling obj.m _ inside a hot loop allocates a wrapper per iteration for no benefit over calling obj.m(x) directly. And a method that was generic loses its polymorphism on conversion: def id[A](a: A) = a eta-expands only at a fixed A, because Scala 2 has no polymorphic function values at all and Scala 3's polymorphic function types are a separate construct.

The arity wall - Function0 through Function22

There is no Function23. The FunctionN traits are generated source, they stop at twenty-two, and TupleN stops at the same number for the same reason. A method may take twenty-three parameters, but the moment you want that as a value the compiler has nowhere to put it.

In practice the wall is hit by generated code rather than by hand-written code: case classes projected from a wide database table, protobuf or Avro mappings, and configuration objects. The escapes are ordinary design moves - group parameters into a case class and take one argument instead of twenty-three; take a builder or a Map[String, Any] at the boundary and validate into a typed shape; or keep the wide thing as a def and never lift it to a value, since methods have no such limit. Shapeless-style HList encodings dodge the arity limit generically, and that machinery is covered in the Shapeless article.

The limit is worth knowing about mostly because the error message is unhelpful. A missing Function23 surfaces as a plain "not found: type" or an inference failure some distance from the real cause, and it is a fifteen-minute puzzle the first time.

Closures - what actually gets captured

A lambda that references a name from an enclosing scope closes over it, and Scala's rule is capture-by-value for a val: the value is copied into the closure object's field at construction. That is why the Java 8 "effectively final" restriction has no Scala analogue for vals, and why for (i <- 1 to 3) yield () => i gives three closures that return 1, 2 and 3 - the for desugars to foreach/map, so each iteration has a genuinely fresh i parameter.

A captured var is the case that surprises people. A local var lives on the stack, and a closure can outlive the frame, so the compiler lifts it into a heap cell - scala.runtime.IntRef, ObjectRef, and friends - and rewrites every read and write, inside and outside the closure, to go through cell.elem. Every closure that captures that var shares one cell:

var i = 0
val fs = scala.collection.mutable.ListBuffer.empty[() => Int]
while (i < 3) { fs += (() => i); i += 1 }
fs.map(_())   // List(3, 3, 3) - one shared IntRef, read after the loop

The same lifting explains a class of concurrency bug: a var mutated inside a lambda handed to a Future or a parallel collection is an unsynchronised shared field, not a thread-local, and it races. It also explains a memory-shape problem. Referring to a field or a method of the enclosing class inside a lambda captures this, not the field - so a small lambda registered in a long-lived callback table can pin an entire object graph, and in Spark the same capture is what turns an innocuous rdd.map(row => helper(row)) into a Task not serializable failure. The fix in both cases is to bind what you need to a local val before the lambda and close over that.

Currying and multiple parameter lists

def f(a: Int)(b: Int) and def f(a: Int, b: Int) compile to the same thing on the JVM: one method taking two arguments. Multiple parameter lists are a front-end feature, not a different runtime shape, and writing f(1) alone is a compile error rather than a function of one argument. A real chain of nested function values only appears when you ask for one, via (f _).curried or by partial application - and each link in that chain is a separate Function1 object.

What the extra list buys you is four things the single list cannot express:

• Type inference flows left to right across lists. Fixing the accumulator type in an earlier list is why foldLeft(z)(op) has the shape it does; the inference argument is developed in the type system article.
• Only a trailing list may be implicit / using, which is the entire calling convention of contextual abstraction - see implicits and type classes.
• A single-argument trailing list can be written with braces, withResource(f) { in => ... }, which is how user-defined control structures read like language syntax.
• Partial application against an earlier list gives genuinely reusable specialisations: val logAt = log(Level.Warn) _ allocates one wrapper and is then called at one argument.

The cost side is small but not zero. curried on a Function3 allocates three objects and turns one call into three virtual dispatches, so it belongs in configuration and combinator code, not in an inner loop.

By-name parameters are not quite a zero-arg function

A parameter declared x: => Int is unevaluated at the call site; the argument expression is wrapped in a thunk and re-evaluated at every mention inside the body. It is common to hear this described as a different mechanism from Function0, and at the representation level that is not accurate - the thunk is a zero-argument function object, compiled through the same lambda path, with the same allocation behaviour. The differences are all above the bytecode:

• => T is not a first-class type. You cannot write val x: => Int, cannot put one in a List, and cannot return one. It exists only in a parameter position.
• Call sites are unchanged. assert(cond, expensiveMessage) reads like a strict call; the Function0 version forces every caller to write () => expensiveMessage.
• Uses inside the body are unchanged too - x + x, not x() + x() - and that invisibility is exactly the trap: it evaluates twice, and if the argument does I/O or is expensive, it does that twice.

def retry[A](n: Int)(body: => A): A =        // body re-run per attempt: correct
  try body catch { case _: Exception if n > 0 => retry(n - 1)(body) }

def orElse[A](a: => A, b: => A): A = {
  lazy val fst = a                            // memoise when you want once-only
  if (fst != null) fst else b
}

Re-evaluation is the feature when you are writing retry, a lazy ||, or a logger that must not build a string it will discard; it is the bug when the caller assumed once-only. lazy val inside the body is the standard way to pin it down, at the cost of one initialisation check per read.

The combinator interface, read as an interface

map, flatMap, filter, foreach and withFilter are not a collections convenience. They are the structural interface the language itself compiles against: a for comprehension desugars to flatMap chains ending in a map, with guards routed through withFilter so no intermediate collection is built, and foreach substituted when there is no yield. That desugaring is purely syntactic and untyped - it names the methods and lets normal resolution find them - which is why Option, Try, Either, Future, ZIO effects and your own types all work in a for without inheriting from anything.

Reading it as an interface changes how you design types. If a wrapper of yours has a sensible "transform the inside" and "transform and flatten" operation, naming them map and flatMap buys comprehension syntax for free. If it does not, borrowing the names to mean something else will produce comprehensions that compile and mislead.

collect is the member of this family worth calling out separately, because it takes a PartialFunction and so fuses filter-then-map into one pass with one lambda instead of two.

foldLeft, foldRight, reduce and fold

The four aggregation combinators differ in ways that matter more than their signatures suggest.

foldLeft(z)(op) is a tail-recursive left-to-right traversal, implemented as a loop, and safe on a collection of any size. foldRight associates from the right, and the naive definition op(x, foldRight(rest)) is not tail-recursive: one stack frame per element, and a StackOverflowError on a long strict sequence. Library implementations dodge this by reversing and folding left - which is correct but means foldRight on a strict collection buys you nothing except argument order and a traversal you have paid for twice.

The case where foldRight is genuinely different is a lazy structure. If the combining function takes its accumulator by name, a right fold over a LazyList can short-circuit without forcing the tail, so it terminates on an infinite source where a left fold cannot. That is the reason the operation exists; on a List[Int] it is the wrong default.

reduce has no zero and throws UnsupportedOperationException on an empty collection - a genuine production failure mode when the input is a filtered stream that happened to match nothing, and the reason reduceOption exists. fold(z)(op) is deliberately weaker than foldLeft: its signature forces accumulator and element to the same type, and it makes no promise about traversal order, so it is safe to parallelise and only correct if z is a true identity and op is associative. Passing 0 to a subtraction, or "" to a non-associative combine, gives an answer that is right sequentially and wrong under .par.

Composition and PartialFunction

Function1 carries andThen and compose, which differ only in direction: f andThen g applies f first, g compose f is the same pipeline written the way mathematicians write it. Each combinator returns a new Function1 whose apply calls the two originals, so a five-stage composition is five objects and five virtual dispatches per element rather than one inlined body. Function.chain(Seq(f, g, h)) folds a sequence of endomorphisms into one and has the same cost profile.

PartialFunction[A, B] extends A => B but is a materially different contract: it adds isDefinedAt(a): Boolean and promises nothing about apply outside that domain. The literal { case Some(x) => x } becomes a PartialFunction when a PartialFunction is expected and an ordinary Function1 that throws MatchError otherwise - the same source text, two different types, decided by the expected type.

The API is built around not running the match twice. applyOrElse(x, default) tests and applies in one pass; lift turns the partial function into a total A => Option[B]; orElse chains domains so the first one that is defined wins. Calling if (pf.isDefinedAt(x)) pf(x) by hand runs the pattern match twice and is the mistake applyOrElse exists to prevent. This is also the mechanism behind collect, Akka's receive, and recover on Future and Try: each is an open-ended dispatch table that must be able to say "not mine" without throwing.

What higher-order code costs

Three costs are specific to function values, as opposed to the collection-level costs of intermediate allocation and element boxing that collections performance covers.

Boxing at the apply boundary. Because apply erases to Object, a (Int, Int) => Int would box on every call. The standard library works around this by annotating Function0, Function1 and Function2 with @specialized over a subset of primitive types, which generates specialized subtraits with primitive signatures - JFunction1$mcII$sp is the Int => Int variant, the mc suffix spelling result type then argument types. When the compiler can see the primitive types statically it targets the specialized apply and no boxing occurs. Function3 and above have no specialization at all, so a three-argument numeric lambda boxes unconditionally.

Megamorphic call sites. The apply call inside map is a single bytecode shared by every caller. HotSpot inlines it happily when the profile shows one or two receiver types; at three or more the site is megamorphic, profile-guided inlining stops, and the body becomes a real interface dispatch. A generic combinator used from a dozen places in the codebase is exactly that shape, which is why a hand-written while loop sometimes beats a map that is fine in a microbenchmark and slow in the application.

Inlining budgets. HotSpot's defaults - roughly 35 bytecodes for a cold callee, 325 for a hot one - are per-method, and a composed pipeline is many small frames rather than one. Scala's own inliner (-opt:inline -opt-inline-from:** in 2.13) can flatten some of this at compile time, at the cost of binary compatibility if you inline across library boundaries you do not control.

Where the abstraction stops paying

The failure mode of higher-order code is not usually performance, it is legibility. A chain of six combinators with point-free lambdas is compact to write and hostile to read six months later, and the compiler will not help because it type-checks perfectly. The practical threshold most teams converge on is that a pipeline stops being an improvement somewhere around four stages or the first nested lambda, and the fix is naming the intermediate steps as vals - which costs nothing at runtime and restores the ability to read the code top to bottom.

Debugging degrades too. A stack trace through lambda-heavy code is a column of synthetic $anonfun$method$1 frames with no argument values, and since 2.12 there is no anonymous class name to grep for either. Breakpoints inside a lambda work, but stepping through a composed pipeline in a debugger jumps between generated frames in an order that does not match the source.

The reasonable division: use the combinator vocabulary for the shape of a data transformation, where it genuinely beats a loop for both clarity and correctness; drop to a while loop with primitive locals in the handful of numeric inner loops where allocation and dispatch are measurably the problem; and profile before assuming which one you are in, because the uniform API hides the difference in both directions.