Allow recursive definitions?

[ericphanson]

e.g. @jakobnissen was discussing on #helpdesk how to implement types for regex, and wrote the Rust version would look like

enum Re{
    Empty,
    Class(u8),
    Rep(Box<Re>),
    Alt(Box<Re>, Box<Re>),
    Cat(Box<Re>, Box<Re>),
    Diff(Box<Re>, Box<Re>),
    And(Box<Re>, Box<Re>),
}

I wanted to try with SumTypes, but ran into the fact that you can't have recursive definitions:

julia> using SumTypes

julia> @sum_type Re begin
           Empty()
           Class(::UInt8)
           Rep(::Re)
           Alt(::Re, ::Re)
           Cat(::Re, ::Re)
           Diff(::Re, ::Re)
           And(::Re, ::Re)
       end
ERROR: UndefVarError: Re not defined
Stacktrace:
 [1] top-level scope
   @ ~/.julia/packages/SumTypes/OTmhF/src/SumTypes.jl:92
 [2] top-level scope
   @ REPL[3]:1

[MasonProtter]

Sorry @ericphanson for the late reply. Yeah, this this unfortunately a problem with Julia itself not allowing recursive type definitions ☹️. It's in fact one of the few 3-digit issues still open: JuliaLang/julia#269

The way wound it here would be to write something like this:

julia> @sum_type _Re{T} begin
           Empty{T}()
           Class{T}(::UInt8)
           Rep{T}(::T)
           Alt{T}(::T, ::T)
           Cat{T}(::T, ::T)
           Diff{T}(::T, ::T)
           And{T}(::T, ::T)
       end
       const Re = _Re{_Re}
       Empty() = Empty{Re}()
       Class(x) = Class{Re}(x)
       Rep(x) = Rep{Re}(x)
       Alt(x, y) = Alt{Re}(x, y)
       Diff(x, y) = Diff{Re}(x, y)
       And(x, y) = And{Re}(x, y);

julia> And(Empty(), Class(1))
And(Empty{Re}()::_Re{Re}, Class{Re}(0x01)::_Re{Re})::_Re{_Re{Re}}

but that's pretty ugly. Maybe we can automate the process in the package.

[MasonProtter]

Okay, @ericphanson, this now works with #19

Voila!

julia> using SumTypes

julia> @sum_type Re begin
           Empty
           Class(::UInt8)
           Rep(::Re)
           Alt(::Re, ::Re)
           Cat(::Re, ::Re)
           Diff(::Re, ::Re)
           And(::Re, ::Re)
       end;

julia> And(Empty, Empty)
And(Empty::Re, Empty::Re)::Re

julia> And(Empty, Class(0x0))
And(Empty::Re, Class(0x00)::Re)::Re

julia> And(Alt(Rep(Empty), Empty), Class(0x0))
And(Alt(Rep(Empty::Re)::Re, Empty::Re)::Re, Class(0x00)::Re)::Re

julia> count_classes(r::Re, c=0) = @cases r begin
           Empty => c
           Class => c + 1
           Rep(x) => c + count_classes(x)
           Alt(x, y) => c + count_classes(x) + count_classes(y)
           Cat(x, y) => c + count_classes(x) + count_classes(y)
           Diff(x, y) => c + count_classes(x) + count_classes(y)
           And(x, y) => c + count_classes(x) + count_classes(y)
       end;

julia> count_classes( And(Alt(Rep(Class(0x1)), Empty), Class(0x0)) )
2