Nevoic
4/20/2019 - 10:08 PM

Pattern Matching Comparison

Nat = Natural Number

Z = Zero

S = Successor

Functions with Natural Numbers:

  • addition (plus)
  • subtraction (sub)

Functions with the most general thing I could find that supports comparison operators:

  • quicksort (qs).
Swift.swift
content_copyfile_download
enum Nat {
  case Z
  indirect case S(Nat)
}

func plus(_ x: Nat, _ y: Nat) -> Nat {
  switch (x, y) {
    case (.Z, _): return y
    case (.S(let k), _): return Nat.S(plus(k, y))
  }
}

func sub(_ x: Nat, _ y: Nat) -> Nat {
  switch(x, y) {
    case(_, .Z): return x
    case(.Z, _): return Nat.Z
    case(.S(let a), .S(let b)): return sub(a, b)
  }
}

func qs <T: Comparable> (_ li: [T]) -> [T] {
  switch(li) {
    case []: 
      return []
    default:
      let x = li[0]
      let xs = li.dropFirst(1)
      return qs(xs.filter { $0 < x }) + [x] + qs(xs.filter { $0 >= x})
  }
}
Kotlin.kt
content_copyfile_download
sealed class Nat
object Z : Nat()
class S(val n: Nat) : Nat()

fun plus(x: Nat, y: Nat): Nat = when(x) {
    is Z -> y
    is S -> S(plus(x.n, y))
}

fun sub(x: Nat, y: Nat): Nat = when {
    y is Z -> x
    x is Z -> y
    x is S && y is S -> sub(x.n, y.n)
    else -> null!!
}

fun <T: Comparable<T>> qs(li: List<T>): List<T> = when (li) {
    listOf<T>() -> listOf()
    else -> {
        val x = li[0]
        val xs = li.drop(1)
        qs(xs.filter { it < x }) + listOf(x) + qs(xs.filter { it >= x })
    }
}
Scala.scala
content_copyfile_download
sealed trait Nat
case object Z extends Nat
case class S(n: Nat) extends Nat

def plus: (Nat, Nat) => Nat = {
  case (Z, y) => y
  case (S(k), y) => S(plus(k, y))
}

def sub: (Nat, Nat) => Nat = {
  case (x, Z) => x
  case (Z, y) => y
  case (S(a), S(b)) => sub(a, b)
}

def qs[T <: Ordered[T]]: List[T] => List[T] = {
  case List() => List()
  case x :: xs => qs(xs.filter(_ < x)) ++ List(x) ++ qs(xs.filter(_ >= x))
}
F.fs
content_copyfile_download
type Nat = Z | S of Nat

let rec plus = function
    | Z, y -> y
    | S k, y -> S (plus (k, y))
    
let rec sub = function
    | x, Z -> x
    | Z, y -> Z
    | S a, S b -> sub (a, b)
    
let rec qs = function
    | [] -> []
    | x :: xs -> qs (List.filter ((<) x) xs) @ [x] @ qs (List.filter ((>=) x) xs)
Haskell.hs
content_copyfile_download
data Nat = Z | S Nat deriving Show

plus Z y = y
plus (S k) y = S (plus k y)

sub x Z = x
sub Z y = Z
sub (S a) (S b) = sub a b

qs [] = []
qs (x:xs) = qs (filter (<x) xs) ++ [x] ++ qs (filter (>=x) xs)
notes.md
content_copyfile_download
  • Rendered
  • Source

Rules

  1. Make sure the functions are generic to the same level
  2. Make sure to use the language's pattern matching construct for all solutions, or the closest thing to it
  3. Write code concisely, but with the proper spacing and somewhat readable

Thoughts regarding pattern matching

Kotlin

Negative

The only language that lacked structural pattern matching.

Positive

  • Smart casting meant less loss from lack of structural matching & less explicit casting
  • Expression control statements and smart casting allowed for concise code

Swift

Negative

The only language with non-expression control statements.

Positive

  • Expressed algebraic data types (sum & product) via enums, bypassing the need to construct class hierarchies that are generally needed in OO languages
  • Enum type inference mostly solved the problem of the extra verbosity of enums vs sealed hierarchies (at the call site). And in the places the inference won't work, explicitly declaring the enum sometimes improves readability anyway.

Scala

Negative

The only language lacking null safety, which implicitly makes patterns more prone to error (although the idiom of Scala is Option, null only exists for Java interop).

Positive

  • Pattern matching is much closer to the gold standard of functional languages while maintaining general OO capabilities (like classes/inheritance/etc.).
  • Syntactic sugar for methods that consist entirely of patterns, at the call site and method definition

Haskell

Negative

Can't think of a negative specific to only Haskell in regards to pattern matching, scroll below for negatives it shares with other languages

Positive

  • Best pattern matching capacity among all.
  • Most concise
  • Can define functions entirely from patterns, types are inferred and generalized to the highest level (this is true of all functions though)

Haskell & Scala

Negative

  • Pattern matching may be incomplete, although it's a warning (optional error) in Haskell, and there are marker distinctions in Intellij for Scala between complete and incomplete patterns.

Positive

  • Have a lot more standard structural patterns to match to (lists for example)
  • Generally much more friendly to pattern matching due to syntax and language constructs

Kotlin & Scala

Positive

  • Concise class definitions made algebraic data type definitions more concise than most OO languages (although not as concise as Swift to be fair)
  • The sealed keyword allows small hierarchies to be known at compile time as they're all defined in one file, making them more like enums.

Extra code examples

Mix between Kotlin & Swift // Found out later the Scala version is better than this lol

  fun plus(n1: Nat, n2: Nat) = when(n1, n2) {
    (Z, _) -> n2
    (S(val k), _) -> S(plus(k, n2))
  }

Code to test plus method

Kotlin

println(plus(S(Z), S(S(Z))))

Scala:

Have to put all code in an object that extends App and run

println(plus(S(Z), S(S(Z))))

Haskell:

print $ plus (S Z) (S (S Z))

Swift:

print(plus(Nat.S(Nat.Z), Nat.S(Nat.S(Nat.Z))))