# Static lists in Julia

This post explores the possibility to build static lists in Julia, meaning lists for which the size is known at compile-time. This is inspired by a post on a Scala equivalent but will take different roads to see more than a plain port. Of course, this implementation is not that handy nor efficient but is mostly meant to push the limits of the type system, especially a trick of using recursive types as values (replacing a dependent type system). Some other references:

- The list operations are inspired by the implementation in
*DataStructures.jl* *StaticArrays.jl*is a good inspiration for static data structures in Julia

## Table of Contents

# First thoughts: value type parameter

Julia allows developers to define type parameters. In the case of a list, the most obvious one may be the type of data it contains:

`abstract type MyList{T} end`

Some types are however parametrized on other things, if we look at the
definition of `AbstractArray`

for example:

`AbstractArray{T,N}`

Supertype for N-dimensional arrays (or array-like types) with elements of type T.

The two type parameters are another type `T`

and integer `N`

for the
dimensionality (tensor rank). The only constraint for a value to be
an acceptable type parameter is to be composed of plain bits, complying
with `isbitstype`

.

This looks great, we could define our StaticList directly using integers.

```
"""
A static list of type `T` and length `L`
"""
abstract type StaticList{T,L} end
struct Nil{T} <: StaticList{T,0} end
StaticList{T}() where T = Nil{T}()
StaticList(v::T) where T = Cons(v, Nil{T}())
struct Cons{T,L} <: StaticList{T,L+1}
h::T
t::StaticList{T,L}
function Cons(v::T, t::StaticList{T,L}) where {T,L}
new{T,L}(v,t)
end
end
# Usage:
# Cons(3, Nil{Int}()) is of type StaticList{Int,1}
# Cons(4, Cons(3, Nil{Int}())) is of type StaticList{Int,2}
```

If you try to evaluate this code, you will get an error:

`ERROR: MethodError: no method matching +(::TypeVar, ::Int64)`

Pretty explicit, you cannot perform any computation on values used as type parameters. With more complex operations, this could make the compiler hang, crash or at least perform poorly (we would be forcing the compiler to execute this code at compile-time).

One way there might be around this is macros or replacing sub-typing with another mechanism. For the macro-based approach, ComputedFieldTypes.jl does exactly that. More discussion on computed type parameters in [1] and [2].

**Edit**: using integer type parameters can be achieved using *ComputedFieldTypes.jl* as such:

```
julia> using ComputedFieldTypes
julia> abstract type StaticList{T,L} end
julia> struct Nil{T} <: StaticList{T,0} end
julia> @computed struct Cons{T,L} <: StaticList{T,L}
h::T
t::StaticList{T,L-1}
function Cons(v::T, t::StaticList{T,L0}) where {T,L0}
L = L0+1
new{T,L}(v,t)
end
end
julia> Cons(3, Nil{Int}())
Cons{Int64,1,0}(3, Nil{Int64}())
julia> Cons(4, Cons(3, Nil{Int}()))
Cons{Int64,2,1}(4, Cons{Int64,1,0}(3, Nil{Int64}()))
```

This might be the neatest option for building the `StaticList`

.

# Recursive natural numbers

We can use the same technique as in the Scala post, representing natural number using recursive types.

`ZeroLength`

is a special singleton type`Next{L}`

represents the number following the one represented by`L`

We can modify our previous example:

```
"""
A type parameter for List length, the numerical length can be retrieved
using `length(l::Length)`
"""
abstract type Length end
struct ZeroLength <: Length end
struct Next{L<:Length} <: Length end
"""
A linked list of size known at compile-time
"""
abstract type StaticList{T,L<:Length} end
struct Nil{T} <: StaticList{T,ZeroLength} end
StaticList{T}() where T = Nil{T}()
StaticList(v::T) where T = Cons(v, Nil{T}())
struct Cons{T,L<:Length} <: StaticList{T,Next{L}}
h::T
t::StaticList{T,L}
function Cons(v::T, t::StaticList{T,L}) where {T,L<:Length}
new{T,L}(v,t)
end
end
"""
By default, the type of the Nil is ignored if different
from the type of first value
"""
Cons(v::T,::Type{Nil{T1}}) where {T,T1} = Cons(v, Nil{T}())
```

