Julia Language Types Dispatching on Types

Example

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 Nil and 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())))

Is the list empty?

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 2:

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:

How long is the list?

The 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 length function?

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 isempty:

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

Next steps

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.