CS计算机代考程序代写 Haskell Elixir compiler Java python C/CPS 506

C/CPS 506
Comparative Programming Languages Prof. Alex Ufkes
Topic 7: Pattern matching, custom types in Haskell

Notice!
Obligatory copyright notice in the age of digital delivery and online classrooms:
The copyright to this original work is held by Alex Ufkes. Students registered in course CCPS 506 can use this material for the purposes of this course but no other use is permitted, and there can be no sale or transfer or use of the work for any other purpose without explicit permission of Alex Ufkes.
© Alex Ufkes, 2020, 2021 2

Course Administration
© Alex Ufkes, 2020, 2021
3
It’s important to start thinking about the assignment if you haven’t already.

Any Questions?
© Alex Ufkes, 2020, 2021
4

© Alex Ufkes, 2020, 2021
5
Let’s Get Started!

Types in Haskell
Statically Typed:
• Haskell uses static type checking.
• Every expression is assigned a type.
• If a function’s arguments aren’t the expected
type, a compile error occurs.
Type Inference
• Like Python, and unlike Java, we need not specify type.
• It is inferred by the context: X = “Hello”, X is a string.
• However, we can explicitly specify types.
• Good practice when we know what types we want;
compiler will give errors upon type mismatch.
© Alex Ufkes, 2020, 2021
6

Types in Haskell
:t can be used to reveal type:
• 1 is instance of Num type class.
• 1.0 is instance of Fractional type class.
• ‘a’ is a Char
• “Hello” is a [Char] • [Char] = String
• t is a Bool
© Alex Ufkes, 2020, 2021
7

Num p => p ?
Type Variables:
• p is a type variable whose value can be any type in typeclass Num (Integer, Float, etc.)
• Haskell is free to treat 7 as it sees fit, so long as it does so in a way that adheres to the operations defined in type class Num.
© Alex Ufkes, 2020, 2021
8

Typeclasses?
Haskell tries to keep types as generic as possible
• If we explicitly declare a variable as integer, it can’t be passed to a function requiring float.
• However, if we generically infer it to be a Num, it can be used anywhere any other member of Num is allowed.
© Alex Ufkes, 2020, 2021
9

Types in Haskell
We can explicitly indicate types:
• Use :: to assign a type
• My advice for you is to start by letting
the inference engine figure it out.
• At this point, it knows better than you.
© Alex Ufkes, 2020, 2021
10

Types in Haskell
We can explicitly indicate types:
When defining a name, can indicate type explicitly:
© Alex Ufkes, 2020, 2021
11

Type Classes
Type polymorphism and type variables:
Recall: Overloading
• In languages like C++, the == operator is
overloaded to work with many different types.
• Numeric type equality and string equality are
performed differently.
• In general, if we want to compare two values of
type α, we use an α-compare
• α is a type variable, because its value is a type.
© Alex Ufkes, 2020, 2021
12

Type Classes
Consider the equality (==) operator:
Takes two parameters, each of the same type (call it α), and returns a Boolean
This operator may not be defined for all types, just some. Thus, we can associate == with a specific type class containing those
types for which == is defined.
This type class is called Eq in Haskell.
© Alex Ufkes, 2020, 2021
13

Eq Type Class
(==) is defined for types in typeclass Eq
• (==) takes two args of type a, where a is a member of type class Eq
• It returns Bool
• If a concrete type, a, belongs to a certain type class, we say a is an instance of that type class.
• Int is an instance of Eq, for example.
© Alex Ufkes, 2020, 2021
14

© Alex Ufkes, 2020, 2021 15

Num Type Class
• This allows numeric values freedom to be an integer or floating point as the compiler sees fit.
• Num class contains all numbers, and certain operations over them such as addition.
© Alex Ufkes, 2020, 2021
16

Num Type Class
• p is a type variable
• The type of 5 isp, andpis a
member of type class Num
© Alex Ufkes, 2020, 2021
17

© Alex Ufkes, 2020, 2021 18

Show Type Class
Types that are members of the Show class have functions which convert their value to a String.
© Alex Ufkes, 2020, 2021
19

Function Types
head takes a list containing type a, and returns a value of type a
tail takes a list containing type a, and returns a list containing type a
© Alex Ufkes, 2020, 2021
20
a and b can be literally any type!

Function Types
putStrLn:
• Accepts String, returns IO action.
• -> indicates function
• String is input, IO() is output.
• More on IO actions later.
© Alex Ufkes, 2020, 2021
21
Same as [Char]

© Alex Ufkes, 2020, 2021
22
We’ll create our own types soon, and see how to add them to existing type classes.