We can then define basic information for a list, its length:

```
Base.length(::Type{ZeroLength}) = 0
Base.length(::Type{Next{L}}) where {L} = 1 + length(L)
Base.eltype(::StaticList{T,L}) where {T,L} = T
Base.length(l::StaticList{T,L}) where {T,L} = length(L)
```

One thing should catch your attention in this block,
we use a recursive definition of `length`

for the `Length`

type,
which means we can blow our compiler. However, both of the definitions
are static, in the sense that they don’t use type information, so
the final call should reduce to spitting out the length cached at compile-time.
You can confirm this is the case by checking the produced assembly instructions with `@code_native`

.
We respected our contract of a list with size known at compile-time.

# Implementing a list-y behaviour

This part is heavily inspired by the *DataStructures.jl* list implementation,
as such we will not re-define methods with semantically similar but
implement them for our list type. Doing so for your own package
allows user to switch implementation for the same generic code.

The first operation is being able to join a head with an existing list:

```
DataStructures.cons(v::T,l::StaticList{T,L}) where {T,L} = Cons(v,l)
"""
Allows for `cons(v,Nil)`. Note that the `Nil` type is ignored.
"""
DataStructures.cons(v::T,::Type{Nil}) where {T} = StaticList(v)
(::Colon)(v::T,l::StaticList{T,L}) where {T,L} = DataStructures.cons(v, l)
(::Colon)(v::T,::Type{Nil}) where {T,L} = DataStructures.cons(v, Nil{T})
```

Implementing the odd `::Colon`

methods allows for a very neat syntax:

```
l0 = StaticList{Int}()
l1 = 1:l0
l2 = 2:l1
```

Unlike the Scala post, we are not using the `::`

operator which
is reserved for typing expressions in Julia.
We can add a basic head and tail methods, which allow querying
list elements without touching the inner structure. This
will be useful later on.

```
DataStructures.head(l::Cons{T,L}) where {T,L} = l.h
DataStructures.tail(l::Cons{T,L}) where {T,L} = l.t
```

Testing list equality can be done recursively, dispatching on the three possible cases:

```
==(l1::StaticList, l2::StaticList) = false
function ==(l1::L1,l2::L2) where {T1,L,T2,L1<:Cons{T1,L},L2<:Cons{T2,L}}
l1.h == l2.h && l1.t == l2.t
end
"""
Two `Nil` are always considered equal, no matter the type
"""
==(::Nil,::Nil) = true
```

We can now define basic higher-order functions, such as `zip`

below,
and implement the iteration interface.

```
function Base.zip(l1::Nil{T1},l2::StaticList{T2,L2}) where {T1,T2,L2}
Nil{Tuple{T1,T2}}
end
function Base.zip(l1::Cons{T1,L1},l2::Cons{T2,L2}) where {T1,L1,T2,L2}
v = (l1.h, l2.h)
Cons(v,zip(l1.t,l2.t))
end
Base.iterate(l::StaticList, ::Nil) = nothing
function Base.iterate(l::StaticList, state::Cons = l)
(state.h, state.t)
end
```

Iterating over our lists is fairly straight-forward, and will be more efficient than the recursive implementations of the higher-order functions, we still kept it for equality checking, more a matter of keeping a functional style in line with the Scala post.

The case of list reversal is fairly straightforward: iterate and accumulate the list in a new one.

```
function Base.reverse(l::StaticList{T,L}) where {T,L}
l2 = Nil{T}
for h in l
l2 = Cons(h, l2)
end
l2
end
```

We define the cat operation between multiple lists.

