Higher-order functions as their own expression and array kind - #10696

Summary

An alternative design to #10502 and #10503, for comparison. It has the same features (variables, lambdas and list_transform), but a higher-order function is its own kind of node in expressions and arrays, holding its lambdas next to its children, instead of a scalar function that keeps its lambda in its options.

It's a draft to decide between the two designs, not meant to merge as is.

Changes

• Variables and lambdas, as in Add lambdas and variables for higher-order scalar functions #10502:

  • var("x") builds Expression::Variable, which displays as @x.
  • Lambda { params, body } is the written form. Lambda::bind rewrites each @x to $.x and binds the body to a struct of the parameters, giving a BoundLambda.
  • BoundLambda::evaluate runs it over parameter arrays.

• HigherOrderFnVTable, in a new higher_order_fn module:

  • a function that takes values and lambdas;
  • it binds its own lambdas against its value children's dtypes (bind_lambdas), in whatever order it needs;
  • it decides when they run (execute receives the bound lambdas).

  HigherOrderFnRef is its type-erased handle.

• Expression::HigherOrder { function, children, lambdas } and BoundExpression::HigherOrder { …, lambdas, bound }. The bound node keeps its written lambdas, so it displays @x and rebinds them when a rewrite changes its children's dtypes.

• HigherOrderArray runs a bound node. It has slice and filter pushdown, so a lambda never runs on rows that aren't selected.

• list_transform(list, lambda) now lives in higher_order_fn::fns:

  • it accepts List input only, takes one parameter, and is strict;
  • it runs over an exact ListArray: null lists are emptied, then list_from_list_view makes the elements back to back;
  • the result keeps the input's offsets and validity.

• The new variants are handled in binding, return_dtype, apply, apply_bound, display, optimize, traversal, validity (strict functions only) and serialization (an error for now). ScalarFnVTable is unchanged.

Compared with #10502 and #10503

Six places assumed that a node which isn't a scalar function is the root or has no children, and compiled anyway:

• Traversal skipped the inside of higher-order nodes, so scanning a file with list_transform failed.
• The scan's field annotator marked the node as reading every field.
• apply_bound returned its input unchanged.
• Serialization wrote the node as $.
• apply panicked.
• Without slice and filter rules, a lambda that can fail errored on rows a filter had removed.

All six are fixed here.

Not done

• Dictionary pushdown for HigherOrderArray; an_infallible_transform_pushes_into_dictionary_values is ignored. The scan's own dictionary rule in vortex-layout doesn't know about the new node either.
• Reduce and simplify rules for higher-order nodes.
• Validity for functions that aren't strict.
• Serialization and a registry for the new function kind.

Testing

• cargo nextest run -p vortex-array -p vortex-layout -p vortex-file
• cargo clippy -p vortex-array -p vortex-layout --all-targets --all-features -- -D warnings
• cargo +nightly-2026-09-10 fmt -p vortex-array -p vortex-layout -p vortex-file --check
• cargo test --doc -p vortex-array -- lambda exprs::var list_transform higher_order
• RUSTDOCFLAGS="-D warnings --cfg docsrs" cargo doc --no-deps --document-private-items -p vortex-array -p vortex-layout --features vortex-array/_test-harness
• Also run locally but not included: the probes from the Add lambdas and variables for higher-order scalar functions #10502/Add list_transform #10503 review, about 1,500 lines covering file scans and 6,000 randomized list cases. They all pass after the fixes above.