© Alex Ufkes, 2020, 2021 23

Functions in Haskell
As expected of a pure functional language, functions are central in Haskell
© Alex Ufkes, 2020, 2021
24
• •
If we’re compiling our code into an executable, we need a main.
If we’re using the GHCi shell, we don’t.

Functions in Haskell
Let’s start simple:
Define function called square that takes one argument x
square computes x*x, where x is the input argument
© Alex Ufkes, 2020, 2021
25

Functions in Haskell
Let’s start simple:
© Alex Ufkes, 2020, 2021
26
Invoke function square in the typical fashion

Functions in Haskell
© Alex Ufkes, 2020, 2021
27
Function named sum
Parameter list
Expression to evaluate

Functions in Haskell
© Alex Ufkes, 2020, 2021
28
Passing in four args

Functions in Haskell
• Based on what we’re doing in square and sum (multiplying and adding)…
• Haskell determined that input and output type should be instances of typeclass Num.
• (+) and (*) are both defined for all types in typeclass Num.
© Alex Ufkes, 2020, 2021
29

Haskell Modules
This is getting tedious to type interactively.
Let’s create a module!
• Similar to modules in Elixir
• We can load the module in GHCi
• Access its functions and expressions
© Alex Ufkes, 2020, 2021
30

Loading a Module
© Alex Ufkes, 2020, 2021
31

© Alex Ufkes, 2020, 2021 32

When we make changes to Test module, can reload with 1 click!
© Alex Ufkes, 2020, 2021 33

Loading a Module
Use :load in terminal GHCi:
© Alex Ufkes, 2020, 2021
34

Control Structures
if then else
• Brackets required around negative arguments
• Otherwise it thinks you’re subtracting 6 from f
© Alex Ufkes, 2020, 2021
35

Control Structures
if then else if then else
• Here we have a function named sign, that takes one argument x
• It returns:
o -1 if x is negative o 1 if x is positive
o 0 if x is 0
• If/else construct in Haskell is similar to most other languages.
• It must include a then and an else
© Alex Ufkes, 2020, 2021
36

Control Structures
if then else if then else
We can now format across multiple lines. HOWEVER: Indentation matters in Haskell!
© Alex Ufkes, 2020, 2021
37

© Alex Ufkes, 2020, 2021 38

© Alex Ufkes, 2020, 2021 39

Indenting in Haskell
Golden Rule:
Code which is part of some expression should be indented further than the beginning of that expression
https://en.wikibooks.org/wiki/Haskell/Indentation
© Alex Ufkes, 2020, 2021
40

If all that weren’t enough, Tabs don’t work properly unless they’re 8 spaces exactly.
© Alex Ufkes, 2020, 2021 41

Local Names in Functions
When binding a name inside a function or module, we use the “let” keyword
© Alex Ufkes, 2020, 2021
42

Multiple Expressions
• We now have two expressions in this function!
• if/elseandlet
• Must add the do keyword
© Alex Ufkes, 2020, 2021
43

© Alex Ufkes, 2020, 2021 44

Case Statement
• When matching specific values, a case construct is easier to write.
• Just like Elixir, the _ is wild. It catches everything else.
© Alex Ufkes, 2020, 2021
45

Case Statement
© Alex Ufkes, 2020, 2021
46

Pattern Matching: Case
© Alex Ufkes, 2020, 2021
47

Pattern Matching: Case
© Alex Ufkes, 2020, 2021
48
Will never match!

© Alex Ufkes, 2020, 2021 49

Unlike Elixir…
Try and be more general to catch anything that isn’t a 3-tuple?
© Alex Ufkes, 2020, 2021
50

Piecewise Functions
Just like Elixir’s function signature pattern matching
Makes recursion very easy!
© Alex Ufkes, 2020, 2021
51

Piecewise Functions
• Return unit vector if point lies on axis
• Return input point otherwise
© Alex Ufkes, 2020, 2021
52

Functions: Guards
• Matches input arguments to x and y
• Guards denoted with |
• otherwise is the same as saying True
© Alex Ufkes, 2020, 2021
53

Recursion
© Alex Ufkes, 2020, 2021
54
Classic list length finder
Built-in length function
Our own user function

Tail Recursion?
© Alex Ufkes, 2020, 2021
55
Less important in Haskell
• In Haskell, function call model is different
• Function calls don’t necessarily create a
new stack frame
• In practice, tail recursion not a big deal.

Recursion: cons
Here we treat the input argument as a pair containing the head and tail of the list.
© Alex Ufkes, 2020, 2021
56

