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

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

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

ERROR: UndefVarError: ListExpr not defined

1 Like
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.

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

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

struct ListExpr <: AbstractVector
   ...
end

and implement the array interface 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 here)?

1 Like

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:

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.

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.

Unfortunately, AFAIK there are no recursive data types in Julia.

Actually there are, as in this example.

1 Like

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)?

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).

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> 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> 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> 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.

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.

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

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

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 and Essentials · The Julia Language

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


By the way, the reply from @Mason is (as he probably knows) similar to julia/expr.jl at dfbb9c49dda33b8e40dead35af97ccaf96fda4b0 · JuliaLang/julia · GitHub