Recursive type union

Is there any way to express “X is an Int, or a Tuple of X” in Julia?

const MyT = Union{Int, NTuple{2, MyT}}

fails because MyT is not in scope. I tried the Y-Combinator, but Julia doesn’t like (X{X} where X) either, so it doesn’t seem possible.

1 Like

I don’t think its possible and probably won’t be.

1 Like

What are you trying to match? I.e. What is X in the tuple of X?

Let’s say I implement a binary tree using tuples, eg. (1, ((4,5), 3)). How can I define a type which contains all such trees? I could use type/immutable of course, but in my case, that’s inconvenient.

You could make a new type, parametrised by the actual type of the hierarchy of tuples, and then dispatch on the base type.

That seems to me like overspecializing the type. If performance is not a concern, I would instead recommend either the simple

struct BinaryTree{T}
    data::Union{T, NTuple{2, BinaryTree{T}}}
end

or my personal preference

abstract BinaryTree{T}
struct BinaryNode{T} <: BinaryTree{T}
    left::BinaryTree{T}
    right::BinaryTree{T}
end
struct BinaryLeaf{T} <: BinaryTree{T}
    data::T
end

If performance is important, it is better to do

struct BinaryTree{T}
    isleaf::Bool
    left::BinaryTree{T}
    right::BinaryTree{T}
    data::T
end

and leave the unnecessary fields #undef, as may be required.

Note that, in particular, option (2) is the Julia equivalent of algebraic data types available in many languages, which it looks like is what @cstjean is trying to emulate.

Let’s say I implement a binary tree using tuples, eg. (1, ((4,5), 3)). How can I define a type which contains all such trees? I could use type/immutable of course, but in my case, that’s inconvenient.

You could also use LightGraphs.jl - they have a specific generator for binary trees.

Thank you for the suggestions everyone, but the binary tree was just an example. My use case is closer to first-order logic. My constants are numbers, tuples of numbers, tuples of tuples of numbers, etc. Not constants: variables, tuples with a variable, tuples of tuples with a variable, etc.

A recursive definition would have been neat, but I can express is_constant() as a function instead of a type, or replace tuples with a user-defined type. It’s not a significant issue.

1 Like

Perhaps you may then be interested in Nemo.jl, a computer algebra package with long term support and a recent awesome German grant.

1 Like