Warmup & Review

Warmup: Desugaring

Rewrite this code in desugared form (i.e., the lambda calculus) with all the implicit parentheses we used last week and no use of infix operators.

• twice x = x + x
• more y = twice y+y
• map f list
• 1 : [2,3]
• f a b+g c d

Warmup: Valid or Invalid

For each piece of code (expression or declaration), is it okay, or is it nonsensical in some way (if it doesn't make sense, what is wrong?)

• 1 + 1
• 1 +
• Int + 1
• test1 :: Int -> Int -> Bool
• test2 :: Int -> 3 -> Bool
• test3 :: True -> False -> True
• f 0 = 0
• f Int = 0
• g [] = True
• g h:t = False

Additional Examples:

• ('2', True)
• ['2', True]

Wiki Extra: Guards, if and case statements

In this bonus material, we'll play with the factorial function!

Some neat ways to write the factorial function include

fact n = product [1..n]

fact n = foldr (*) 1 [1..n]

fact n = foldr1 (*) [1..n]

You may want to look at the type of foldr and foldr1 to see how these work.

But normally we're write factorial recursively, like this:

fact 0 = 1
fact n = n * fact (n-1)

This uses pattern matching. It's basically syntactic sugar for a case statement like this

fact n = case n of 0 -> 1
                   _ -> n * fact (n-1)

Generally, we like pattern matching over if statements, but we could use an if statement like this:

fact n = if n < 1 then 1
                  else n * fact (n-1)

But a nicer notation than an if is often to use guard syntax:

fact n | n < 1       = 1
       | otherwise   = n * fact (n-1)

If you look on-line, people will often show guards with multiple clauses ending with otherwise (which is just the same as True), but you can just have one clause. If none of the guards are true, matching proceeds with the next pattern, so we could write the base case last like this:

fact n | n >= 1    = n * fact (n-1)
fact _             = 1

Here's a better example of a guard without an otherwise:

commonPrefix (x:xs) (y:ys) | x == y   = x :: commonPrefix xs ys
commonPrefix _      _                 = []

commonPrefix (x:xs) (y:ys) = if x == y then x :: commonPrefix xs ys
                                       else []
commonPrefix _      _      = []

Types & Typeclasses

What's the Type?

1. 'c'
2. True
3. [True,False]
4. ('c', True, GT)
5. "Hello"
6. ['h','e','l','l','o']
7. \x -> x ++ " World"
8. \x -> x
9. \x -> \y -> (x,y)
10. \x -> \y -> [x,y]
11. \x -> \y -> x == y
12. \x -> "--> " ++ show x
13. \x -> x+1
14. 42

Class Notes:

Values, Types, and Typeclasses

In Haskell, Values are instances of Types. This relationship is similar to set membership where the values are members of types. Example values include:

• 'c'
• True
• GT (and LT and EQ)
• [True, False]
• "Hello"
• 42

The Types of these values, respectively, are:

• Char
• Bool
• Ordering
• [Bool]
• [Char]
• At this point, we cannot know, as there are many types that encode numerical values. You can give this value an explicit type by writing 42 :: Integer instead.

Above Types, there are Typeclasses. These are detailed in the next section, and help by grouping types by which operations can be performed on them. For instance, by writing the function \x -> \y -> x < y, Haskell knows that x and y must be values of the same type, which is part of the Ord Typeclass (which contains all types which have a defined method of comparison).

Haskell's families of types — Typeclasses

Recall that values have types. Types belong to type classes.

• Eq defines the == and /= operators
• Ord defines comparison operators, such as <
  • Note that any type in Ord must also be in Eq
• Bounded defines minBound and maxBound, so for instance, minBound :: Int gives -2147483648
• Enum defines the succ and pred operators, and also allows a type to be used in list ranges
• Read defines the read operator which turns a String into a value
  • Note that Haskell needs to be able to infer what the resulting type should be, so something like read "4" + 2 or (read "4") :: Int will work, but simply read "4" will not.
• Show defines the show operator which turns a value into a String.
• Num defines +, -, /, etc...

Haskell's data Declarations

Haskell is not an object oriented language, so there are no classes, but rather types and type classes.

Some types are predefined like Bool and Ordering, but there's nothing really special about these types. Here are their type signatures:

data Bool = False | True

data Ordering  =  LT | EQ | GT 

Here Bool and Ordering are types and False, True, LT, EQ, and GT are values.

Note: Ordering is a type while Ord is a typeclass. They are not the same thing!

Defining Our Own Types

We are able to define our own types by using data declarations.

data CoinFlip = Heads | Tails

data Suit = Clubs | Diamonds | Hearts | Spades

data ThermostatSetting = Off 
                       | Cooling 
                       | Heating

These newly defined types will not belong to any typeclasses, such as Eq or Show, even though you will be able to use them as literal constants in expressions and pattern matching. You might also think you can “see them” when you use :t on an expression (because it just prints what you typed and so it looks like it's printing out values of the type even though it isn't). To get Haskell to include the corresponding "obvious" definitions of == and show, you use deriving, as shown below.

If you wanted make sure Bool could be used where things of the Show type class are used, we could define show for the type Bool.

instance Show Bool where
  show :: Bool -> String
  show True = "True"
  show False = "False"

Similarly, here is how you would define the == operator on Bools.

instance Eq Bool where
  (==) :: Bool -> Bool -> Bool
  (==) True  True  = True
  (==) False False = True
  (==) _     _     = False

Sometimes, you can have Haskell logically write functions that allow a type to be in an existing type class by using deriving (...). Here are some examples of type declarations:

data Bool = False | True
       deriving (Eq, Ord, Bounded, Enum, Read, Show)

data Ordering  =  LT | EQ | GT 
       deriving (Eq, Ord, Bounded, Enum, Read, Show)

data CoinFlip = Heads | Tails
       deriving (Show, Eq, Ord)

data Suit = Clubs | Diamonds | Hearts | Spades
       deriving (Show, Eq, Ord)

data ThermostatSetting = Off 
                       | Cooling 
                       | Heating
       deriving (Show, Eq, Ord)

You can also give different names to types that already exist. For example, you can say that Strings are the same as [Char]. Then, if you input :info String into ghci, you will get type String = [Char]. However, ghci will still identify "Hello" and other strings as [Char].

When using this method to derive Ord, the ordering is determined by the order in which the possible values are written. For example, when we write a new type as such:

data Mystery = A | B
       deriving (Eq, Ord)

The comparison A < B will return True.

Using a type

data ThermostatSetting = Off 
                       | Cooling 
                       | Heating
       deriving (Show, Eq, Ord)

Let's define isRunning :: ThermostatSetting -> Bool

isRunning Off = False
isRunning Heating = True
isRunning Cooling = True

isRunning Off = False
isRunning othermode = True

isRunning Off = False
isRunning _   = True

Associated Values

data ThermostatSetting = Off 
                       | CoolTo Int 
                       | HeatTo Int
                       | OutOfService String
       deriving (Show, Eq, Ord)

Let's define isRunning :: Int -> ThermostatSetting -> Bool

isRunning _ Off              = False
isRunning _ (OutOfService _) = False
isRunning temp (CoolTo t)    = temp > t
isRunning temp (HeatTo t)    = temp < t

data Crayon = Red | Orange | Yellow | Green 
            | Blue | Purple | Black | White
            | RGB  Int Int Int
       deriving (Show, Ord, Eq)

data Complex = Rect   Float Float
             | Polar  Float Float
       deriving (Show)

Note that in the case of Complex, we don't want to use the default implementations of == or <, because we need to do some actual math to compare rectangular and polar coordinates. Thus we don't use deriving for Eq or Ord.

Associated values should look totally new to you, unless you've worked with something like Swift (enums with associated values), Pascal (variant records/variants), Rust (discriminated/tagged unions), or ML.

C and C++ have a construct that is similar in that it can store one of several data types (union), however, it lacks the "tag" that lets us know which type we have. Associated values can be used by either creating a custom datatype or using the visitor design pattern.

Recursive Types

data ListOfInt = Nil 
               | Cons Int ListOfInt
       deriving (Show, Eq, Ord)

Let's define ihead :: ListOfInt -> Int

ihead Nil = error "empty"
ihead (Cons e _) = e

Recursive Types with Parameters

data ListOf a  = Nil 
               | Cons a (ListOf a)
       deriving (Show, Eq, Ord)

Let's define phead :: ListOf a -> a

phead Nil = error "empty"
phead (Cons e _) = e

Haskell's Built-in List Type

data [a]       = [] 
               | a : [a]
       deriving (Show, Eq, Ord)

Let's define head :: [a] -> a

head [] = error "empty"
head (e : _) = e

-- MelissaONeill - 05 Feb 2020