Chaining array of functions

General Usage
1

Suppose I have a 1d array of functions:
f_array = [f1, f2, f3, f4]

This array can be of arbitrary length, and each function may have multiple inputs/outputs.

How do I do a reduce style operation to make a new function consisting of the composition of all previous functions: So an f satisfying
f(x) = f1 o f2 o f3 o f4(x)

Can’t work it out. Thanks!!!

1 Like
2 
f1(x) = x^1
f2(x) = x^2
f3(x) = x^3
f4(x) = x^4
f(x) = (f1∘f2∘f3∘f4)(x)
1 Like
3

You can do
reduce(∘, f_array)(x)

Note that functions in containers in Julia are not automatically very efficient, usually there is an expensive unboxing step that needs to take place.

Consider checking out FunctionWrappers.jl (fortunately this still works even on Julia 1.3).

3 Likes
4

You might want foldl() or foldr() instead of reduce, since reduce does not make any guarantees about its associativity.

It’s also worth noting that you actually get good performance using the chained function without needing to use FunctionWrappers or anything like it:

julia> f1(x) = x^1
f1 (generic function with 1 method)

julia> f2(x) = x^2
f2 (generic function with 1 method)

julia> f3(x) = x^3
f3 (generic function with 1 method)

julia> f4(x) = x^4
f4 (generic function with 1 method)

julia> f = foldl(∘, [f1, f2, f3, f4])
#58 (generic function with 1 method)

julia> using BenchmarkTools

julia> @btime $f($(1.0))
  21.348 ns (0 allocations: 0 bytes)
1.0

What’s happening here is that the return type of foldl itself cannot be inferred (because it depends on the non-concrete element types of [f1, f2, f3, f4], but the resulting function that it returns has no such limitations:

julia> @code_warntype foldl(∘, [f1, f2, f3, f4])
Variables
  #self#::Core.Compiler.Const(foldl, false)
  op::Core.Compiler.Const(∘, false)
  itr::Array{Function,1}

Body::Any
1 ─ %1 = Core.NamedTuple()::Core.Compiler.Const(NamedTuple(), false)
│   %2 = Base.pairs(%1)::Core.Compiler.Const(Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}(), false)
│   %3 = Base.:(#foldl#189)(%2, #self#, op, itr)::Any
└──      return %3

julia> @code_warntype f(1.0)
Variables
  #self#::Core.Compiler.Const(getfield(Base, Symbol("##58#59")){getfield(Base, Symbol("##58#59")){getfield(Base, Symbol("##58#59")){typeof(f1),typeof(f2)},typeof(f3)},typeof(f4)}(getfield(Base, Symbol("##58#59")){getfield(Base, Symbol("##58#59")){typeof(f1),typeof(f2)},typeof(f3)}(getfield(Base, Symbol("##58#59")){typeof(f1),typeof(f2)}(f1, f2), f3), f4), false)
  x::Tuple{Float64}

Body::Float64
1 ─ %1 = Core.getfield(#self#, :f)::Core.Compiler.Const(getfield(Base, Symbol("##58#59")){getfield(Base, Symbol("##58#59")){typeof(f1),typeof(f2)},typeof(f3)}(getfield(Base, Symbol("##58#59")){typeof(f1),typeof(f2)}(f1, f2), f3), false)
│   %2 = Core.getfield(#self#, :g)::Core.Compiler.Const(f4, false)
│   %3 = Core._apply(%2, x)::Float64
│   %4 = (%1)(%3)::Float64
└──      return %4
10 Likes
5

In Julia 1.4, you can use ∘(f_array...): https://docs.julialang.org/en/latest/base/base/#Base.:∘

As ∘ is associative, this doesn’t matter much. But I agree using foldl here is nicer.

Also, if you want to support arbitrary length array, including empty one, it’s important to specify init as in foldl(∘, f_array; init=identity).

3 Likes
6

Thanks a lot everybody, every single answer was really helpful.

I edited this post: somehow in my head I mixed associativity and commutativity and wrote something that would be confusing for readers based on that. Not great for a supposed mathematician, I’ll blame it on jetlag!

To correctly (this time) summarise the above: reduce() requires associativity of the operator it is reducing with respect to. Therefore it is OK for function composition, which is associative. foldl() and foldr() additionally work on non-associative operations, as they fix the order in which the computer carries the reduction.

Thanks again for the prompt, informative replies! I’m not someone who has really posted on forums of any kind much before, was pleasantly surprised :).

3 Likes
7

Aren’t you mixing associativity and commutativity? Note that reduce requires associativity but not commutativity. So reduce does give you the correct result for ∘.

2 Likes
8

Hi tkf,

Yes I was! Thanks. I actually was trying to say composition is not commutative but is associative, I got the words jumbled. I was actually misunderstanding the reduce() function, which I see operates on associative operations regardless of commutativity, and is therefore amenable to the composition operator.

Thanks :slight_smile: I’ll edit my previous post to reflect that

2 Likes
9

I have some examples of doing this in my package with what I call “pipelines”

Maybe it’ll help give you ideas.

1 Like
10

Perfect, it’s a superset of what I wanted to do. Thanks!

2 Likes
11

If you find any cool or better patterns please report back! I’d love to improve whats being done there. By the way that code is MIT licensed so do whatever you please with it.

2 Likes
12

Composition on a tuplet works as you suggest, but composition on an array does something else, am I understanding correctly?

composition on a tuplet:

julia> ∘(f1, f2, f3)
f1 ∘ f2 ∘ f3

composition on an array

julia> ∘([f1, f2, f3])
3-element Vector{Function}:
f1 (generic function with 1 method)
f2 (generic function with 1 method)
f3 (generic function with 1 method)

Thanks!

13

You want to splat here:

julia> ∘([f1, f2, f3]...)
f1 ∘ f2 ∘ f3

otherwise you’re only passing one argument (the array) to ∘

4 Likes
14

Oh of course, thanks a lot Nils!

1 Like