```
function Base.cat(l1::StaticList{T,L},l2::StaticList{T,L}) where {T,L}
l = l2
for e in reverse(l1)
l = Cons(e, l)
end
l
end
```

The reverse is necessary to keep the order of the two lists.

# Special-valued lists

Now that we have a basic static list implementation, we can spice things up.
`StaticList`

is just an abstract type in our case, not an algebraic data type
as in common functional implementations, meaning we can define other sub-types.

Imagine a numeric list, with a series of zeros or ones somewhere. Instead of storing all of them, we can find a smart way of representing them. Let us define a static list of ones:

```
struct OnesStaticList{T<:Number,L<:Length} end
Base.iterate(l::OnesStaticList, ::Type{ZeroLength}) = nothing
function Base.iterate(l::OnesStaticList{T,L}, state::Type{Next{L1}} = L) where $
(one(T), L1)
end
```

This list corresponds to the 1 value of type `T`

, repeated for all elements.
In a similar fashion, one can define a ZeroList:

```
struct ZerosStaticList{T<:Number,L<:Length} end
Base.iterate(l::ZerosStaticList, ::Type{ZeroLength}) = nothing
function Base.iterate(l::ZerosStaticList{T,L}, state::Type{Next{L1}} = L) where$
(zero(T), L1)
end
```

One thing to note is that these lists are terminal, in the sense that they cannot be part of a greater list. To fix this, we can add a tail to these as follows:

```
struct ZerosStaticList{T<:Number,L<:Length,TL<:StaticList{T,<:Length}}
t::TL
end
Base.iterate(l::ZerosStaticList, ::Type{ZeroLength}) = l.t
function Base.iterate(l::ZerosStaticList{T,L}, state::Type{Next{L1}} = L) where$
(zero(T), L1)
end
```

The `t`

field of the list contains the tail after the series of zeros,
we can thus build a much simpler representation in case of long constant series.
In a similar fashion, one could define a constant list of `N`

elements, storing
the value just once.

# Multi-typed lists

There is one last extension we can think of with this data structure. Since we have a recursive length parameter, why not add it a type at each new node?

```
abstract type TLength end
struct TZeroLength <: TLength end
struct TNext{T,L<:TLength} <: TLength end
abstract type TStaticList{L<:TLength} end
struct TNil <: TStaticList{TZeroLength} end
struct TCons{T, L<:TLength} <: TStaticList{TNext{T,L}}
h::T
t::TStaticList{L}
function TCons(v::T, t::TStaticList{L}) where {T,L<:TLength}
new{T,L}(v,t)
end
end
```

With such construct, all nodes can be of a different type `T`

, without
removing the type information from the compiler.

```
julia> TCons(3,TNil())
TCons{Int64,TZeroLength}(3, TNil())
julia> TCons("ha", TCons(3,TNil()))
TCons{String,TNext{Int64,TZeroLength}}("ha", TCons{Int64,TZeroLength}(3, TNil()))
```

One interesting thing to note here is that the type takes the same structure as the list itself:

**Type**: either a `T`

and a `TLength`

containing the rest of the type, or `TNil`

**Data**: either a value of a given type and the rest of the list, or empty list

# Conclusion

The Julia type system and compiler allow for sophisticated specifications when designing data structures, which gives it a feel of compiled languages. This however should not be abused, in our little toy example, the type parameter grows in complexity as the list does, which means the compiler has to carry out some computation.

If you want some further compile-time tricks, Andy Ferris’s workshop at JuliaCon 2018 details how to perform compile-time computations between bits and then bytes.

If you have any idea how to implement `StaticList`

using integer parameters instead
of custom struct I would be glad to exchange. Porting this to
use ComputedFieldTypes.jl might be a fun
experiment.

Feel free to reach out any way you prefer, Twitter, email to exchange or discuss this post.

# Sources

Header image source: https://pxhere.com/en/photo/742575

[1] A proposal on Julia “Defer calculation of field types until type parameters are known”, julia/issues/18466

[2] Discussion on compile-time computations on Discourse