CS240h: Functional systems in Haskell

Why Haskell?

Why take CS240h?

Administrivia

Final project

Getting started with Haskell

Bindings

Haskell is a pure functional language

How to program without mutable variables?

Tail recursion

Guards and where clauses

Tip: variable names

Every expression and binding has a type

More on types

User-defined data types

Using data types

Parameterized types

More deconstruction tips

Lists

Some basic list functions in Prelude

head :: [a] -> a
head (x:_) = x
head [] = error "head: empty list"
tail :: [a] -> a             -- all but first element
tail (_:xs) = xs
tail [] = error "tail: empty list"
a ++ b :: [a] -> [a] -> [a]  -- infix operator concatenate lists
[] ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys
length :: [a] -> Int         -- This code is from language spec
length [] = 0 -- GHC implements differently, why?
length (_:l) = 1 + length l
filter :: (a -> Bool) -> [a] -> [a]
filter pred [] = []
filter pred (x:xs)
| pred x = x : filter pred xs
| otherwise = filter pred xs

Note function error :: String -> a reports assertion failures

Hoogle

Example: counting letters

Function composition

Lambda abstraction

Infix vs. Prefix notation

Fixity

Fixity of specific operators

infixl 9  !!             -- This is the default when fixity unspecified
infixr 9 .
infixr 8 ^, ^^, ⋆⋆
infixl 7 ⋆, /, `quot`, `rem`, `div`, `mod`
infixl 6 +, - -- Unary negation "-" has this fixity, too
infixr 5 ++ -- built-in ":" constructor has this fixity, too
infix 4 ==, /=, <, <=, >=, >, `elem`, `notElem`
infixr 3 &&
infixr 2 ||
infixl 1 >>, >>=
infixr 1 =<<
infixr 0 $, $!, `seq`

The "infixr 0" operators

Accumulators revisited

factorial n0 = loop 1 n0
where loop acc n | n > 1 = loop (acc * n) (n - 1)
| otherwise = acc
factorial n0 = loop 1 n0
where loop acc n | n > 1 = (loop $! acc * n) (n - 1)
| otherwise = acc
factorial n0 = loop 1 n0
where loop acc n | n > 1 = acc `seq` loop (acc * n) (n - 1)
| otherwise = acc

Hackage and cabal

Modules and import syntax

do notation

main = do
(url:_) <- getArgs -- Sets url to first command-line argument
page <- simpleHttp url -- Sets page to contents as a ByteString
putStr (L.toString page) -- Converts ByteString to String and prints it

What are the types of IO actions?

main :: IO ()
getArgs :: IO [String]
simpleHttp :: String -> IO L.ByteString -- (really more polymorphic)
putStr :: String -> IO ()

Another way to see IO [Peyton Jones]

do page <- simpleHttp url
putStr (L.toString page)

Another way to see IO [Peyton Jones]

do page <- simpleHttp url
putStr (L.toString page)

Running urldump

$ ghc --make urldump
[1 of 1] Compiling Main             ( urldump.hs, urldump.o )
Linking urldump ...
$ ./urldump http://www.scs.stanford.edu/
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
...

The return function

Point-free IO composition

Lazy IO

More on polymorphism

id :: a -> a
id x = x
const :: a -> b -> a
const a _ = a
fst :: (a, b) -> a
fst (a, _) = a
snd :: (a, b) -> b
snd (_, b) = b
print a = putStrLn (show a)   -- what's the type?  a -> IO ()?
show a = ???                  -- how to implement?

Parametric vs. ad hoc polymorphism

Classes and Instances

The Context of a type declaration

The Dreaded Monomorphism Restriction (DMR)

The DMR continued

The DMR take-away message

Superclasses and instance contexts

Classes of parameterized types

More Functors

Kinds

The Monad class

class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
fail :: String -> m a -- called when pattern binding fails
fail s = error s -- default is to throw exception

(>>) :: m a -> m b -> m a
m >> k = m >>= \_ -> k

The Maybe monad

Algebraic data types

Algebraic types - initialization and matching

data Point = Point { xCoord :: Double, yCoord :: Double }

Algebraic types - access and update

A few Miscellaneous points