Julia pattern matching and data structures

Julia Taiwan 發起人 杜岳華

2019.8.18

Outline

  • Value type
  • Simulate pattern matching
  • Linked list in functional style
  • Match package
  • True pattern matching
  • Other pattern matching packages

Multiple dispatch

In [1]:
foo(x::Integer) = "Integer!"
Out[1]:
foo (generic function with 1 method)
In [2]:
foo(5)
Out[2]:
"Integer!"

Value type

In [3]:
foo(::Val{true}) = "TRUE"
foo(::Val{false}) = "FALSE"
Out[3]:
foo (generic function with 3 methods)
In [4]:
foo(Val(true))
Out[4]:
"TRUE"
In [5]:
foo(Val(false))
Out[5]:
"FALSE"

Wrapping

In [6]:
foo(x::Bool) = foo(Val(x))
Out[6]:
foo (generic function with 4 methods)
In [7]:
foo(true)
Out[7]:
"TRUE"
In [8]:
foo(false)
Out[8]:
"FALSE"

What values can I dispatch on?

In [9]:
Val(true)
Out[9]:
Val{true}()
In [10]:
Val(5)
Out[10]:
Val{5}()
In [11]:
Val(UInt8(5))
Out[11]:
Val{0x05}()
In [12]:
Val(5.0)
Out[12]:
Val{5.0}()
In [13]:
Val(1+2im)
Out[13]:
Val{1 + 2im}()

What values can I dispatch on?

In [14]:
Val('A')
Out[14]:
Val{'A'}()
In [15]:
Val("ABC")

TypeError: in Type, in parameter, expected Type, got String

Stacktrace:
 [1] Val(::String) at ./essentials.jl:728
 [2] top-level scope at In[15]:1
In [16]:
Val([1,2,3])

TypeError: in Type, in parameter, expected Type, got Array{Int64,1}

Stacktrace:
 [1] Val(::Array{Int64,1}) at ./essentials.jl:728
 [2] top-level scope at In[16]:1

What values can I dispatch on?

  • All numbers
  • Char
  • Bool

Simulate pattern matching

In [17]:
isone(::Val{1}) = true
isone(::Val{N}) where {N} = false
isone(x::Int) = isone(Val(x))
Out[17]:
isone (generic function with 3 methods)
In [18]:
isone(1)
Out[18]:
true
In [19]:
isone(2)
Out[19]:
false
In [20]:
isone(2.0)

MethodError: no method matching isone(::Float64)
You may have intended to import Base.isone
Closest candidates are:
  isone(!Matched::Int64) at In[17]:3
  isone(!Matched::Val{1}) at In[17]:1
  isone(!Matched::Val{N}) where N at In[17]:2

Stacktrace:
 [1] top-level scope at In[20]:1

Dispatching on type

Value types wrap values into types.

Multiple dispatch is acting on types.

Linked list in functional style

In [21]:
abstract type LinkedList{T} end

mutable struct NullNode{T} <: LinkedList{T}
end

mutable struct Node{T} <: LinkedList{T}
    data::T
    next::LinkedList{T}
end
In [22]:
null = NullNode{Int}()
Out[22]:
NullNode{Int64}()
In [23]:
n1 = Node(1, null)
Out[23]:
Node{Int64}(1, NullNode{Int64}())
In [24]:
n2 = Node(2, n1)
Out[24]:
Node{Int64}(2, Node{Int64}(1, NullNode{Int64}()))
In [25]:
n3 = Node(3, n2)
Out[25]:
Node{Int64}(3, Node{Int64}(2, Node{Int64}(1, NullNode{Int64}())))

How to find 2?

In [26]:
istwo(::Val{2}) = true
istwo(::Val{N}) where {N} = false
istwo(x::Int) = istwo(Val(x))
Out[26]:
istwo (generic function with 3 methods)
In [27]:
findtwo(::NullNode) = false
findtwo(x::Node) = istwo(x.data) ? true : findtwo(x.next)
Out[27]:
findtwo (generic function with 2 methods)
In [28]:
findtwo(n3)
Out[28]:
true

How to replace 2?

In [29]:
replacetwo(::NullNode, n) = nothing
function replacetwo(x::Node, n)
    if istwo(x.data)
        x.data = n
        return n
    else
        return replacetwo(x.next, n)
    end
end
Out[29]:
replacetwo (generic function with 2 methods)
In [30]:
replacetwo(n3, 4)
Out[30]:
4
In [31]:
n3
Out[31]:
Node{Int64}(3, Node{Int64}(4, Node{Int64}(1, NullNode{Int64}())))

But...

The relation between pattern matching and multiple dispatch

Pattern matching package

In [32]:
using Match
In [33]:
bar(x) = @match x begin
   1 => "one"
   2 => "two"
   _ => "Something else..."
end
Out[33]:
bar (generic function with 1 method)
In [34]:
bar(1)
Out[34]:
"one"
In [35]:
bar(2)
Out[35]:
"two"
In [36]:
bar(3)
Out[36]:
"Something else..."

Match types

In [37]:
bar(x) = @match x begin
   n::Int      => "integer"
   str::String => "string"
   d::Dict     => "dictionary"
end
Out[37]:
bar (generic function with 1 method)
In [38]:
bar(5)
Out[38]:
"integer"
In [39]:
bar("5")
Out[39]:
"string"
In [40]:
bar(Dict(2 => "2"))
Out[40]:
"dictionary"

Find 2

In [41]:
findtwo2(x::LinkedList) = @match x begin
    Node(2, _)     => 2
    Node(_, next)  => findtwo2(next)
    x::NullNode    => 0
end
Out[41]:
findtwo2 (generic function with 1 method)
In [42]:
null = NullNode{Int}()
n1 = Node(1, null)
n2 = Node(2, n1)
n3 = Node(3, n2)
Out[42]:
Node{Int64}(3, Node{Int64}(2, Node{Int64}(1, NullNode{Int64}())))
In [43]:
findtwo2(n3)
Out[43]:
2

Implement some APIs

  • length
  • find
  • print

Let's try length

In [44]:
import Base.length
length(x::LinkedList, n) = @match x begin
    Node(_, next)  => length(next, n+1)
    x::NullNode    => n
end
length(x::LinkedList) = length(x, 0)
Out[44]:
length (generic function with 87 methods)
In [45]:
length(n3)
Out[45]:
3

Let's try find

In [46]:
find(x::LinkedList{T}, n::T) where {T} = @match x begin
    Node(d, _), if d == n end => true
    Node(_, next)             => find(next, n)
    x::NullNode               => false
end
Out[46]:
find (generic function with 1 method)
In [47]:
find(n3, 2)
Out[47]:
true
In [48]:
find(n3, 0)
Out[48]:
false

Let's try print

In [49]:
Base.show(io::IO, x::LinkedList{T}) where {T} = @match x begin
    Node(d, next)    => (print(d, ", "); Base.show(io, next))
    x::NullNode      => print()
end
In [50]:
print(n3)

3, 2, 1,

Other pattern matching packages

Thank you for attention