First-Class Patterns

60 %
40 %
Information about First-Class Patterns
Technology

Published on February 27, 2014

Author: jdegoes

Source: slideshare.net

Description

Some languages, like SML, Haskell, and Scala, have built-in support for pattern matching, which is a generic way of branching based on the structure of data.

While not without its drawbacks, pattern matching can help eliminate a lot of boilerplate, and it's often cited as a reason why functional programming languages are so concise.

In this talk, John A. De Goes talks about the differences between built-in patterns, and so-called first-class patterns (which are "do-it-yourself" patterns implemented using other language features).

Unlike built-in patterns, first-class patterns aren't magical, so you can store them in variables and combine them in lots of interesting ways that aren't always possible with built-in patterns. In addition, almost every programming language can support first-class patterns (albeit with differing levels of effort and type-safety).

During the talk, you'll watch as a mini-pattern matching library is developed, and have the opportunity to follow along and build your own pattern matching library in the language of your choice.

First-Class Patterns John A. De Goes - @jdegoes Frontier Developers, February 26

Agenda ● ● ● ● ● ● Intro Pattern Matching 101 First-Class-ness 101 Magical Patterns First-Class Patterns Exercises

Intro Pattern Matching ● Divides a (possibly infinite) set of values into a discrete number of cases, where each case can be handled in a uniform way ● “if” on steroids ○ Sometimes strictly more powerful (e.g. Haskell)

Intro - Examples -- sign of a number sign x | | | x > 0 x == 0 x < 0 = = = 1 0 -1 -- take the first n elements from a list take take take 0 _ n _ [] (x:xs) = = = [] [] x : take (n-1) xs -- generate some javascript valueToJs valueToJs valueToJs valueToJs ... :: Options -> ModuleName -> Environment -> Value -> JS _ _ _ (NumericLiteral n) = JSNumericLiteral n _ _ _ (StringLiteral s) = JSStringLiteral s _ _ _ (BooleanLiteral b) = JSBooleanLiteral b

Intro - Examples sealed trait Level case object Level1 extends Level case object Level2 extends Level sealed trait Title case object DBAdmin extends Title case class SWEngineer(level: Level) extends Title case class Employee(manager: Option[Employee], name: String, title: Title) val employees = ??? val selfManagedLevel2Engineers = employees.collect { case Employee(None, name, SWEngineer(Level2)) => name }

Pattern Matching 101 Filter Does it have the structure I want? [Yes/No] If so, extract out the pieces that are relevant to me. Extract

Pattern Matching 101 -- take the first n elements from a list take 0 _ = [] take _ [] = [] take n (x:xs) = x : take (n-1) xs Filter - does it have non-empty list structure? Extract - Give me ‘head’ and ‘tail’

Pattern Matching 101 Products Sums case class Employee( sealed trait Title manager: Option[Employee], name: String, title: case object DBAdmin extends Title terms Title case class SWEngineer(level: Level) extends Title ) class Account { interface Shape { } ... class Rect extends Shape { … } public Account(BigDecimal balance, User holder) { class Ellipse extends Shape { … } ... } } class Pentagon extends Shape { … } terms

First-Class-ness 101 data Maybe a = Nothing | Just a deriving (Eq, Ord) class Person { public Person(String name, int age) { ... } }

First-Class-ness 101 Magic interferes with your ability to abstract and compose.

Magical Patterns Ordinary Duplication sealed object … case case trait Provenance Provenance { class Either(left: Provenance, right: Provenance) extends Provenance class Both(left: Provenance, right: Provenance) extends Provenance def allOf(xs: Seq[Provenance]): Provenance = { if (xs.length == 0) Unknown else if (xs.length == 1) xs.head else xs.reduce(Both.apply) } def anyOf(xs: Seq[Provenance]): Provenance = { if (xs.length == 0) Unknown else if (xs.length == 1) xs.head else xs.reduce(Either.apply) } }

Magical Patterns Factoring sealed object case case case case case trait Provenance Provenance { object Unknown extends Provenance object Value extends Provenance class Relation(value: SqlRelation) extends Provenance class Either(left: Provenance, right: Provenance) extends Provenance class Both(left: Provenance, right: Provenance) extends Provenance def allOf(xs: Seq[Provenance]): Provenance = reduce(xs)(Both.apply) def anyOf(xs: Seq[Provenance]): Provenance = reduce(xs)(Either.apply) private def reduce(xs: Seq[Provenance])( f: (Provenance, Provenance) => Provenance): Provenance = { if (xs.length == 0) Unknown else if (xs.length == 1) xs.head else xs.reduce(f) } }

Magical Patterns Factoringz sealed object case case case case case trait Provenance Provenance { object Unknown extends Provenance object Value extends Provenance class Relation(value: SqlRelation) extends Provenance class Either(left: Provenance, right: Provenance) extends Provenance class Both(left: Provenance, right: Provenance) extends Provenance private def strict[A, B, C](f: (A, B) => C): (A, => B) => C = (a, b) => f(a, b) val BothMonoid = Monoid.instance(strict[Provenance, Provenance, Provenance](Both.apply), Unknown) val EitherMonoid = Monoid.instance(strict[Provenance, Provenance, Provenance](Either.apply), Unknown) def allOf(xs: List[Provenance]): Provenance = Foldable[List].foldMap(xs)(identity)(BothMonoid) def anyOf(xs: List[Provenance]): Provenance = Foldable[List].foldMap(xs)(identity)(EitherMonoid) }

