# Recursive type union

**URL:** <https://discourse.julialang.org/t/recursive-type-union/2972>\
**Category:** General Usage\
**Created:** [March 30, 2017, 4:35pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972 "2017-03-30T16:35:59Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [March 30, 2017, 4:35pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/1 "2017-03-30T16:35:59Z")

</div>

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

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

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 30, 2017, 4:51pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/2 "2017-03-30T16:51:49Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 30, 2017, 8:40pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/3 "2017-03-30T20:40:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [March 30, 2017, 9:25pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/4 "2017-03-30T21:25:53Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 30, 2017, 9:36pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/5 "2017-03-30T21:36:40Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![fengyang.wang](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fengyang.wang/32/104_2.png) [@fengyang.wang](https://discourse.julialang.org/u/fengyang.wang)\
**Post date:** [March 30, 2017, 9:44pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/6 "2017-03-30T21:44:06Z")

</div>

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

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

```

or my personal preference

```julia
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

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

```

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

---

<div class="post-metadata">

**Author:** ![fengyang.wang](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fengyang.wang/32/104_2.png) [@fengyang.wang](https://discourse.julialang.org/u/fengyang.wang)\
**Post date:** [March 30, 2017, 9:51pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/7 "2017-03-30T21:51:32Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [March 30, 2017, 11:24pm UTC](https://discourse.julialang.org/t/recursive-type-union/2972/8 "2017-03-30T23:24:23Z")

</div>

> 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](http://juliagraphs.github.io/LightGraphs.jl/latest/generators/) - they have a specific generator for binary trees.

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [March 31, 2017, 12:29am UTC](https://discourse.julialang.org/t/recursive-type-union/2972/9 "2017-03-31T00:29:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![miguelraz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/miguelraz/32/631_2.png) [@miguelraz](https://discourse.julialang.org/u/miguelraz)\
**Post date:** [March 31, 2017, 12:36am UTC](https://discourse.julialang.org/t/recursive-type-union/2972/10 "2017-03-31T00:36:00Z")

</div>

Perhaps you may then be interested in [Nemo.jl](https://github.com/wbhart/Nemo.jl), a computer algebra package with long term support and a recent awesome German grant.