В этой статье рассмотрим добавление в программу на Julia пользовательского типа данных и перегрузку стандартных функций для удобной работы с новым типом.

Что такое пользовательский тип

Страшная тайна — граница между "пользовательскими" и "встроенными" типами данных в Julia практически отсутствует. В любой программе на Julia можно доопределить собственные типы данных, и работа с ними от работы со встроенными почти ничем не отличается ни с точки зрения написания кода, ни с точки зрения скорости исполнения этого кода (привет, Python). Вводимые типы данных могут быть либо примитивными, либо составными. Вторые делятся также на абстрактные и конкретные типы.

Далее будем рассматривать пример составных конкретных типов, т.к. конкретные объекты в памяти относятся к конкретным типам, а абстрактные нужны только для построения иерархии.

Составные типы определяются ключевыми словами struct и mutable struct. В первом случае создаётся неизменяемый тип:

# структура с полями x и y
struct Point
    x
    y
end

Объекты типа Point неизменяемы, т.е. значение поля в однажды созданном объекте нельзя изменить.

julia> p = Point(2, 3)
Point(2, 3)

julia> p.x
2

julia> p.y
3

julia> p.x = 4
ERROR: setfield! immutable struct of type Point cannot be changed

Но можно сделать и изменяемый тип:

mutable struct MutablePoint
    x
    y
end

julia> mp = MutablePoint(3, 4)
MutablePoint(3, 4)

julia> mp.y = 2
2

julia> mp
MutablePoint(3, 2)

Для эффективности полям структуры и самой структуре можно добавить аннотации типа. Например:

struct ParametricPoint{T<:Real}
    x::T
    y::T
end

Это значит, что тип ParametricPoint параметризован типом T и что поля x и y теперь должны быть значениями одного и того же типа T. Поведение будет таким:

julia> ParametricPoint(1, 1)
ParametricPoint{Int64}(1, 1)

julia> ParametricPoint{Float64}(1, 1)
ParametricPoint{Float64}(1.0, 1.0)

