# How to define a type that may be a vector of itself?

**URL:** <https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914>\
**Category:** New to Julia\
**Created:** [September 7, 2022, 9:26pm UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914 "2022-09-07T21:26:44Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![SodAlmighty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sodalmighty/32/42450_2.png) [@SodAlmighty](https://discourse.julialang.org/u/SodAlmighty)\
**Post date:** [September 7, 2022, 9:26pm UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/1 "2022-09-07T21:26:44Z")

</div>

How to define a type that may be a vector of itself?

```julia
const ListExpr = Vector{Union{ListExpr, Number, String}}

```

> ERROR: UndefVarError: ListExpr not defined

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [September 7, 2022, 10:02pm UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/2 "2022-09-07T22:02:19Z")

</div>

```julia
julia> struct ListExpr
           data::Vector{Union{ListExpr, Number, String}}
       end

julia> ListExpr([])
ListExpr(Union{Number, String, ListExpr}[])

julia> ListExpr([1, "foo"])
ListExpr(Union{Number, String, ListExpr}[1, "foo"])

```

Your `const` approach would define an _alias_, not a type. As such, what is written on the right hand side of the assignment has to exist independent of the left hand side.

---

<div class="post-metadata">

**Author:** ![SodAlmighty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sodalmighty/32/42450_2.png) [@SodAlmighty](https://discourse.julialang.org/u/SodAlmighty)\
**Post date:** [September 7, 2022, 10:13pm UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/3 "2022-09-07T22:13:44Z")

</div>

I see. But then the `ListExpr` instance wouldn’t _be_ a vector; it would _contain_ a vector field called `data`…

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [September 7, 2022, 10:19pm UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/4 "2022-09-07T22:19:58Z")

</div>

Indeed - if you want to use `ListExpr` like a vector, you can do

```julia
struct ListExpr <: AbstractVector
   ...
end

```

and implement the [array interface](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-array) appropriately, by forwarding to that field.

This is a somewhat advanced thing to do, so may I ask what you’re trying to achieve (trying to avoid an [XY-problem](https://en.wikipedia.org/wiki/XY_problem) here)?

---

<div class="post-metadata">

**Author:** ![SodAlmighty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sodalmighty/32/42450_2.png) [@SodAlmighty](https://discourse.julialang.org/u/SodAlmighty)\
**Post date:** [September 7, 2022, 10:29pm UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/5 "2022-09-07T22:29:40Z")

</div>

For experience, and also to help me increase my understanding of Lisp, I’ve been attempting to write a toy Lisp parser in various languages. I found Julia the other day, spent a few days reading the manual (yes, all of it) and now I’m having a go.

I was trying to do this:

```julia
struct SymbolExpr
	name ::String
end
const ListExpr = Vector{Expression}
const Expression = Union{SymbolExpr, ListExpr, Number, String}

```

So an `Expression` can be various types of expression. Ordinarily I’d use an abstract base class, but I also want it to be a `Vector{Expression}`, and you can’t do that with inheritance.

I guess I could just define `Expression` as a `Union{}`, but that strikes me as lazy.

---

<div class="post-metadata">

**Author:** ![SodAlmighty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sodalmighty/32/42450_2.png) [@SodAlmighty](https://discourse.julialang.org/u/SodAlmighty)\
**Post date:** [September 7, 2022, 10:32pm UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/6 "2022-09-07T22:32:58Z")

</div>

Maybe I could do something like `Union{T, Vector{T}} where T`. But I’d still need some way to limit it to valid expression types.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [September 8, 2022, 12:18am UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/7 "2022-09-08T00:18:28Z")

</div>

Unfortunately, AFAIK there are no [recursive data types](https://en.wikipedia.org/wiki/Recursive_data_type) in Julia.

---

<div class="post-metadata">

**Author:** ![benninkrs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/benninkrs/32/3191_2.png) [@benninkrs](https://discourse.julialang.org/u/benninkrs)\
**Post date:** [September 8, 2022, 12:38am UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/8 "2022-09-08T00:38:03Z")

</div>

Actually there are, as in [this example](https://docs.julialang.org/en/v1/manual/constructors/#Incomplete-Initialization).

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [September 8, 2022, 12:41am UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/9 "2022-09-08T00:41:25Z")

</div>

I’m not sure if self-referential data structure means the same as self-referential data types. Do you have an example (which solves OP’s problem)?

---

<div class="post-metadata">

**Author:** ![Mason](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mason/32/2423_2.png) [@Mason](https://discourse.julialang.org/u/Mason)\
**Post date:** [September 8, 2022, 1:14am UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/10 "2022-09-08T01:14:00Z")

</div>

It seems that what you’re doing involves a computed type relation. Our inheritance and type alias system does not support that

However, since we allow people to lift computations into the type domain, what you’re attempting here could perhaps be accomplished with what we call traits (though this is likely not a great idea).

```julia
struct Expression end
struct Not{T} end

# We treat symbol, number and string as having the Expression trait
isexpr(::Type{<:Union{Symbol, Number, String}}) = Expression

# A vector has the expression trait if it's element type has the expression trait.
isexpr(::Type{Vector{T}}) where {T} = isexpr(T)

# fallback method for all other types
isexpr(::Type) = Not{Expression}

foo(x::T) where {T} = foo(isexpr(T), x)
foo(::Type{Expression}, x) = "you gave me an expression!"
foo(::Type{Not{Expression}}, x) = "that's not an expression!"

```

In this way, when you do `foo(x)` it first asks “is `x` what I call and `Expression`?” and then forwards that information to the next method as a type that can be dispatched on.

```julia
julia> foo(1)
"you gave me an expression!"

julia> foo([:hi, :bye])
"you gave me an expression!"

julia> foo(Dict(1 => 2))
"that's not an expression!"

```

However, there’s an additonal problem with this, which is the promotion of element types in arrays:

```julia
julia> foo([:hi, "bye"])
"that's not an expression!"

```

this is because `[:hi, "bye"]` is a `Vector{Any}`, **not** a `Vector{Union{Symbol, String}}`. If you tell the array what element type you want though, it’ll work:

```julia
julia> let v = Union{Symbol, String}[:hi, "bye"]
           foo(v)
       end
"you gave me an expression!"

```

I think though for this reason, an array just isn’t a great datatype for this if you want to be able to verify at the type level that your expression only contains valid objects.

---

<div class="post-metadata">

**Author:** ![benninkrs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/benninkrs/32/3191_2.png) [@benninkrs](https://discourse.julialang.org/u/benninkrs)\
**Post date:** [September 8, 2022, 2:44am UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/11 "2022-09-08T02:44:43Z")

</div>

> I’m not sure if self-referential data structure means the same as self-referential data types

I’m not sure I understand the distinction. The example I linked to satisfies the definition given on the wikipedia page, namely, “a data type for values that may contain other values of the same type”.

> Do you have an example (which solves OP’s problem)?

To the extent I understand what the OP is trying to do, it is solved by @Sukera’s solution (and also the OP’s own solution in post 4), which is also an example of a recursive data type. But defining a type as a vector of itself I think doesn’t make sense.

---

<div class="post-metadata">

**Author:** ![SodAlmighty](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sodalmighty/32/42450_2.png) [@SodAlmighty](https://discourse.julialang.org/u/SodAlmighty)\
**Post date:** [September 8, 2022, 8:50am UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/12 "2022-09-08T08:50:27Z")

</div>

> what you’re attempting here could perhaps be accomplished with what we call traits

An interesting solution. Why “not a great idea”?

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [September 8, 2022, 8:57am UTC](https://discourse.julialang.org/t/how-to-define-a-type-that-may-be-a-vector-of-itself/86914/13 "2022-09-08T08:57:53Z")

</div>

I would also echo @Sukera 's replies. For such a central part of your project, it might well be worth it to define your own type.

Maybe you can take some inspiration from [julia/boot.jl at c094a89b9bf5ae9dccbf5d85c3925d619cfe1dcf · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/blob/c094a89b9bf5ae9dccbf5d85c3925d619cfe1dcf/base/boot.jl#L100) and [Essentials · The Julia Language](https://docs.julialang.org/en/v1/base/base/#Core.Expr)

Since your list expressions will eventually encapsulate a lot, you can follow @Sukera 's approach and even specify the types.

If you don’t want to define a new type because of inconvenience syntax, implement the functions from the corresponding interfaces: [Interfaces · The Julia Language](https://docs.julialang.org/en/v1/manual/interfaces/#Indexing)

* * *

By the way, the reply from @Mason is (as he probably knows) similar to [julia/expr.jl at dfbb9c49dda33b8e40dead35af97ccaf96fda4b0 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/blob/dfbb9c49dda33b8e40dead35af97ccaf96fda4b0/base/expr.jl)