Please work on the "homework1.hs" file to implement the functions by following instructions. You would need to submit the same file (.hs) with your solutions.
Grading Rubric:
-- 100%: works on all given examples AND general cases
03-types-and-typeclasses February 20, 2021 1 Types and Typeclasses 1.1 Believe the type 1.1.1 Static type system Haskell has a static type system. • The type of every expression is known at compile time, which leads to safer code. • If you write a program where you try to divide a boolean type with some number, it won’t even compile. • That’s good because it’s better to catch such errors at compile time instead of having your program crash. • Everything in Haskell has a type, so the compiler can reason quite a lot about your program before compiling it. 1.1.2 Type inference Unlike Java or Pascal, Haskell has type inference. • It can infer that on its own, so we don’t have to explicitly write out the types of our functions and expressions to get things done. Understanding the type system is a very important part of learning Haskell. • A type is a kind of label that every expression has. • It tells us in which category of things that expression fits. • The expression True is a boolean, "hello" is a string, etc. Jupyter Note: We’ll turn off the automatic linting for IHaskell first. [1]: :opt no-lint 1.1.3 Examine the types of some expressions We’ll do that by using the :t command which, followed by any valid expression, tells us its type. [2]: :t 'a' 'a' :: Char [3]: :t True 1 https://hackage.haskell.org/package/base/docs/Prelude.html#v:True https://github.com/gibiansky/IHaskell/wiki#opt-no-lint True :: Bool [4]: :t "HELLO!" "HELLO!" :: [Char] [5]: :t (True, 'a') (True, 'a') :: (Bool, Char) [6]: :t 4 == 5 4 == 5 :: Bool 1.1.4 Types Expression Types • :: is read as “has type of”. • Explicit types are always denoted with the first letter in capital case. – 'a', as it would seem, has a type of Char, which stands for character. – True is of a Bool type. – Examining the type of "HELLO!" yields a [Char]. The square brackets denote a list. • Unlike lists, each tuple length has its own type. – So the expression of (True, 'a') has a type of (Bool, Char), – an expression such as ('a','b','c') would have the type of (Char, Char, Char). • 4 == 5 will always return False, so its type is Bool. Function Types • Functions also have types. • When writing our own functions, we can choose to give them an explicit type declaration. • From here on, we’ll give all the functions that we make type declarations. [7]: removeNonUppercase :: [Char] -> [Char] removeNonUppercase st = [ c | c <- st,="" c="" `elem`="" ['a'..'z']="" ]="" removenonuppercase="" "abc123agc"="" "agc"="" •="" removenonuppercase="" has="" a="" type="" of="" [char]="" -=""> [Char], meaning that it maps from a string to a string. • It takes one string as a parameter and returns another as a result. • The [Char] type is synonymous with String so it’s clearer if we write removeNonUppercase :: String -> String. • We didn’t have to give this function a type declaration because the compiler can infer by itself that it’s a function from a string to a string but we did anyway. Function with multiple parameters But how do we write out the type of a function that takes several parameters? 2 https://hackage.haskell.org/package/base/docs/Prelude.html#t:Char https://hackage.haskell.org/package/base/docs/Prelude.html#v:True https://hackage.haskell.org/package/base/docs/Prelude.html#t:Bool https://hackage.haskell.org/package/base/docs/Prelude.html#v:False https://hackage.haskell.org/package/base/docs/Prelude.html#t:Bool https://hackage.haskell.org/package/base/docs/Prelude.html#t:String [8]: addThree :: Int -> Int -> Int -> Int -- addThree :: Int, Int, Int -> Int -- wrong addThree x y z = x + y + z [9]: addThree 1 2 3 6 [10]: addTreeFortwo = addThree 1 [11]: addTreeFortwo 2 3 6 [12]: :t (+) (+) :: forall a. Num a => a -> a -> a • The parameters are separated with -> and there’s no special distinction between the param- eters and the return type. • The return type is the last item in the declaration and the parameters are the first three. Check funtion types If you want to give your function a type declaration but are unsure as to what it should be, * Functions are expressions too, so :t works on them without a problem. [13]: :t take take :: forall a. Int -> [a] -> [a] [14]: take 2 [1..10] [1,2] 1.1.5 Common types Here’s an overview of some common types. Int • Int stands for integer. – It’s used for whole numbers. 7 can be an Int but 7.2 cannot. – Int is bounded, which means that it has a minimum and a maximum value. Usually on 32-bit machines the maximum possible Int is 2147483647 and the minimum is - 2147483648. • Integer stands for also integer. – The main difference is that it’s not bounded so it can be used to represent really really big numbers. – Int, however, is more efficient. [15]: factorial :: Integer -> Integer factorial n = product [1..n] -- 1*2*3*..*n 3 https://hackage.haskell.org/package/base/docs/Prelude.html#t:Int https://hackage.haskell.org/package/base/docs/Prelude.html#t:Int https://hackage.haskell.org/package/base/docs/Prelude.html#t:Int https://hackage.haskell.org/package/base/docs/Prelude.html#t:Int https://hackage.haskell.org/package/base/docs/Prelude.html#t:Integer https://hackage.haskell.org/package/base/docs/Prelude.html#t:Int [16]: factorial 50 30414093201713378043612608166064768844377641568960512000000000000 Float Float is a real floating point with single precision. [17]: circumference :: Float -> Float circumference r = 2 * pi * r [18]: circumference 4.0 25.132742 Double Double is a real floating point with double the precision! [19]: circumference' :: Double -> Double circumference' r = 2 * pi * r [20]: circumference' 4.0 25.132741228718345 Bool Bool is a boolean type. It can have only two values: True and False. Char Char represents a character. It’s denoted by single quotes. A list of characters is a string. Tuple • Tuples are types but they are dependent on their length as well as the types of their compo- nents, • so there is theoretically an infinite number of tuple types. • Note that the empty tuple () is also a type which can only have a single value: () [21]: :t (12,'a',"a",[1..2], [[1],[2]]) (12,'a',"a",[1..2], [[1],[2]]) :: forall a1 a2 a3. (Enum a1, Num a2, Num a1, Num␣ ↪→a3) => (a2, Char, [Char], [a1], [[a3]]) 1.2 Type variables Because head takes a list of any type and returns the first element, so what could it be? [22]: fun :: (Integral a) => a -> a-> a -> [a] fun x y z = [x,y,z] [23]: fun 1 2 3 [1,2,3] [24]: -- fun :: (Int a) => a -> a-> a -> [a] -- wrong fun x y z = [x,y,z] 4 https://hackage.haskell.org/package/base/docs/Prelude.html#t:Float https://hackage.haskell.org/package/base/docs/Prelude.html#t:Double https://hackage.haskell.org/package/base/docs/Prelude.html#t:Bool https://hackage.haskell.org/package/base/docs/Prelude.html#v:True https://hackage.haskell.org/package/base/docs/Prelude.html#v:False https://hackage.haskell.org/package/base/docs/Prelude.html#t:Char https://hackage.haskell.org/package/base/docs/Prelude.html#v:head 1.2.1 Type variable Hmmm! What is this a? Is it a type? • types are written in capital case, so it can’t exactly be a type. • it’s actually a type variable. That means that a can be of any type. • This is much like generics in other languages, only in Haskell it’s much more powerful because it allows us to easily write very general functions if they don’t use any specific behavior of the types. • Functions that have type variables are called polymorphic functions. 1.2.2 Type variable examples Although type variables can have names longer than one character, we usually give them names of a, b, c, d … The type declaration of head states that it takes a list of any type and returns one element of that type. [25]: :t head head :: forall a. [a] -> a [26]: :t fst fst :: forall a b. (a, b) -> a • fst takes a tuple which contains two types and returns an element which is of the same type as the pair’s first component. • That’s why we can use fst on a pair that contains any two types. • Note that just because a and b are different type variables, they don’t have to be different types. It just states that the first component’s type and the return value’s type are the same. 1.3 Typeclasses 101 • A typeclass is a sort of interface that defines some behavior. • If a type is a part of a typeclass, that means that it supports and implements the behavior the typeclass describes. • Typeclasses are NOT like classes in object oriented languages. They are like Java interfaces. 1.3.1 Eq typeclass What’s the type signature of the == function? [27]: :t (==) (==) :: forall a. Eq a => a -> a -> Bool [28]: (==) 2 3 False [29]: (+) 2 3 5 https://hackage.haskell.org/package/base/docs/Prelude.html#v:head https://hackage.haskell.org/package/base/docs/Prelude.html#v:fst https://hackage.haskell.org/package/base/docs/Prelude.html#v:fst https://hackage.haskell.org/package/base/docs/Prelude.html#v:-61--61- 5 Note: • the equality operator, == is a function. • So are +, *, -, / and pretty much all operators. • If a function is comprised only of special characters, it’s considered an infix function by default. • If we want to examine its type, pass it to another function or call it as a prefix function, we have to surround it in parentheses. [30]: :t (==) (==) :: forall a. Eq a => a -> a -> Bool • Everything before the => symbol is called a class constraint. • It reads like this: the equality function takes any two values that are of the same type and returns a Bool. ### Eq typeclass cont’ed • The type of those two values must be a member of the Eq class (this was the class constraint). • The Eq typeclass provides an interface for testing for equality. • Any type where it makes sense to test for equality between two values of that type should be a member of the Eq class. • All standard Haskell types except for IO (the type for dealing with input and output) and functions are a part of the Eq typeclass. • The elem function has a type of (Eq a) => a -> [a] -> Bool because it uses == over a list to check whether some value we’re looking for is in it. 1.3.2 Some basic typeclasses Eq • Eq is used for types that support equality testing. • The functions its members implement are == and /=. • So if there’s an Eq class constraint for a type variable in a function, it uses == or /= somewhere inside its definition. • All the types we mentioned previously except for functions are part of Eq, so they can be tested for equality. [31]: 5 == 5 True [32]: 5 /= 5 -- 5 \= 5 False [33]: 'a' == 'a' True [34]: "Ho Ho" == "Ho Ho" True 6 https://hackage.haskell.org/package/base/docs/Prelude.html#v:-61--61- https://hackage.haskell.org/package/base/docs/Prelude.html#v:-43- https://hackage.haskell.org/package/base/docs/Prelude.html#v:-42- https://hackage.haskell.org/package/base/docs/Prelude.html#v:-45- https://hackage.haskell.org/package/base/docs/Prelude.html#v:-47- https://hackage.haskell