Topics in Advanced Computing Lesson 7: More on Defining Types

1. Reading
   1. Questions?
2. Type Parameters
   1. Data.Map
   2. Vector
3. Deriving
4. Synonyms
5. Recursive Structures
   1. Lists
   2. Fixity?
   3. Trees
6. Instances
7. Defining Typeclasses
8. Functors
   1. Lists
   2. Maybes
   3. Trees

Reading

Up through Chapter 9.

Questions?

Type Parameters

Last time we saw the Maybe type.

data Maybe a = Nothing | Just a

The Maybe type constructor takes a parameter a, returns a type Maybe a.

Try out:

• :k Maybe
• Just "hello"
• :t Just "Hello"
• :t Nothing

The uncons function in the Data.List module returns a Maybe:

ghci> :m + Data.List
ghci> uncons [1, 2, 3] ghci> uncons []

By the way: how do we get the “values” of a function that is returned by a Maybe? There is a standard prelude function called maybe:

maybe :: b -> (a -> b) -> Maybe a -> b
maybe n _ Nothing = n
maybe _ f (Just x) = f x

Given a default value (n), a function (f), and a Maybe (m) this returns either n if m is nothing, or it returns f x if m is Just x.

Data.Map

We saw this last time too:

ghci> :m + Data.Map
ghci> :k Map
Map :: * -> * -> *
ghci> :t empty
empty :: Map k a
ghci> :t singleton “bob” (3::Int)
singleton “bob” (3::Int) :: Map String Int

Style note: this is allowed, but is bad form

data Ord k => Map k v = ...

That is: you’re allowed to add type class constraints to a type constructor, but this is considered bad form. Instead: we only add those constraints to specific functions that rely on those classes.

Vector

Example from the book

data Vector a = Vector a a a deriving (Show)

vplus :: (Num t) => Vector t -> Vector t -> Vector t
(Vector i j k) `vplus` (Vector l m n) = Vector (i+l) (j+m) (k+n)

rescale :: (Num t) => Vector t -> t -> Vector t
(Vector i j k) `rescale` m = Vector (i*m) (j*m) (k*m)

dotProduct :: (Num t) => Vector t -> Vector t -> t
(Vector i j k) `dotProduct` (Vector l m n) = i*l + j*m + k*n

Deriving

Can automatically derive Eq, Ord, Enum, Read, Show, etc.

Synonyms

Can introduce type aliases or synonyms:

type AssocList k v = [(k, v)]

lookup :: Eq k => k -> AssocList k v -> Maybe v
lookup _ [] = Nothing
lookup k ((x, v) : xs)
  | x == v = Just v
  | otherwise = lookup k xs

(Clearer implementation of the find function we did last time.)

Recursive Structures

Lists

What is a list? Recursively: it’s an element followed by another list (base case: empty list).

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

Or, as a record:

data List a = Empty | Cons { lHead :: a, lTail :: List a } deriving (Show, Read, Eq, Ord)

Play around:

ghci> 4 Cons (5 Cons Empty)

cons is the name of : operator (“construct” a new list). We can do something similar: to make a function automatically “infix”, we can define it with special characters:

infixr 5 :.
data List a = a :. List a | Empty deriving (Eq, Ord, Show, Read)

ghci> (3 :. 4 :. 5 :. Empty) :: List Int
3 :. (4 :. (5 :. Empty))

Fixity?

• Defining an operator, you can give it a fixity
• infixr: this is a right-associative infix operator.
• The number tells you the precedence. Can be from 1-9
  • Ex: ‘*’ is infixl 7 but ‘+’ is infixl 6.
  • Higher precedence binds more tightly.
  • Both of those are left-associative (why?)
  • Why should ours be right-associative?
• If you wanted a non-associative operator, you can use infix.

Trees

Let’s make a binary tree. Imperatively, we thiunk of a binary tree as containing a root node, which contains a data element, and (at most) two children: a left node and a right node. Declaratively: a tree is either an empty tree, or it has a root node which contains left and right subtrees.

data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Eq, Show, Read)

singleton :: a -> Tree a
singleton x = Node x Nil Nil

Let’s make it a binary search tree in fact. A BST is a tree that has the property: if $x < y$, then x appears on the left of y on the tree. How do we ensure this? When we insert, we check if the node we are inserting is less than the root. If it is, then put it on the left. If not, put it on the rigth:

insert :: Ord a => a -> Tree a -> Tree a
insert x Nil = singleton x -- base case
insert x n@(Node a left right)
  | x < a == Node a (insert x left) right
  | x > a == Node a left (insert x right)
  | otherwise = n

• Let’s play around with this.
• Exercise: implement a function that takes in an (unsorted) list and returns a BST. (Use a fold!)
• Exercise: implement a function that takes an element x and a Tree and returns True or False depending on whether x is an element of the tree.

member :: Ord a => a -> Tree a -> Bool
member _ _ = False -- change this

Instances

data AmPm = AM | PM deriving Show
data Time = Time { hour :: Int, minute :: Int, amPm :: AmPm }

instance Show Time where
    show (Time h m a)
      | m < 10 = show h ++ ":0" ++ show m ++ " " ++ show a
      | otherwise = show h ++ ":" ++ show m ++ " " ++ show a

Defining Typeclasses

Eq?

class Eq a where
  (==), (/=) :: a -> a -> Bool
  x /= y = not (x == y)
  x == y = not (x /= y)

ToBool:

class ToBool a where
  toBool :: a -> Bool

Implementation?

instance ToBool Bool where
  toBool = id

instance ToBool Int where
  toBool 0 = False -- C semantics
  toBool _ = True

instance ToBool [a] where
  toBool [] = False -- JS semantics
  toBool _ = True

instance ToBool (Maybe a) where
  toBool Nothing = False
  toBool (Just _) = True

Functors

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a

Aside: mathematical functors?

• Category: set of objects and morphisms (functions) between those objects.
• Functor: a mapping of categories: objects to objects and mappings to mappigns
  • …with the caveat that it preserves identity morphisms and commutes with compositions

Back to it:

• f is a type constructor that takes an argument (ex: Maybe)
• <$ has a default implementation: given an object of type a, replace all objects of type b with that constant object.
• Many default implementations of Functors: lists, Maybes, Eithers, tuples

Lists

instance Functor [] where
  fmap = map

How does this definition make sense?

Maybes

instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f Just x = ...

What do you think?

Trees

What about our tree type?

data Tree a = Nil | Node a (Tree a) (Tree a)

instance Functor Tree where
  fmap f Nil = Nil
  fmap f (Node a left right) = ...