Recursion: filter
• First argument is a Boolean function
• Second input is a list
• Base case is if the list is empty
• Otherwise, we call the function p with
the head of the list.
• If true, append it to the running list
• If false, do not append
• In both cases, make the recursive call
with the tail.
© Alex Ufkes, 2020, 2021
57
• Returns true if x >= 0 • Falseotherwise

Recursion: filter
© Alex Ufkes, 2020, 2021
58
Test pos function

Return Multiple Things? Lists/tuples to the rescue!
• Notice there is a lot of duplicate computation here.
• Add a local variable?
© Alex Ufkes, 2020, 2021
59

let/in Structure
• This is one expression (let/in)
• We don’t need to add do keyword
© Alex Ufkes, 2020, 2021
60

© Alex Ufkes, 2020, 2021 61

Infix Functions
Use symbolic operators as functions:
Enclose in parentheses to use in non-infix mode
© Alex Ufkes, 2020, 2021
62

Function Composition
In math, f ○ g means “f following g”. Same thing in Haskell.
© Alex Ufkes, 2020, 2021
63
Can be written as:

Lambda Functions
Like anonymous functions in Elixir:
Square as Lambda function
Lambda function with two args
© Alex Ufkes, 2020, 2021
64

Lambda Functions
They don’t need names!
Return True no matter what
Return opposite of input
Good for passing as arguments when that’s the only place you need them
© Alex Ufkes, 2020, 2021
65

Good for passing as arguments when that’s the only place you need them
Use with map, flip sign of list elements
© Alex Ufkes, 2020, 2021 66

Comments
About time we mentioned them…
© Alex Ufkes, 2020, 2021
67

Type Inference
Remember this error?
© Alex Ufkes, 2020, 2021
68

© Alex Ufkes, 2020, 2021
69
?

Type of chkClr is inferred:
• Takes as input a tuple with three values
o (a1, a2, a3)
• The type of each value in the tuple must
be instances of type class Eq and Num.
• The output of chkClr is a character list.
© Alex Ufkes, 2020, 2021 70

Type Inference
Based on the contents of chkClr:
• Haskell determined that the output is [Char]
• The input is a 3-tuple whose elements must
be instances of Num and Eq.
© Alex Ufkes, 2020, 2021
71

Specify Function Type
• chkAxis takes a pair-tuple of Floats as input, and returns the same as output.
• Instead of constants being of type Num or Fractional, they are treated as Floats
© Alex Ufkes, 2020, 2021
72

Specify Function Type
© Alex Ufkes, 2020, 2021
73

Thoughts?
© Alex Ufkes, 2020, 2021
74

?
Ord is a type class:
• When we didn’t explicitly define our types, Haskell inferred the type for us.
• Ord is a type class under which the operations used on our inputs are defined.
• I.e., comparison operators.
© Alex Ufkes, 2020, 2021
75

Type VS Type Class
• Ord is a type class, thus we specify that a is an instance of Ord
• cmp2 accepts two instances of Ord as arguments.
• Ord contains many different types, a can be any of them
• Int & Char are types, not type classes
• We can use the above notation
© Alex Ufkes, 2020, 2021
76

Ord Type Class
• Ord is a type class that supports comparison
• Comparison is all we’re doing in our function
• Thus, Haskell infers types as Ord
© Alex Ufkes, 2020, 2021
77

Ord Type Class
Int is an instance of Ord type class, so when we made our function args explicitly Int, we were OK
© Alex Ufkes, 2020, 2021
78

How About This?
© Alex Ufkes, 2020, 2021
79

© Alex Ufkes, 2020, 2021 80
Num type class does not define comparison!

Hmmmm…
Num doesn’t have comparison, Ord doesn’t have addition
It compiled and loaded, what type did Haskell infer for x and y?
© Alex Ufkes, 2020, 2021 81

Both!
• Whatever type we pass in (a), it must be an instance of both Ord and Num.
• Int is one such type, as is Float
© Alex Ufkes, 2020, 2021 82

Ord:
Num:
© Alex Ufkes, 2020, 2021 83

Custom Data Types
© Alex Ufkes, 2020, 2021 84

Custom Data Types
• Lists and tuples are already quite powerful for organizing data
• What if we want to add custom behaviors over our data?
• For example, we can declare a pair tuple (1, 2).
• What if we want to treat these as coordinates and compute
the sum? The dot product? Etc.?
• Addition is not defined for tuples, let alone more complicated
operations.
© Alex Ufkes, 2020, 2021 85

