Julia: пользовательские типы

В этой статье рассмотрим добавление в программу на 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!