Kan Extensions

Universal aggregation (Σ) and completion (Δ)

Author

Simon Frost

Introduction

Kan extensions are often called “the most universal construction in category theory.” In FunctorFlow, they serve as the foundational operation for two dual patterns:

  • Left Kan extension (Σ) = universal aggregation. It pushes forward values along a relation and reduces them. This single abstraction subsumes attention, pooling, message passing, and context fusion.
  • Right Kan extension (Δ) = universal completion. It fills in missing or partial values along a compatibility relation. This covers denoising, repair, and reconciliation.

FunctorFlow uses the mathematical symbols Σ and Δ for these operations, following the convention from algebraic Julia packages like CategoricalProjectionModels.jl where left and right Kan extensions are denoted as sigma and delta pushforwards.

Both patterns take a source value, a relation (the “along” functor), and a reducer that determines how grouped values are combined.

Setup

using FunctorFlow

Left Kan (Σ): Universal Aggregation

A left Kan extension groups source values by a relation and reduces each group. Consider a set of node values and an incidence relation defining neighborhoods:

D = Diagram(:LeftKanDemo)
add_object!(D, :Values; kind=:messages)
add_object!(D, :Incidence; kind=:relation)
Σ(D, :Values; along=:Incidence, reducer=:sum, name=:aggregate)

compiled = compile_to_callable(D)

values = Dict(:a => 1, :b => 2, :c => 3, :d => 4)
incidence = Dict(:x => [:a, :b], :y => [:b, :c, :d], :z => [:a])

result = FunctorFlow.run(compiled, Dict(:Values => values, :Incidence => incidence))
println("Sum aggregation: ", result.values[:aggregate])
Sum aggregation: Dict(:y => 9, :z => 1, :x => 3)

Target :x receives 1 + 2 = 3, target :y receives 2 + 3 + 4 = 9, and target :z receives 1.

This is the same pattern as:

  • Attention: values are value vectors, relation is the attention matrix
  • Pooling: values are features, relation groups features into pools
  • Message passing: values are node messages, relation is the adjacency

Right Kan (Δ): Universal Completion

A right Kan extension completes partial data using a compatibility relation. Where Σ aggregates many values into one, Δ fills in missing values from compatible sources.

D2 = Diagram(:RightKanDemo)
add_object!(D2, :PartialValues; kind=:partial)
add_object!(D2, :Compatibility; kind=:relation)
Δ(D2, :PartialValues; along=:Compatibility, name=:complete)

compiled2 = compile_to_callable(D2)

partial = Dict(:a => nothing, :b => 42, :c => nothing, :d => 99)
compat = Dict(:a => [:b, :c], :c => [:d, :a])

result2 = FunctorFlow.run(compiled2, Dict(:PartialValues => partial, :Compatibility => compat))
println("Completed: ", result2.values[:complete])
Completed: Dict{Any, Any}(:a => 42, :c => 99)

For target :a, the compatible sources are :b (42) and :c (nothing). The :first_non_null reducer returns 42. For :c, the compatible sources are :d (99) and :a (nothing), yielding 99.

Custom Reducers

You can write and bind custom reducers. A reducer is a function with the signature (source_values, relation, metadata) -> result, where source_values is a Dict of source key-value pairs, relation maps target keys to vectors of source keys, and the result is a Dict of target key-value pairs.

D3 = Diagram(:CustomReducer)
add_object!(D3, :Vals; kind=:messages)
add_object!(D3, :Rel; kind=:relation)
Σ(D3, :Vals; along=:Rel, reducer=:weighted_sum, name=:weighted_sum)

# Custom reducer: weighted sum where weight = position index
function my_weighted_sum(source_values, relation, metadata)
    relation_dict = FunctorFlow.normalize_relation(relation)
    result = Dict{Any, Any}()
    for (target, sources) in relation_dict
        total = 0.0
        for (i, src) in enumerate(sources)
            val = get(source_values, src, 0)
            total += i * val
        end
        result[target] = total
    end
    return result
end

bind_reducer!(D3, :weighted_sum, my_weighted_sum)

compiled3 = compile_to_callable(D3)
result3 = FunctorFlow.run(compiled3, Dict(
    :Vals => Dict(:a => 10, :b => 20),
    :Rel => Dict(:x => [:a, :b])
))
println("Weighted sum: ", result3.values[:weighted_sum])
Weighted sum: Dict{Any, Any}(:x => 50.0)

With weights [1, 2] and values [10, 20], the result is 1*10 + 2*20 = 50.

The Duality

Left and right Kan extensions are dual. Applied to the same data, they answer different questions:

  • Left Kan (Σ) (aggregation): “What is the combined value at each target?”
  • Right Kan (Δ) (completion): “What value should fill each missing slot?”
D_dual = Diagram(:Duality)
add_object!(D_dual, :Data; kind=:messages)
add_object!(D_dual, :Relation; kind=:relation)

Σ(D_dual, :Data; along=:Relation, reducer=:sum, name=:aggregated)
Δ(D_dual, :Data; along=:Relation, name=:completed)

compiled_dual = compile_to_callable(D_dual)

data = Dict(:a => 10, :b => nothing, :c => 30)
rel = Dict(:x => [:a, :b], :y => [:b, :c])

result_dual = FunctorFlow.run(compiled_dual, Dict(:Data => data, :Relation => rel))
println("Left Kan Σ (sum): ", result_dual.values[:aggregated])
println("Right Kan Δ (first_non_null): ", result_dual.values[:completed])
Left Kan Σ (sum): Dict(:y => 30, :x => 10)
Right Kan Δ (first_non_null): Dict{Any, Any}(:y => 30, :x => 10)

The Σ operator sums available values per target group, while Δ fills in missing values from compatible neighbors. Together, they form the predict-and-repair duality at the heart of FunctorFlow’s architectural patterns.