Share
Embed
PureScript Meetup #12
# PureScript Meetup #12
## Pattern Matching & Algebraic Data Types
PureScript By Example Chapter 5: https://github.com/paf31/purescript-book/blob/master/text/chapter5.md
tc39/proposal-pattern-matching: https://github.com/tc39/proposal-pattern-matching
cybai
December 20, 2017
Transcript
71 slides
-
Agenda • Pattern Matching • Guards • Case Expression •
Named Patterns • Nested Patterns • Wildcard pattern • Totality 2 -
Agenda (Cont.) • Introduction to Algebraic Data Types • Sum
Type • Product Type • `type` • `newtype` 3 -
Pattern Matching gcd :: Int -> Int -> Int gcd
n 0 = n gcd 0 m = m gcd n m = if n > m then gcd (n - m) m else gcd n (m - n) 6 -
Pattern Matching gcd :: Int -> Int -> Int gcd
n 0 = n gcd 0 m = m gcd n m = if n > m then gcd (n - m) m else gcd n (m - n) 7 Each line is called an alternative or a case. The expressions on the left of the equals sign are called patterns -
Pattern Matching (Cont.) 8 gcd :: Int -> Int ->
Int gcd n 0 = n gcd 0 n = n gcd n m | n > m = gcd (n - m) m | otherwise = gcd n (m - n) Guards `otherwise` is an alias for `true` from `Prelude`. Ref: Pursuit of `otherwise` -
Pattern Matching (Cont.) 9 Case Expression describeArray :: Array Int
-> String describeArray xs = "This array is " <> case xs of [] -> "empty." [x] -> "a singleton array." xs -> "a longer array." -
Pattern Matching (Cont.) 10 Named Patterns sortPair :: Array Int
-> Array Int sortPair arr@[x, y] | x <= y = arr | otherwise = [y, x] sortPair arr = arr -
Pattern Matching (Cont.) 11 Record Pattern showPerson :: { first
:: String, last :: String } -> String showPerson { first: x, last: y } = y <> ", " <> x -
Pattern Matching (Cont.) 12 type Address = { street ::
String, city :: String } type Person = { name :: String, address :: Address } livesInLA :: Person -> Boolean livesInLA { address: { city: "Los Angeles" } } = true livesInLA _ = false Record Pattern w/ Nested Pattern -
Pattern Matching (Cont.) 13 Wildcard pattern fromString :: String ->
Boolean fromString "true" = true fromString _ = false -
Pattern Matching (Cont.) 14 isEmpty :: forall a. Array a
-> Boolean isEmpty [] = true isEmpty _ = false Wildcard pattern takeFive :: Array Int -> Int takeFive [0, 1, a, b, _] = a * b takeFive _ = 0 -
Pattern Matching (Cont.) • Functions which return a value for
any combination of inputs are called total functions. • Functions which do not are called partial. 15 Totality Ref: PureScript By Example - CH5 - Pattern Match Failures and Partial Functions -
Pattern Matching (Cont.) 16 Totality not :: Boolean -> Boolean
not true = false Compiler will detect exhaustive which means that this function doesn’t match all the cases of `Boolean`; also, it means this is a partial function. -
Pattern Matching (Cont.) 17 Totality import Partial.Unsafe (unsafePartial) not ::
Boolean -> Boolean not = unsafePartial \true -> false If we still need to make this function as a partial function, then we need to use the `unsafePartial` function to let compiler know this is a partial function. -
Pattern Matching (Cont.) 18 showPerson :: forall r. { first
:: String, last :: String | r } -> String showPerson { first: x, last: y } = y <> ", " <> x Row Polymorphism -
Pattern Matching (Cont.) 19 After looking these syntax, maybe some
people will think: Isn’t it just like a `switch-case`? -
Pattern Matching (Cont.) 20 After looking these syntax, maybe some
people will think: Isn’t it just like a `switch-case`? No, they’re different. -
Pattern Matching (Cont.) 21 After looking these syntax, maybe some
people will think: Isn’t it just like a `switch-case`? No, they’re different. But, why? What’s the difference? -
Pattern Matching (Cont.) 22 Let’s take a look for an
example first. In JS function leftPad(str, padding) { switch (typeof padding) { case "number": return Array(padding + 1).join(" ") + str; case "string": return padding + str; default: throw new Error( `Unexpected type with '${padding}'.` ); } } -
Pattern Matching (Cont.) 23 Let’s take a look for an
example first. In PureScript data Padding = PaddingStr String | PaddingNum Int repeat :: String -> Int -> String repeat str 0 = str repeat str n = str <> (repeat str (n - 1)) leftPad :: String -> Padding -> String leftPad s (PaddingStr a) = a <> s leftPad s (PaddingNum a) = repeat " " a <> s -
Pattern Matching (Cont.) 24 With Algebraic Data Types, the Type
System of PureScript will help us to check the type w/ your data types; however, in JS, you need to check each type of value by yourself with `if` or `switch`. -
Pattern Matching (Cont.) 25 So, yeah, the benefit of Pattern
Matching is from Algebraic Data Types. Let’s dig into the world of ADTs. -
– Orah Kittrell “A type can be thought of as
an enumeration of constructors that have zero or more arguments.” 27 -
Algebraic Data Types 28 Before talking about what Algebraic Data
Type exactly is, let’s talk about how datatypes construct. -
Algebraic Data Types 31 data Bool = False | True
Declare a data type -
Algebraic Data Types 32 data Bool = False | True
Declare a data type Type Constructor without Argument -
Algebraic Data Types 33 data Bool = False | True
Declare a data type Type Constructor without Argument Data Constructors a.k.a Value Constructors In this case, it takes no arguments so we can also call it nullary constructor. -
Algebraic Data Types 34 data Bool = False | True
Declare a data type Type Constructor without Argument Data Constructors a.k.a Value Constructors In this case, it takes no arguments so we can also call it nullary constructor. This `pipe` denotes to Sum Type which we’ll mention in the later slides. -
Algebraic Data Types 35 • Type Constructor • Data Constructor
We can know there’re two kinds of constructors from previous slides: Let’s understand how they’re different. -
Algebraic Data Types • Used at type level, in type
signature, typeclass declarations and instances. (Type Class and Instance will not be covered in this slides.) • Types are static and solve at compile time. 36 Type constructors -
Algebraic Data Types • Construct values at term level. •
Can interact with the values at runtime. • Only exist in value, term, or runtime space. • value, term, and runtime space are not different but just describe the types for different spaces. 37 Data constructors Term level is where your values live and is the code that executes when your program is running. -
Algebraic Data Types 38 Although the term constructor is often
used to describe all type constructors and data constructors, we can make a distinction between constants and constructors. Ref: haskellbook - CH11 -
Algebraic Data Types 39 Constants data Bool = False |
True We can see `Bool` as an example of type constants. It takes no arguments and is nullary. Also, its data constructors are also constants which also take no arguments. -
Algebraic Data Types 40 Constructors Type constructor takes one argument.
data List a = Nil | Cons a (List a) Phantom data constructor which means its type constructor has argument(s) but it doesn’t use the argument(s) like a phantom. Data constructor awaiting two values to be applied to. Besides, the values must be same type as `a` in type constructor. -
Algebraic Data Types 41 data Bool = True | False
toString :: Bool -> String toString True = "true" toString False = "false" Example -
Algebraic Data Types 43 Arity Arity means how many arguments
a function or a constructor take. -
Algebraic Data Types 44 Arity Arity means how many arguments
a function or a constructor take. nullary is combined from `null` and `-ary`. `-ary` means “of” -
Algebraic Data Types • nullary data constructor: constructor takes no
arguments • unary data constructor: constructor takes one argument • data constructor takes more than one arguments; we’ll call them products 45 Arity -
Algebraic Data Types 46 Arity -- | nullary data Unit
= Unit -- | unary data Currency = Currency Int -- | product of two points data Line = Line Point Point We’ll talk about product type in the later slides. -
Algebraic Data Types 48 Why we call it algebraic data
type? Because we can understand how argument structures construct via two basic operations: sum and product. -
Algebraic Data Types 49 Why we call it algebraic data
type? Because we can understand how argument structures construct via two basic operations: sum and product. So, we can calculate how many possible implementation via type signature. -
Algebraic Data Types 52 Sum Type The pipe operator, `|`,
means “or”. This is the `sum` in algebraic data types. -
Algebraic Data Types 53 Sum Type The pipe operator, `|`,
means “or”. This is the `sum` in algebraic data types. data Bool = False | True -
Algebraic Data Types 54 Sum Type The pipe operator, `|`,
means “or”. This is the `sum` in algebraic data types. data Bool = False | True We know nullary data constructor represents only one possible. Thus, it also means 1. -
Algebraic Data Types 55 Sum Type The pipe operator, `|`,
means “or”. This is the `sum` in algebraic data types. data Bool = False | True We know nullary data constructor represents only one possible. Thus, it also means 1. We can count its cardinality to find Bool is like a set with 2 elements. -
Algebraic Data Types 56 Sum Type: Exercise data Browser =
Chrome | Firefox | Safari | Opera | Edge -
Algebraic Data Types 57 Sum Type: Exercise data Browser =
Chrome | Firefox | Safari | Opera | Edge Ans: The cardinality of `Browser` type constructor is 5. -
Algebraic Data Types 59 Product Type A product type’s cardinality
is the product of the cardinalities of its data constructors. -
Algebraic Data Types 60 Product Type A product type’s cardinality
is the product of the cardinalities of its data constructors. If Sum Type represents “or”, then Product Type represents “and”. -
Algebraic Data Types 61 Product Type A product type’s cardinality
is the product of the cardinalities of its data constructors. If Sum Type represents “or”, then Product Type represents “and”. Any data constructor with more than one argument is a product. -
Algebraic Data Types 62 Product Type A product type’s cardinality
is the product of the cardinalities of its data constructors. If Sum Type represents “or”, then Product Type represents “and”. Any data constructor with more than one argument is a product. Let’s try to define one! -
Algebraic Data Types 64 Product Type data BrowserVendor = Vendor
Browser Bool We already knew that cardinality of Browser is 5 and cardinality of Bool is 2. -
Algebraic Data Types 65 Product Type data BrowserVendor = Vendor
Browser Bool We already knew that cardinality of Browser is 5 and cardinality of Bool is 2. [ Chrome True, Chrome False, Firefox True, Firefox False, Safari True, Safari False, Opera True, Opera False, Edge True, Edge False, ] -
Algebraic Data Types 66 Product Type data BrowserVendor = Vendor
Browser Bool We already knew that cardinality of Browser is 5 and cardinality of Bool is 2. [ Chrome True, Chrome False, Firefox True, Firefox False, Safari True, Safari False, Opera True, Opera False, Edge True, Edge False, ] If we try to enumerate this data type, then we can get the cardinality with 10 which is equal to 2 * 5. -
Algebraic Data Types • Type synonym a.k.a Type alias •
Cannot define typeclass instances • Ex. 67 type type Name = String -
Algebraic Data Types • Define a type that can only
have a unary data constructor • Cannot be a product type, sum type, or contain nullary constructors • Can define typeclass instances • No runtime overhead due to reusing the type it contains • Ex. 68 newtype newtype String = Array Char