Algebraic Data Types

MLStyle’s algebraic data types (ADTs) are just a shorter syntax for writing the types you already know from Base Julia.

Basic constructors

The @data macro creates an abstract type and any number of subtypes. For example, suppose we want to create a type representing expressions for a calculator program.

@data Expression begin
    Value(::Int)
    Operation(::Symbol, ::Value, ::Value)
end

This @data macro creates

abstract type Expression end

struct Value <: Expression
    _1::Int
end

struct Operation <: Expression
    _1::Symbol
    _2::Value
    _3::Value
end

and defines MLStyle.pattern_uncall for each of those subtypes so they can be used in pattern matching. That’s it.

Specifying field names

Each of the subtypes can have field names specified like this:

@data T begin
    C1(a,b,c)
    C2(x,y)
end

which creates

abstract type T end

struct C1 <: T
    a
    b
    c
end

struct C2 <: T
     x
     y
end

and again defines MLStyle.pattern_uncall for each of those subtypes so they can be used in pattern matching.

Specifying field names and types

Field names and types can be specified together:

@data T begin
    C1(a::Int,b::Int,c::Int)
    C2(x::Float64,y::Float64)
end

which creates

abstract type T end

struct C1 <: T
    a::Int
    b::Int
    c::Int
end

struct C2 <: T
     x::Float64
     y::Float64
end

and once again defines MLStyle.pattern_uncall for each of those subtypes so they can be used in pattern matching.

Subtyping

You can subtype existing abstract types with the standard <: syntax:

julia> @data ShortVec{T} <: AbstractVector{T} begin
           V0()
           V1(::T)
           V2(::T, ::T)
       end

julia> supertypes(V0{Int})
(V0{Int64}, ShortVec{Int64}, AbstractVector{Int64}, Any)

Less familiar

Singleton instances

A type with no fields has only one instance. You can make two such singletons a and b

@data T begin
  a
  b
end

does essentially

abstract type T end

struct _A <: T end
const a = _A()

struct _B <: T end
const b = _B()

where a is the sole instance of its type (which is a subtype of T). Likewise b is the only instance of its type (which is also a subtype of T).

Again this defines MLStyle.pattern_uncall, as well as custom show methods for the values.

Cheat Sheet

Cheat sheet for regular ADT definitions:

@data A <: B begin
    C1 # is a singleton instance
    
    # C1 is a value but C2 is a constructor
    C2()
    
    # the capitalized means types(field names are "_1", "_2", ...)
    # C3(1, "2")._1 == 1
    C3(Int, String)
  
    C4(::Int, ::String)   # "::" means types
    
    # the lowercase means field names
    # C5(:ss, 1.0).a == :ss
    C5(a, b)
    
    C6(a::Int, b::Vector{<:AbstractString})
end

Cheat sheet for GADT definitions:

@data Ab{T} <: AB begin
    
    C1 :: Ab{X} #  C1 is an enum. X is not type variable!
    C2 :: () => Ab{Int}

    # where is for inference, the clauses must be assignments
    C3{A<:Number, B} :: (a::A, b::Symbol) => Ab{B} where {B = Type{A}}
    # C3(1, :a) :: C3{Int, Tuple{Int}}
    # C3(1, :a) :: Ab{Int, Tuple{Int}}
end

Examples

@data E begin
    E1
    E2(Int)
end

@assert E1 isa E && E2 <: E
@match E1 begin
    E2(x) => x
    E1 => 2
end # => 2

@match E2(10) begin
    E2(x) => x
    E1 => 2
end # => 10

@data A begin
    A1(Int, Int)
    A2(a :: Int, b :: Int)
    A3(a, b) # equals to `A3(a::Any, b::Any)`
end

@data B{T} begin
    B1(T, Int)
    B2(a :: T)
end

@data C{T} begin
    C1(T)
    C2{A} :: Vector{A} => C{A}
end

abstract type DD end
some_type_to_int(x::Type{Int}) = 1
some_type_to_int(x::Type{<:Tuple}) = 2

@data D{T} <: DD begin
    D1{T} :: Int => D{T}
    D2{A, B} :: (A, B, Int) => D{Tuple{A, B}}
    D3{A, N} :: A => D{Array{A, N}} where {N = some_type_to_int(A)}
end
# z :: D3{Int64,1}(10) = D3(10) :: D{Array{Int64,1}}

Example: Modeling Arithmetic Operations

using MLStyle
@data Arith begin
    Number(Int)
    Add(Arith, Arith)
    Minus(Arith, Arith)
    Mult(Arith, Arith)
    Divide(Arith, Arith)
end

The above code makes a clear description about Arithmetic operations and provides a corresponding implementation.

If you want to transpile above ADTs to some specific language, there is a clear step:

julia> eval_arith(arith :: Arith) =
          # locally and hygienically change the meaning of '!'
           let ! = eval_arith
               @match arith begin
                   Number(v)        => v
                   Add(fst, snd)    => !fst + !snd
                   Minus(fst, snd)  => !fst - !snd
                   Mult(fst, snd)   => !fst * !snd
                   Divide(fst, snd) => !fst / !snd
               end
           end
eval_arith (generic function with 1 method)

julia> eval_arith(
           Minus(
               Number(2),
               Divide(Number(20),
                      Mult(Number(2),
                           Number(5)))))
0.0

About Type Parameters

where is used for type parameter introduction.

The following 2 patterns are equivalent:

A{T1...}(T2...) where {T3...}
A{T1...}(T2...) :: A{T1...} where {T3...}

Check Advanced Type Pattern for more about where use in matching.