# Nested Parametric Types and Collections

**URL:** <https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777>\
**Category:** General Usage\
**Tags:** parametric-types\
**Created:** [June 14, 2022, 8:36pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777 "2022-06-14T20:36:56Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![bmit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bmit/32/12443_2.png) [@bmit](https://discourse.julialang.org/u/bmit)\
**Post date:** [June 14, 2022, 8:36pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/1 "2022-06-14T20:36:56Z")

</div>

I’m having trouble understand parametric types and mixing parameters in collections. For example,

```julia
struct Foo{T, S}
    a::T
    b::S
end

```

If I have this definition I can do the following:

```julia
a = Foo(1, 2)
b = Foo(1., 2)
c = Foo(1., 2.)

v = Foo[]
push!(v, a)
push!(v, b)
push!(v, c)

```

I know `v` is going to be filled with items of type `Foo`, but not the specific type parameters ahead of time. That’s okay, this works.

> 3-element Vector{Foo}:  
> Foo{Int64, Int64}(1, 2)  
> Foo{Float64, Int64}(1.0, 2)  
> Foo{Float64, Float64}(1.0, 2.0)

Now if I extend this with another wrapper type

```julia
struct Bar{T}
    a::T
end

```

The following fails and I’m unclear why

```julia
v = Bar{Foo}[]
push!(v, Bar(a))

```

> ERROR: MethodError: Cannot `convert` an object of type  
> Bar{Foo{Int64, Int64}} to an object of type  
> Bar{Foo}  
> Closest candidates are:  
> convert(::Type{T}, ::T) where T at /Applications/Julia-1.7.app/Contents/Resources/julia/share/julia/base/essentials.jl:218  
> Bar{T}(::Any) where T at REPL[11]:2

I’m not clear why the second fails and the first does not. Any tips on how to get this sort of pattern working?

---

<div class="post-metadata">

**Author:** ![JonasWickman](https://avatars.discourse-cdn.com/v4/letter/j/9de0a6/32.png) [@JonasWickman](https://discourse.julialang.org/u/JonasWickman)\
**Post date:** [June 14, 2022, 8:52pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/2 "2022-06-14T20:52:33Z")

</div>

I’m not good enough at Julia to tell whether this is a good idea but defining

```julia
v = Bar{<:Foo}[]
push!(v,Bar(a))

```

does work. The `<:`denotes that the type parameter for Bar should subtype Foo

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [June 14, 2022, 9:43pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/3 "2022-06-14T21:43:29Z")

</div>

> [@bmit](#):
>
> That’s okay, this works

Note that in both cases the resulting vector is a container associated to abstract types, and that can be detrimental for performance.

---

<div class="post-metadata">

**Author:** ![bmit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bmit/32/12443_2.png) [@bmit](https://discourse.julialang.org/u/bmit)\
**Post date:** [June 15, 2022, 12:48am UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/4 "2022-06-15T00:48:23Z")

</div>

Is the performance detriment because the length of the vector and the type doesn’t tell you number of bits?

In general, is there a “best way” to approach this problem? Specifically, having a collection different types and dispatching on each element individually?

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [June 15, 2022, 2:07am UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/5 "2022-06-15T02:07:17Z")

</div>

> [@bmit](#):
>
> ERROR: MethodError: Cannot `convert` an object of type  
> Bar{Foo{Int64, Int64}} to an object of type  
> Bar{Foo}

Although the concrete type `Foo{Int64, Int64}` is subtype of the parametric type `Foo`, the concrete type `Bar{Foo{Int64, Int64}}` is not a subtype of the concrete type `Bar{Foo}`. Look up “even though `Float64 <: Real` we **DO NOT** have `Point{Float64} <: Point{Real}`” in the [docs](https://docs.julialang.org/en/v1/manual/types/#man-parametric-composite-types).

`Bar{<:Foo}` is syntactic sugar for `Bar{T} where T<:Foo`, and `Bar{Foo{Int64, Int64}}` is very much a subtype of that.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [June 15, 2022, 2:27am UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/6 "2022-06-15T02:27:07Z")

</div>

> [@bmit](#):
>
> Is the performance detriment because the length of the vector and the type doesn’t tell you number of bits?

You’re on the right track, it’s related to why I specified “concrete type `Bar{Foo}`”. Let’s use `Vector{T}` as an example, 1-dimensional arrays are familiar.

When `T` is concrete (and `isbits`) e.g. `Vector{Int64}`, each element has a known layout and size (`Int64` is 8 bytes), so the array’s elements can be laid next to each other in 1 contiguous block of memory. This makes linear memory accesses efficient and can enable SIMD to save time (simultaneous operations on multiple elements).

When `T` is abstract e.g. `Vector{Real}`. each element can be any subtype of `Real`, so the size is unfixed. An array’s O(1)-indexing really relies on each element’s size being the same, so _pointers_ are laid next to each other in 1 contiguous block. Each pointer specifies the memory address of a separately allocated instance. Because the array’s data is scattered all over the memory, access and calculations need to spend more time doing more work.

Note that each `Vector{Int64}` and `Vector{Real}` have specific implementations, and these implementations are different. In other words, they are both _concrete_ types, and concrete types cannot subtype each other, even if their parameters do (`Int64<:Real`). They are both subtypes of the iterated union type `Vector{T} where T<:Real`. You can probably draw the parallels to your `Foo{Int64, Int64}`, `Foo`, `Bar{Foo{Int64, Int64}}`, and `Bar{Foo}`.

---

<div class="post-metadata">

**Author:** ![bmit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bmit/32/12443_2.png) [@bmit](https://discourse.julialang.org/u/bmit)\
**Post date:** [June 15, 2022, 2:17pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/7 "2022-06-15T14:17:26Z")

</div>

This is incredibly helpful. Thank you for taking the time. A few followup questions as I digest this.

I understand that O(1) indexing doesn’t work if element sizes aren’t the same. Is there also a penalty for iteration?

The use case I’m grappling with is something like the following:

I have a collection of data of different types - let’s say it’s different subtypes of `AbstractMatrix` - `Diagonal`, `Sparse`, etc. At run time I don’t know how many of each to expect, however I have specialized methods that efficiently process each subtype. I then iterate over the collection dispatching to the correct method for each element.

It seems like a trade between the performance penalty of having a collection of a Abstract Type and the benefit of having specialized methods. I could promote each type, but there’s a penalty in the promotion and also the extra processing from losing specialized methods. Is there another approach I’m missing that avoids this trade?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [June 15, 2022, 2:34pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/8 "2022-06-15T14:34:20Z")

</div>

If the time to process each Matrix dominates, you should not worry.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [June 15, 2022, 6:48pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/9 "2022-06-15T18:48:15Z")

</div>

> [@bmit](#):
>
> I understand that O(1) indexing doesn’t work if element sizes aren’t the same. Is there also a penalty for iteration?

Maybe this wasn’t made clear, but `Vector{Real}` _does_ have O(1) indexing because it has a contiguous block of pointers of a fixed size, even if the actual instance of an element is allocated elsewhere and can be any size.

AFAIK, iteration is generally easier to implement as O(1). Think of linked lists where each scattered element is attached to a pointer to the next element, accessing that pointer is O(1). With arrays, you move a fixed number of bytes to the next element, and sometimes the element is implemented as a pointer you access to get the actual instance; that’s also O(1).

Indexing is harder, and it’s easy to see why. What happens when you’re currently on index 1 of a linked list and you want index 8? You have to access the pointer to index 2, then the one to index 3, then to index 4, etc. The amount of work you need to do depends on where you started, that’s not O(1). If you want to access the index (3,1,2) of a multidimensional array, based on the dimensions you know that you need move N bytes 2 times, M bytes 1 time, and L bytes 3 times, or `move(a, b, c) = N*a + M*b + L*c`. You do the same calculation for any index, so it’s O(1).

---

<div class="post-metadata">

**Author:** ![bmit](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bmit/32/12443_2.png) [@bmit](https://discourse.julialang.org/u/bmit)\
**Post date:** [June 16, 2022, 5:25pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/10 "2022-06-16T17:25:40Z")

</div>

> [@Benny](#):
>
> Maybe this wasn’t made clear, but `Vector{Real}` _does_ have O(1) indexing because it has a contiguous block of pointers of a fixed size, even if the actual instance of an element is allocated elsewhere and can be any size.

All this makes sense in theory - I’m usually confused with how it works under the hood in Julia. For example, where does the logic of `Vector{X}` being an continuous block of pointers with O(1) indexing break down? Perhaps naively, it seems like my original example of `v = Bar{<:Foo}[]` might also be implemented as contiguous pointers vs a linked list? How would I test this? Or are there general rules to learn for Julia?

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [June 16, 2022, 6:49pm UTC](https://discourse.julialang.org/t/nested-parametric-types-and-collections/82777/11 "2022-06-16T18:49:44Z")

</div>

`Core.Array` is a subtype of `Core.DenseArray`, which is [documented](https://docs.julialang.org/en/v1/base/arrays/#Core.DenseArray) to have contiguous elements in memory, so you can absolutely count on that. It’s unusual for implementation details to be documented or ingrained in the type system because it locks the language into something, but this is just how multidimensional arrays are implemented across many languages for decades.  
Pointers implementing fields and elements restricted by abstract types is also documented in the “Parametric Composite Types” section I linked earlier. It doesn’t always happen though, there _is_ an optimization for a kind of abstract type: [isbits Unions](https://docs.julialang.org/en/v1/devdocs/isbitsunionarrays/) (implied \<= 256 isbits types). This being documented in the _devdocs_ makes it apparent this is the more typical internal implementation detail you’re not supposed to control or count on. I’m pretty sure the `@code_llvm` of indexing an array can reveal if this is happening, but I’ve never been able to read assembly.