# Expand a Tuple at given positions, type stable dims

**URL:** <https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914>\
**Category:** Internals & Design\
**Tags:** question\
**Created:** [March 15, 2019, 2:27pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914 "2019-03-15T14:27:21Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 15, 2019, 2:27pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/1 "2019-03-15T14:27:21Z")

</div>

I would like to make a PR extending [#29749](https://github.com/JuliaLang/julia/pull/29749) by generalizing `eachslice` to generic dimensions.

I have two questions:

1. What’s the recommended API for specifying dimensions in a type stable way? Eg should I use a `Tuple` of `Val` indexes, as in `dims = (Val(1), Val(3))`?

2. Is there a good solution to inserting `Colon()` into a `CartesianIndex` at positions known at compile time (supposing there is an answer to the above questions).

For (2), I came up with a recursive solution (using tupes of numbers, and assuming insertion positions are ordered, also no error checking):

```julia

@inline _insert_colons(before, after) = (before..., after...) # done
@inline function _insert_colons(before, after, ::Val{1}, rest...)
    _insert_colons((before..., Colon()), after, rest...)
end
@inline _decr_index(::Val{T}) where T = Val{T-1}()
@inline function _insert_colons(before, after, rest...)
    _insert_colons((before..., first(after)), Base.tail(after), map(_decr_index, rest)...)
end

insert_colons(indexes, positions) = _insert_colons((), indexes, positions...)

@code_warntype insert_colons((1, 2, 3), (Val{1}(), Val{2}()))

```

but it compiles into a `PartialStruct`.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [March 15, 2019, 4:57pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/2 "2019-03-15T16:57:19Z")

</div>

Nice! I’m more than happy to provide a bit of feedback to help make this happen.

For point 1, the key is to lean on constant propagation instead of explicit `Val` usage. The key test cases, then, are going to be introspecting functions that call `eachslice` with a constant literal tuple. For example:

```julia
julia> f(;dims=()) = dims[1]+dims[2]+dims[3]
f (generic function with 1 method)

julia> g() = f(dims=(1,2,3))
g (generic function with 1 method)

julia> @code_llvm g()

; @ REPL[5]:1 within `g'
define i64 @julia_g_12214() {
top:
  ret i64 6
}

```

For this to work, you need to ensure that `f` inlines up to the point where you use `dims`. Now combining this with a more complicated algorithm (point 2) is gonna be tricky. Encoding these literal constants as quickly as possible into a typed tuple is probably going to be your best bet. Unfortunately the naive things with `ntuple` doesn’t quite do the trick:

```julia
julia> f(A;dims) = ntuple(i->i in dims ? (:) : 1, ndims(A))
f (generic function with 1 method)

julia> g(A) = f(A, dims=(2,3))
g (generic function with 1 method)

julia> @code_warntype g(rand(3,4,5))
Body::Tuple{Union{Colon, Int64},Colon,Union{Colon, Int64}}

```

It’s rather amazing how Julia is able to concretely identify the second element in that tuple, but it’s not quite able to follow `in` the whole way along all the checks in the tuple. Even more amazing is that this is all happening with the totally generic `in(x, itr)` definition. Ok, so perhaps that’s the key, let’s try adding some specialized `in` methods for small tuples:

```julia
julia> Base.in(x, ::Tuple{}) = false
       Base.in(x, t::Tuple{Any}) = x == t[1]
       Base.in(x, t::NTuple{2,Any}) = x == t[1] || x == t[2]
       Base.in(x, t::NTuple{3,Any}) = x == t[1] || x == t[2] || x == t[3]
       Base.in(x, t::NTuple{4,Any}) = x == t[1] || x in Base.tail(t)

julia> @code_warntype g(rand(3,4,5))
Body::Tuple{Int64,Colon,Colon}
# ...
11 ─ return (1, Colon(), Colon())

```

Now you can encode your constant literals into a `Tuple` of either `Int`s or `Colon`s… and then use that for your type-stable algorithm. To use this “template” tuple to replace an arbitrary tuple of indices, walk through them in sync:

```julia
replace_colons(template::Tuple{}, idxs::Tuple{}) = ()
replace_colons(template::Tuple{Int, Vararg{Any}}, idxs::Tuple{Any, Vararg{Any}}) = (idxs[1], replace_colons(tail(template), tail(idxs))...)
replace_colons(template::Tuple{Colon, Vararg{Any}}, idxs::Tuple{Any, Vararg{Any}}) = (:, replace_colons(tail(template), tail(idxs))...)

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 15, 2019, 5:10pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/3 "2019-03-15T17:10:51Z")

</div>

> [@mbauman](#):
>
> For point 1, the key is to lean on constant propagation instead of explicit `Val` usage.

Thanks for your help. Shoudn’t there be a `Val`-based or similar fallback interface though that does not rely on constant propagation? Then the caller could use the `dims = (1,2,3)` interface, have that propagate the constants, the rest of the code working in type space.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [March 15, 2019, 5:13pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/4 "2019-03-15T17:13:42Z")

</div>

> [@Tamas\_Papp](#):
>
> Shoudn’t there be a `Val` -based or similar fallback interface though that does not rely on constant propagation?

Why though? It’ll only be fast if folks use a literal constant like `Val(2)`. If they’re doing something dynamic with `Val(d)`, then it’ll be slow.

If we just get things working with constant literals in the first place, then it’ll be fast if folks just write the obvious constant literals. If they’re doing something dynamic, then it’ll be just as slow to construct the (type-unstable) template tuple as it would be to construct the (type-unstable) `Val`s.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [March 15, 2019, 5:23pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/5 "2019-03-15T17:23:14Z")

</div>

There’s one overarching rule in creating fast and type-inferable recursive tuple functions: each step in the recursion _must simplify the types of the arguments_. A great way to simplify arguments for tuples is by following the idiom of `f(t) = (op(t[1]), f(tail(t))...)`. Doing something like `_decr_index` isn’t simplifying the arguments in a way that they type system can reason about — `Val(1)` is exactly the same complexity as `Val(0)`. That’s why a template tuple here is nice — you can recursively step through it while simplifying the arguments and it occurs in a type-stable manner.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 15, 2019, 5:41pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/6 "2019-03-15T17:41:22Z")

</div>

> [@mbauman](#):
>
> each step in the recursion _must simplify the types of the arguments_

Thanks, that makes sense. I will make a PR over the weekend and link it here.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 16, 2019, 8:06am UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/7 "2019-03-16T08:06:43Z")

</div>

I must be missing something, because the way I think about this is making a subset of axes, walking that with a `CartesianIndices`, and putting back the `Colon()`s for `view`. If I do replacement like you suggested, I will get the same views multiple times.

Eg in `size(A) == (2, 3)` along `dims = (1, )`, I would want `view(A, :, 1)`, `view(A, :, 2)`, `view(A, :, 3)`. But replacing the colons in the elements of `CartesianIndices(axes(A))` will still give me 6 views. What am I missing from your suggestion?

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [March 18, 2019, 8:41pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/8 "2019-03-18T20:41:12Z")

</div>

Yeah, it’s a little tricky, especially since you’re just building up an iterator itself. You’ll just want to build the CartesianIndices of the dimensions _not_ in `dims` and then instead of replacing certain dimensions with a `:` you just _insert_ the colon at the appropriate place.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [March 18, 2019, 9:10pm UTC](https://discourse.julialang.org/t/expand-a-tuple-at-given-positions-type-stable-dims/21914/9 "2019-03-18T21:10:56Z")

</div>

This would be great to have. Maybe this is obvious, but a pattern I found useful for such things is this: `collect(Iterators.product(axes(B,1), Ref(:), axes(B,3)))`. No CartesianIndices, but I’m not sure how you would feed those to `view()` anyway.