On Julia, you can define more than one method for each function. Suppose we define three methods of the same function:
foo(x) = 1 foo(x::Number) = 2 foo(x::Int) = 3
When deciding what method to use (called dispatch), Julia chooses the more specific method that matches the types of the arguments:
julia> foo('one') 1 julia> foo(1.0) 2 julia> foo(1) 3
This facilitates polymorphism. For instance, we can easily create a linked list by defining two immutable types, named
Cons. These names are traditionally used to describe an empty list and a non-empty list, respectively.
abstract LinkedList immutable Nil <: LinkedList end immutable Cons <: LinkedList first rest::LinkedList end
We will represent the empty list by
Nil() and any other lists by
Cons(first, rest), where
first is the first element of the linked list and
rest is the linked list consisting of all remaining elements. For example, the list
[1, 2, 3] will be represented as
julia> Cons(1, Cons(2, Cons(3, Nil()))) Cons(1,Cons(2,Cons(3,Nil())))
Suppose we want to extend the standard library's
isempty function, which works on a variety of different collections:
julia> methods(isempty) # 29 methods for generic function "isempty": isempty(v::SimpleVector) at essentials.jl:180 isempty(m::Base.MethodList) at reflection.jl:394 ...
We can simply use the function dispatch syntax, and define two additional methods of
isempty. Since this function is from the
Base module, we have to qualify it as
Base.isempty in order to extend it.
Base.isempty(::Nil) = true Base.isempty(::Cons) = false
Here, we did not need the argument values at all to determine whether the list is empty. Merely the type alone suffices to compute that information. Julia allows us to omit the names of arguments, keeping only their type annotation, if we need not use their values.
We can test that our
isempty methods work:
julia> using Base.Test julia> @test isempty(Nil()) Test Passed Expression: isempty(Nil()) julia> @test !isempty(Cons(1, Cons(2, Cons(3, Nil())))) Test Passed Expression: !(isempty(Cons(1,Cons(2,Cons(3,Nil())))))
and indeed the number of methods for
isempty have increased by
julia> methods(isempty) # 31 methods for generic function "isempty": isempty(v::SimpleVector) at essentials.jl:180 isempty(m::Base.MethodList) at reflection.jl:394
Clearly, determining whether a linked list is empty or not is a trivial example. But it leads up to something more interesting:
length function from the standard library gives us the length of a collection or certain iterables. There are many ways to implement
length for a linked list. In particular, using a
while loop is likely fastest and most memory-efficient in Julia. But premature optimization is to be avoided, so let's suppose for a second that our linked list need not be efficient. What's the simplest way to write a
Base.length(::Nil) = 0 Base.length(xs::Cons) = 1 + length(xs.rest)
The first definition is straightforward: an empty list has length
0. The second definition is also easy to read: to count the length of a list, we count the first element, then count the length of the rest of the list. We can test this method similarly to how we tested
julia> @test length(Nil()) == 0 Test Passed Expression: length(Nil()) == 0 Evaluated: 0 == 0 julia> @test length(Cons(1, Cons(2, Cons(3, Nil())))) == 3 Test Passed Expression: length(Cons(1,Cons(2,Cons(3,Nil())))) == 3 Evaluated: 3 == 3
This toy example is pretty far from implementing all of the functionality that would be desired in a linked list. It is missing, for instance, the iteration interface. However, it illustrates how dispatch can be used to write short and clear code.