Magical Patterns Toxic Duplication - Abstraction Fail val Add = Mapping( "(+)", "Adds two numeric values" NumericDomain, , (partialTyper { case Type.Const(Data.Number(v1)) :: v2 :: Nil if (v1.signum == 0) => v2 case v1 :: Type.Const(Data.Number(v2)) :: Nil if (v2.signum == 0) => v1 case Type.Const(Data. Int(v1)) :: Type.Const(Data. Int(v2)) :: Nil => Type.Const(Data. Int(v1 + v2)) case Type.Const(Data.Number(v1)) :: Type.Const(Data.Number(v2)) :: Nil => Type.Const(Data.Dec(v1 + v2)) }) ||| numericWidening )

Magical Patterns Pattern Combinators - Composition Fail ● Product & sum ○ PartialFunction.orElse ● Negation ● Defaults ● Use-case specific

Magical Patterns Magical patterns limit your ability to abstract over patterns and to compose them together to create new patterns.

First-Class Patterns First-class patterns are built using other language features so you can abstract and compose them.

First-Class Patterns Haskell Example ex4 :: Either (Int,Int) Int -> Int ex4 a = match a $ (1+) <$> (left (pair var (cst 4)) ->> id <|> right var ->> id) <|> left (pair __ var) ->> id http://hackage.haskell.org/package/first-class-patterns

First-Class Patterns “For the rest of us” X match { case Y => Z } type Pattern???

First-Class Patterns Structure Input X match { Output case Y => Z } type Pattern??? Extraction

First-Class Patterns One ‘Option’ Input X match { Output case Y => Z } Extraction type Pattern[X, Z] = X => Option[Z]

First-Class Patterns Basic Patterns def some[A, B](p: Pattern[A, B]): Pattern[Option[A], B] = _.flatMap(p) def none[A, B]: Pattern[A, B] = Function.const( None) def k[A](v0: A): Pattern[A, A] = v => if (v == v0) Some(v0) else None def or[A, B](p1: Pattern[A, B], p2: Pattern[A, B]): Pattern[A, B] = v => p1(v).orElse(p2(v)) scala> or(none, some(k( 2)))(Some(2)) res3: Option[Int] = Some(2) https://gist.github.com/jdegoes/9240971

First-Class Patterns - JS And Now in JavaScript….Because http://jsfiddle.net/AvL4V/

First-Class Patterns Limitations ● Extractors cannot throw away information, leading to ‘dummy parameters’ ● Negation not possible under any circumstances ● No partiality warnings or built-in catch all

Exercises 1. Define a Pattern Combinator to Fix: val Add = Mapping( "(+)", "Adds two numeric values" NumericDomain, , (partialTyper { case Type.Const(Data.Number(v1)) :: v2 :: Nil if (v1.signum == 0) => v2 case v1 :: Type.Const(Data.Number(v2)) :: Nil if (v2.signum == 0) => v1 case Type.Const(Data. Int(v1)) :: Type.Const(Data. Int(v2)) :: Nil => Type.Const(Data. Int(v1 + v2)) case Type.Const(Data.Number(v1)) :: Type.Const(Data.Number(v2)) :: Nil => Type.Const(Data.Dec(v1 + v2)) }) ||| numericWidening ) EASY

Exercises 2. Define ‘Pattern’ and some core patterns in the language of your choice EASY

Exercises 3. Define an ‘And’ pattern that requires both inputs match EASY

Exercises 4. Define an alternate definition of pattern (along with a few core patterns) that permits pattern negation 4.b Optional: Use this to allow catch-alls MODERATE

Exercises 5. Define an alternate definition of pattern (along with a few core patterns) that permits extractors to throw away information HARD

THANK YOU First-Class Patterns John A. De Goes - @jdegoes Frontier Developers, February 26

Add a comment

Related presentations

Related pages

Online Fashion Training • 1st Class Patterns

Online fashion training a learning environment that reflects design education through the fashion industry with life-long learning skills in patternmaking ...
Read more

1st Class Patterns - YouTube

Learn with fashion industry experts and certified fashion educators - fashion design, pattern making, fashion draping and sewing with 1st Class Patterns ...
Read more

first-class-patterns: First class patterns and pattern ...

This package implements a library of first class patterns. The initial basis for this library was Morten Rhiger's "Type-safe pattern combinators"; the ...
Read more

1st Class Patterns - Facebook

1st Class Patterns is on Facebook. To connect with 1st Class Patterns, sign up for Facebook today. Sign Up Log In. 1st Class Patterns. Education Website.
Read more

First-class patterns. - ResearchGate - Share and discover ...

Page 1. First-class patterns Barry JayDelia Kesner University of Technology, SydneyPPS, CNRS and Universit´ e Paris 7 cbj@it.uts.edu.au kesner@pps.jussieu.fr
Read more

1st Class Patterns on Pinterest - Pinterest: Discover and ...

1st Class Patterns | Ezme Anderson PGDHE HND CERT fashion designer, pattern cutter & fashion educator #1CPEducation ~ #fashiondesign ~ #patternmaking ~ # ...
Read more

First Class Patterns (2000) - CiteSeerX

CiteSeerX - Document Details (Isaac Councill, Lee Giles, Pradeep Teregowda): . Pattern matching is a great convenience in programming. However, pattern ...
Read more

First-class patterns - ResearchGate - Share and discover ...

Pure pattern calculus supports pattern-matching functions in which patterns are first-class citizens that can be passed as parameters, evaluated and ...
Read more

First-class patterns - OPUS at UTS: Home - Open ...

JFP 19 (2): 191–225, 2009. c 2009 Cambridge University Press doi:10.1017/S0956796808007144 Printed in the United Kingdom 191 First-class patterns BARRY ...
Read more