About mapping functions and a deepmap!() function

I was thinking about how to apply a function f() to all items of a collections

I knew that my function needed:

  • first to reach every items in my collection
  • second apply the function f to those items

I decide to solve the first with recursion.

After some coding and reading in abstractarray.jl , iterators.jl , broadcast.jl.

I came to realize that the “items” in questions where simply Type and that my function can use Julia dispatch to exit the recursive loop.

This solve the second part in a rather beautiful way : myfunction(f,T::Type) = f(T)

I came up with:

deepmap!(f,n::Number) = f(n)
deepmap!(f,s::AbstractString) = f(s)
deepmap!(f,c::AbstractChar) = f(c)
deepmap!(f,a::AbstractArray) = collect(a[i] = deepmap!(f,a[i]) for i in eachindex(a))

Now I have 2 questions:

  1. Is there any obvious way to extent this deepmap! function to accept a Int i?
deepmap!(f,a::AbstractArray,i::Int)

where i is the depth level you wanna stop the recursion.

  1. Is it possible to extent this deepmap! function to accept a Type T?
deepmap!(f,a::AbstractArray,i::Int,T::DataType)

where T is use to define a function deepmap!(f,A::T) = f(A) at compile time or something
so the deepmap!() function will stop the recursion on that type T and apply f on those Types T items.

This would allow very powerful coding in my opinion.
like defining a custom type and applying a function f() to all items of this type inside whatever Iterable Collections you have .

On a side note I believe that the broadcast!() function should have its own symbol for the broadcast!(f, A, A) case e.g:dest=A
Exactly like the f.(x) for broadcast()
for example the symbol °
So that f°(x) or °|> can be use to do stuff “in-place” inside AbstractArrays.

ps: I know that all commune symbols are already taken and that !. or .! is not possible.

Peoples more advance than me could probably modify Julia to make it create all the functions:

deepmap!(f,A::Type1) = f(A)
deepmap!(f,A::Type2) = f(A)
....

for all Type TypeN for witch the function f is define and thus make sure to always be types stable while making it easy to program as well (you don’t need to define them by yourself).

I think that may already exist but I can’t remember where. But if it doesn’t, good idea!

[Edit: it does in fact mutate,I’m just blind]
[[quote=“rapasite, post:1, topic:51702”]
deepmap!
[/quote]

Since you collect over all containers, non of this is mutating, so it should be deepmap without the exclamation mark :slight_smile:]

While this does work, I think a more generic approach would be:

deepmap(f, arg) = f(arg)
deepmap(f, a::AbstractArray) = collect(a[i] = deepmap(f,a[i]) for i in eachindex(a))

# for comparison: your your manually specialized approach
your_deepmap!(f,n::Number) = f(n)
your_deepmap!(f,s::AbstractString) = f(s)
your_deepmap!(f,c::AbstractChar) = f(c)
your_deepmap!(f,a::AbstractArray) = collect(a[i] = your_deepmap!(f,a[i]) for i in eachindex(a))

which is equivalent in performance, since Julia specializes the generic deepmap(f, arg) = f(arg) for each argument type. This also helps with the definition of custom behaviour, since any narrowly typed method overwrites the generic version. Performance:

julia> @benchmark deepmap(x->(x*2), A) setup = A = [ [rand(Int) for _ in 1:rand(10:20)] for _ in 1:rand(10:20)]
BenchmarkTools.Trial: 
  memory estimate:  1.95 KiB
  allocs estimate:  12
  --------------
  minimum time:     413.573 ns (0.00% GC)
  median time:      734.671 ns (0.00% GC)
  mean time:        837.348 ns (9.61% GC)
  maximum time:     9.399 μs (84.81% GC)
  --------------
  samples:          10000
  evals/sample:     199

julia> @benchmark your_deepmap!(x->(x*2), A) setup = A = [ [rand(Int) for _ in 1:rand(10:20)] for _ in 1:rand(10:20)]
BenchmarkTools.Trial: 
  memory estimate:  1.86 KiB
  allocs estimate:  12
  --------------
  minimum time:     408.035 ns (0.00% GC)
  median time:      736.688 ns (0.00% GC)
  mean time:        833.854 ns (9.28% GC)
  maximum time:     8.549 μs (82.08% GC)
  --------------
  samples:          10000
  evals/sample:     199

# and for containers with mixed types (reduced input array)

julia> @benchmark deepmap(x->(x*2), A) setup = A = [ [rand(Bool) ? rand(Int) : rand(Float64) for _ in 1:rand(5:6)] for _ in 1:rand(5:6)]
BenchmarkTools.Trial: 
  memory estimate:  2.08 KiB
  allocs estimate:  59
  --------------
  minimum time:     3.300 μs (0.00% GC)
  median time:      4.537 μs (0.00% GC)
  mean time:        5.049 μs (3.00% GC)
  maximum time:     300.137 μs (95.68% GC)
  --------------
  samples:          10000
  evals/sample:     8