julia> ParametricPoint{Rational}(1, 1)
ParametricPoint{Rational}(1//1, 1//1)

# ошибка: один из аргументов не приводится к типу T
julia> ParametricPoint{Int}(1, 3.4)
ERROR: InexactError: Int64(3.4)

# ошибка: аргументы разных типов
julia> ParametricPoint(1, 1.0)
ERROR: MethodError: no method matching Point(::Int64, ::Float64)

# ошибка: тип T должен относиться к действительным числам
julia> ParametricPoint{Any}(1,1)
ERROR: TypeError: in Point, in T, expected T<:Real, got Type{Any}

Далее рассмотрим чуть более сложный пример типа-контейнера, чтобы увидеть, какие методы есть в стандартной библиотеке для работы с такими типами.

Двусторонняя очередь

Двустороннюю очередь сделаем из узлов типа DequeNode, которые будут включать запись с данными и ссылки на предыдущий и следующий элементы очереди. Тип DequeNode обязательно должен быть изменяемым, т.к. ссылки нужно будет перезаписывать.

mutable struct DequeNode{T}
    data::T
    prev::DequeNode{T}
    next::DequeNode{T}

    # пустой конструктор - возвращает не до конца инициализированную структуру
    function DequeNode{T}() where T
        node = new{T}()
        node.prev = node.next = node
        return node
    end
    # конструктор с начальным значением
    function DequeNode{T}(x) where T
        node = new{T}()
        node.data = x
        node.prev = node.next = node
        return node
    end
end

Внутренние конструкторы в данном случае нужны, поскольку по умолчанию при конструировании объекта нужно передать аргументами значения всех полей. Поскольку тип задан самореферентно, стандартным конструктором невозможно было бы создать самый первый объект этого типа. Поэтому делаем специальные конструкторы, которые создают узел очереди, ссылающийся сам на себя.

Саму очередь можно представить как фиктивный "входной" узел, не содержащий никаких данных. Его ссылка next будет указывать на первый элемент очереди, а prev — на последний. Для пустой очереди обе ссылки указывают на входной узел. Такая организация упрощает процедуры добавления и удаления узлов.

struct Deque{T}
    entry::DequeNode{T}
end

Deque{T}() where T = Deque{T}(DequeNode{T}())
Deque() = Deque{Any}()

Для структуры самой очереди внутренний конструктор уже не требуется.

Добавление элементов

Стандартными процедурами для очереди являются добавление элемента в начало и в конец и извлечение элементов из начала и конца. Для этих процедур в стандартной библиотеке уже есть функции, к которым нужно будет только добавить методы работы с ещё одним типом:

• push!(collection, element) — добавление элемента в коллекцию (для упорядоченной коллекции — в конец)
• pushfirst!(collection, element) — добавление элемента в начало упорядоченной коллекции
• pop!(collection) — удаление элемента из коллекции (для упорядоченной коллекции — из конца)
• popfirst!(collection) — удаление первого элемента из упорядоченной коллекции

Все эти функции находятся в модуле Base, в него и нужно добавить новые методы. Дополнительно напишем функцию проверки, не пустая ли коллекция — Base.isempty(collection).

Base.isempty(deq::Deque) = deq.entry.prev ? deq.entry

function Base.push!(deq::Deque{T}, elt) where T
    tail = deq.entry.prev
    new_item = DequeNode{T}(elt)
    new_item.prev, new_item.next = tail, deq.entry
    tail.next = deq.entry.prev = new_item
    return deq
end

function Base.pushfirst!(deq::Deque{T}, elt) where T
    head = deq.entry.next
    new_item = DequeNode{T}(elt)
    new_item.prev, new_item.next = deq.entry, head
    head.prev = deq.entry.next = new_item
    return deq
end

function Base.pop!(deq::Deque)
    !isempty(deq) || throw(ArgumentError("deque must be non-empty"))
    last = deq.entry.prev 
    last.prev.next = deq.entry
    deq.entry.prev = last.prev
    return last.data
end

function Base.popfirst!(deq::Deque)
    !isempty(deq) || throw(ArgumentError("deque must be non-empty"))
    first = deq.entry.next
    first.next.prev = deq.entry
    deq.entry.next = first.next
    return first.data
end

Функция push!() позволяет почти тривиально написать конструктор очереди на основе произвольной коллекции:

function Deque(itr)
    d = Deque{eltype(itr)}()
    for elt in itr
        push!(d, elt)
    end
    return d
end

# а ещё конструктор с переменным числом аргументов
Deque(args...) = Deque(args)

Теперь новым типом уже почти можно пользоваться как очередью, если нам нужны только операции добавления и удаления и не требуется функция типа peek() (посмотреть элемент в голове или хвосте очереди, не извлекая его). Для неразрушающего доступа к элементам удобно определить функцию итерирования по контейнеру.

Итерирование

В Julia поддерживается концепция итераторов для прохода по элементам контейнера. Для итерирования нужно определить единственную функцию — iterate(container, state), где state определяет текущее состояние итератора. В частности, конструкция for x in collection — это синтаксический сахар для примерно такого кода:

let nextstate = iterate(collection)
    while nextstate ? nothing
        (x, state) = nextstate
        <что-то сделать>
        nextstate = iterate(collection, state)
    end
end

Функция iterate() принимает аргументом контейнер и "состояние итератора", а возвращает — либо кортеж из элемента контейнера и следующего состояния итератора, либо nothing, если контейнер закончился.
Для очереди логично в качестве "состояния" взять узел очереди, до которого дошла итерация:

function Base.iterate(deq::Deque{T},
                      state::DequeNode{T}=deq.entry) where T
    nextstate = state.next
    nextstate ? deq.entry ? nothing : (nextstate.data, nextstate)
end

Теперь элементы очереди можно перебирать циклом for:

julia> for x in Deque(1:10) println(x); end
1
2
3
4
5
6
7
8
9
10

Большим плюсом является то, что многие функции стандартной библиотеки Julia написаны с использованием обобщённых интерфейсов, в частности, итерирования. Таким образом, автоматически доопределяется проверка принадлежности элемента контейнеру:

julia> 5 ? Deque(3:10)
true

julia> 100 ? Deque(-5:5)
false

Также обнаруживаем, что стал работать метод first(), возвращающий первый элемент коллекции. Для полноты картины дополним метод last() для получения последнего элемента и итерирование в обратном порядке:

function Base.iterate(r::Base.Iterators.Reverse{Deque{T}},
                      state::DequeNode{T}=r.itr.entry) where T
    nextstate = state.prev
    nextstate ? r.itr.entry ? nothing : (nextstate.data, nextstate)
end

function Base.last(deq::Deque)
    isempty(deq) && throw(ArgumentError("deque must be non-empty"))
    deq.entry.prev.data
end

julia> for x in Iterators.reverse(Deque(1:10)) println(x); end
10
9
8
7
6
5
4
3
2
1

Итак, интерфейс очереди как структуры данных теперь полностью определён

Распечатка структуры

Хотя очередь полностью функционирует как структура данных, на печати она пока представляет форменное безобразие:

julia> Deque()
Deque{Any}(DequeNode{Any}(#undef, DequeNode{Any}(#= circular reference @-1 =#), DequeNode{Any}(#= circular reference @-1 =#)))

Добавим метод, чтобы очередь печаталась в более человеческом виде. Вывод структуры в терминал контролируется функцией Base.show(), которую и будем перегружать:

function Base.show(io::IO, deq::Deque{T}) where T
    print(io, "Deque{", T, "}(")
    next = iterate(deq)
    if next ? nothing
        item, state = next
        show(io, item)
        next = iterate(deq, state)
        while next ? nothing
            item, state = next
            print(io, ", ")
            show(io, item)
            next = iterate(deq, state)
        end
    end
    print(io, ")")
end

# Теперь печатается в намного более приятном виде
julia> Deque(1:5)
Deque{Int64}(1, 2, 3, 4, 5)
# очередь из очередей тоже печатается корректно
julia> Deque(Deque(), Deque(), Deque())
Deque{Deque{Any}}(Deque{Any}(), Deque{Any}(), Deque{Any}())

Доступ и изменение по индексу

В принципе, очередь можно использовать и как контейнер с доступом по индексу. Получение и изменение значения по индексу контролируются функциями getindex() и setindex!(). Реализуем нужные методы для очереди.

function Base.getindex(deq::Deque, i::Integer)
    i > 0 || throw(BoundsError(deq, i))
    next = iterate(deq)
    for idx in 1:i-1
        next ? nothing && throw(BoundsError(deq, i))
        _, state = next
        next = iterate(deq, state)
    end
    if next ? nothing
        throw(BoundsError(deq, i))
    else
        return next[1]
    end
end

function Base.setindex!(deq::Deque, val, i::Integer)
    i > 0 || throw(BoundsError(deq, i))
    next = iterate(deq)
    for idx in 1:i-1
        next ? nothing && throw(BoundsError(deq, i))
        _, state = next
        next = iterate(deq, state)
    end
    if next ? nothing
        throw(BoundsError(deq, i))
    else
        record = next[2]
        record.data = val
        return val
    end
end

Полезно также добавить функции вставки элемента в произвольное место insert!() и удаления элемента из произвольной позиции:

function Base.insert!(deq::Deque{T}, i::Integer, val) where T
    i > 0 || throw(BoundsError(deq, i))
    next = iterate(deq)
    for idx in 1:i-1
        next ? nothing && throw(BoundsError(deq, i))
        _, state = next
        next = iterate(deq, state)
    end
    if next ? nothing
        push!(deq, val)
    else
        record = next[2]
        new_node = DequeNode{T}(val)
        new_node.prev, new_node.next = record.prev, record
        record.prev = record.prev.next = new_node
        deq
    end
end

function Base.deleteat!(deq::Deque, i::Integer)
    i > 0 || throw(BoundsError(deq, i))
    next = iterate(deq)
    for idx in 1:i-1
        next ? nothing && throw(BoundsError(deq, i))
        _, state = next
        next = iterate(deq, state)
    end
    if next ? nothing
        throw(BoundsError(deq, i))
    else
        record = next[2]
        record.prev.next, record.next.prev = record.next, record.prev
    end
end

Прочее

Как уже было сказано, ряд функций стандартной библиотеки написан с использованием итераторов, что позволяет им автоматически работать с любым типом, для которого определена функция iterate(). В частности, будут работать функции типа map(), collect() и методы редукции, такие как sum() или minimum().
Например, функцию для нахождения длины очереди можно написать так:

Base.length(deq::Deque) = sum(x->1, deq)

julia> length(Deque(1, 1, 2, 3, 5, 8, 13))
7

Заключение

Как видим, создать в Julia собственный тип данных и организовать удобную работу с ним весьма просто. Благодаря использованию обобщённого программирования в стандартной библиотеке, обычно достаточно определить несколько основных функций, и ряд зависящих от них станет работать автоматически. Так, определив push!(container, element) для добавления единственного элемента, можно обнаружить, что будет работать и push!(container, elements...) для добавления произвольного числа аргументов. Определив итератор, вообще получаем автоматом все функции стандартной библиотеки для работы с абстрактным контейнером.

Happy Hacking!