Recursive type union

General Usage
1

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
2

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

1 Like
3

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

4

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.

5

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

6

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.

7

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.

8

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.

9

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
10

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