julia> @benchmark your_deepmap!(x->(x*2), A) setup = A = [ [rand(Bool) ? rand(Int) : rand(Float64) for _ in 1:rand(5:6)] for _ in 1:rand(5:6)]
BenchmarkTools.Trial: 
  memory estimate:  2.08 KiB
  allocs estimate:  59
  --------------
  minimum time:     3.250 μs (0.00% GC)
  median time:      4.475 μs (0.00% GC)
  mean time:        4.939 μs (3.06% GC)
  maximum time:     282.850 μs (96.25% GC)
  --------------
  samples:          10000
  evals/sample:     8

Yes, I’d add a reverse counting integer argument which stops recursion once it reaches zero:

julia> deepmap(f, arg, ::Int) = f(arg)
deepmap (generic function with 1 method)

julia> deepmap(f, a::AbstractArray, depth::Int) = depth===0 ? a : collect(a[i] = deepmap(f, a[i], depth-1) for i in eachindex(a)) #optionally add a default value
deepmap (generic function with 2 methods)

# for testing:

julia> gentower(depth, counter = 1) = return (depth==counter ? Any[counter,]  : Any[counter, gentower(depth, counter+1) ,counter]) # any to be able to change types, not necessary
gentower (generic function with 2 methods)

julia> print(gentower(8))
Any[1, Any[2, Any[3, Any[4, Any[5, Any[6, Any[7, Any[8], 7], 6], 5], 4], 3], 2], 1]

which does:

julia> deepmap(x->(string(x)), gentower(5), 5)
3-element Array{Any,1}:
 "1"
 Any["2", Any["3", Any["4", ["5"], "4"], "3"], "2"]
 "1"

julia> deepmap(x->(string(x)), gentower(5), 4)
3-element Array{Any,1}:
 "1"
 Any["2", Any["3", Any["4", Any[5], "4"], "3"], "2"]
 "1"

julia> deepmap(x->(string(x)), gentower(5), 3)
3-element Array{Any,1}:
 "1"
 Any["2", Any["3", Any[4, Any[5], 4], "3"], "2"]
 "1"

julia> deepmap(x->(string(x)), gentower(5), 2)
3-element Array{Any,1}:
 "1"
 Any["2", Any[3, Any[4, Any[5], 4], 3], "2"]
 "1"

julia> deepmap(x->(string(x)), gentower(5), 1)
3-element Array{Any,1}:
 "1"
 Any[2, Any[3, Any[4, Any[5], 4], 3], 2]
 "1"

julia> deepmap(x->(string(x)), gentower(5), 0)
3-element Array{Any,1}:
 1
  Any[2, Any[3, Any[4, Any[5], 4], 3], 2]
 1

But it’s efficiency is questionable, I think there are more clever ways to do that:

julia> @benchmark deepmap(x->(string(x)), A, 5) setup = A = gentower(10)
BenchmarkTools.Trial: 
  memory estimate:  1.90 KiB
  allocs estimate:  39
  --------------
  minimum time:     2.744 μs (0.00% GC)
  median time:      2.900 μs (0.00% GC)
  mean time:        3.349 μs (3.56% GC)
  maximum time:     317.833 μs (97.66% GC)
  --------------
  samples:          10000
  evals/sample:     9

[rest follows in a separate post]

Should be doable, let’s see:

struct MyNonrecursingArray{T,D} <: AbstractArray{T,D}
    a::Array{T,D}
end

# Implement basics of array interface
Base.size(my::MyNonrecursingArray) = Base.size(my.a)
Base.getindex(my::MyNonrecursingArray, i::Int) = Base.getindex(my.a, i)
Base.getindex(my::MyNonrecursingArray, I::Vararg{Int, N}) where {N} = Base.getindex(my.a, I...)

# and define that recursion shall stop at that type:
deepmap(f, my::MyNonrecursingArray, depth::Int) = my

which seems to work:

julia> tower = gentower(10);

julia> tower[2][2][2][2][2] = MyNonrecursingArray(tower[2][2][2][2][2])
3-element MyNonrecursingArray{Any,1}:
 6
  Any[7, Any[8, Any[9, Any[10], 9], 8], 7]
 6

julia> print(tower)
Any[1, Any[2, Any[3, Any[4, Any[5, Any[6, Any[7, Any[8, Any[9, Any[10], 9], 8], 7], 6], 5], 4], 3], 2], 1]
# although it's not visible, the Any[6, [...], 6] thing is a MyNonrecursingArray now

julia> deepmap(x->(string(x)), tower, 10)
3-element Array{Any,1}:
 "1"
 Any["2", Any["3", Any["4", Any["5", Any[6, Any[7, Any[8, Any[9, Any[10], 9], 8], 7], 6], "5"], "4"], "3"], "2"]
 "1"
# and it does stop at exactly this level

you may want to wrap that in a macro like @deepmap_stoprecursion MyNonrecursingArray but my macro-fu is pretty weak :smiley:

I don’t think it’s getting more type stable by manually specializing on all the types, but I’m not sure. Also, efficiency is not really my strong game, so we may wait for somebody to make this faster and more elegant together ^^

1 Like

Check out GitHub - JuliaCollections/AbstractTrees.jl: Abstract julia interfaces for working with trees for this sort of thing.

5 Likes