Chained Lists in Julia

Using mutable structs in this version.

Definitions

In [15]:
abstract type ChainedList{T} end
In [16]:
struct EmptyList{T} <: ChainedList{T}
    end # "singleton" : no data at all
In [17]:
mutable struct NonEmptyList{T} <: ChainedList{T}
    first::T
    rest::ChainedList{T}
end

Easy construction

We define --> so that a --> L adds a (of type T) in the front of L, and a --> b creates a list with two elements. So a --> b --> c creates a list with three elements, and so on.

In [18]:
function -->(a::T, L::ChainedList{T}) where {T}
    return NonEmptyList{T}(a, L)
end
Out[18]:
--> (generic function with 2 methods)
In [19]:
function -->(a::T, b::T) where {T}
    empty= EmptyList{T}()
    return NonEmptyList{T}(a, NonEmptyList(b, empty))
end
Out[19]:
--> (generic function with 2 methods)

Pretty printing

In [20]:
function inner_string(L::EmptyList)
    return ""
end
Out[20]:
inner_string (generic function with 2 methods)
In [21]:
function inner_string(L::NonEmptyList{T}) where {T}
    if L.rest == EmptyList{T}()
        return string(L.first)
    else
        return string(L.first) * " --> " * inner_string(L.rest)
    end
end
Out[21]:
inner_string (generic function with 2 methods)
In [22]:
function Base.string(L::ChainedList)
    return "(" * inner_string(L) * ")"
end
    
function Base.print(L::ChainedList)
    print(string(L))
end
In [23]:
# the following does not work :
function Base.show(io,mime::MIME"text/plain",L::ChainedList{T}) where {T}
    println(io, string(L))
end

Efficient concatenation

Without any copying!

In [24]:
function extend!(L1::NonEmptyList{T}, L2::ChainedList{T}) where {T}
    if L1.rest == EmptyList{T}()
        L1.rest= L2
    else
        extend!(L1.rest, L2)
    end
end
Out[24]:
extend! (generic function with 1 method)

Examples

In [25]:
L= 5 --> 4 --> 3 --> 2 --> 1;
print(L)

(5 --> 4 --> 3 --> 2 --> 1)
In [26]:
L2= 5 --> 4 --> 3 --> 2 --> 1;
print(L2)

(5 --> 4 --> 3 --> 2 --> 1)
In [27]:
L == L2
Out[27]:
false
In [28]:
extend!(L, L2) # no output since the new Base.show does not work
Out[28]:
In [30]:
print(L)

(5 --> 4 --> 3 --> 2 --> 1 --> 5 --> 4 --> 3 --> 2 --> 1)