Custom Coordinate Types
data Pt3 = Pt3 Float Float Float
Keyword indicating a custom type definition
Constructor for our custom type. To construct a Pt3, we need 3 values of type Float
Custom type name
© Alex Ufkes, 2020, 2021 86

© Alex Ufkes, 2020, 2021 87

Custom Type Usage
Echoing a value in the interactive window requires its type to be an instance of Show!
© Alex Ufkes, 2020, 2021
88

• •
Hmmm…
The values contained in Pt3 are Float, and we know that Float is an instance of Show.
How can we access the individual elements of Pt3?
© Alex Ufkes, 2020, 2021
89

• Three access functions, one for each of the three values.
• Take as arguments Pt3 (and by extension its three members)
• Return x, y, or z coordinate respectively.
© Alex Ufkes, 2020, 2021 90

Overloading Constructor
• Define Pt3 with three parameters
• Define Pt2 with two parameters
• Name of our data type is now simply Pt,
because we have made it more generic.
There is now a problem with our access functions
© Alex Ufkes, 2020, 2021
91

There is now a problem with our access functions.
Now our access functions work for both Pt2 and Pt3
© Alex Ufkes, 2020, 2021 92

Deriving Show
© Alex Ufkes, 2020, 2021
93
Recall:

Deriving Show
Our custom type will inherit some default display behavior from Show
© Alex Ufkes, 2020, 2021
94

More Advanced Functions
Compute length of Pt2 and Pt3, treating them as vectors
© Alex Ufkes, 2020, 2021
95

Addition, Subtraction, Equality?
Let’s add more functions!
• We can very easily define addition as the sum of each respective X and Y coord
• Likewise for subtraction and equality.
© Alex Ufkes, 2020, 2021
96

Addition, Subtraction, Equality?
© Alex Ufkes, 2020, 2021
97

Addition, Subtraction, Equality?
This seems very clunky. Why can’t we simply add, subtract, or check equality with the symbolic operators (+, -, ==)?
We can! Equality is defined for instances of type class Eq +, -, etc. are defined for instances of type class Num.
How do we make Pt2 and Pt3 instances of another type class?
© Alex Ufkes, 2020, 2021 98

Custom Types & Type Classes
Define what it means for two Pt2 values to be considered equal
Declare Pt to be an instance of Eq
© Alex Ufkes, 2020, 2021
99

© Alex Ufkes, 2020, 2021 100

Minimal Definition
• The minimal definition for being an instance of Eq is == *OR* /= (not equal)
• We only defined ==
© Alex Ufkes, 2020, 2021
101

Haskell is clever enough to derive /= from our definition of ==, and vice versa.
© Alex Ufkes, 2020, 2021 102

Let’s Add /= Anyway
© Alex Ufkes, 2020, 2021
103

By The Way…
© Alex Ufkes, 2020, 2021
104
This should remind you of interfaces in Java
If you create a Java class that implements an interface, it must define all method signatures present in that interface
Most common is the Comparable interface
If our Java class implements Comparable, we must define some way of comparing two instances of our class

Instance of Num
© Alex Ufkes, 2020, 2021
105

• We’re only implementing for Pt2.
• Adding Pt3 follows the same pattern
© Alex Ufkes, 2020, 2021 106

Instance of Num
© Alex Ufkes, 2020, 2021
107

• This may look circular
• We’re using abs and signum in our
definition of abs and signum.
• However! x1 and y1 are Float.
• abs and signum are defined for Float
• We’re defining them for Pt2
© Alex Ufkes, 2020, 2021 108

• fromInteger is a coercion function.
• Dictates how our custom type can be
created from an Integer
• Takes an Integer, returns a Pt
• Lets us do this…
© Alex Ufkes, 2020, 2021 109

© Alex Ufkes, 2020, 2021 110
No more warnings!

© Alex Ufkes, 2020, 2021 111

Instance of Show
In Java-speak, define our own toString(), instead of deriving the default
• The minimal definition for Show is easy
• Need to implement show OR showsPrec
• Let’s do show
• Need to go from Pt2 to a String
© Alex Ufkes, 2020, 2021 112

No longer need to derive Show, we’ve made our own
• Use string concatenation to create a pleasing visual output for Pt2
• In doing so, we make use of show as defined for Floats
© Alex Ufkes, 2020, 2021 113

© Alex Ufkes, 2020, 2021 114

Haskell Tutorials/References:
https://en.wikibooks.org/wiki/Yet_Another_Haskell_Tutorial http://cheatsheet.codeslower.com/CheatSheet.pdf
© Alex Ufkes, 2020, 2021 115

© Alex Ufkes, 2020, 2021 116