The Power of Function Composition - Conor Hoekstra - NDC Oslo 2024

Function composition extends beyond the simple combination of two unary functions - there are multiple composition strategies including operators, functions, trains, chains, and stacks

Pure functions, combinators, and function-only functions (FOF) are related but distinct concepts:

• Pure functions: Same input always produces same output, no side effects
• Combinators: Functions that deal only in their arguments
• FOF: Functions that take only functions as arguments and return functions

Array languages (APL, BQN, J, CAP) offer powerful function composition through:

• Trains: Juxtaposition of functions creating composition patterns
• Ambivalent functions: Functions that can operate both unary and binary
• Built-in operators for common composition patterns

The SKI combinator calculus provides fundamental building blocks for function composition:

• S combinator: For applying binary operations
• K combinator (cancellator): Discards second argument
• I combinator (identity): Returns input unchanged

Different languages handle function composition through various means:

• Python: Functions and operator module
• Haskell: Extensive combinator support
• F#: Pipeline operators
• Stack languages: Implicit composition through stack operations

Knowing different composition strategies allows writing more elegant and maintainable code by:

• Reducing need for explicit loops and temporary variables
• Making code more declarative
• Enabling better pattern matching and optimization

Function composition patterns can be brought back to mainstream languages through libraries and custom implementations

Array languages demonstrate how limiting data structures to arrays while expanding function composition capabilities can lead to more expressive and performant code