Declarative Programming

Real World Haskell

menu_book

Real World Haskell

Table of Contents

Getting started

Types and Functions

Comment on Purity

Type constructors

[] and (,) are type constructors: they take types as input and build new types from them

Strings

String in Haskell is a type synonym with [Char]

Defining type synonyms

type Pair = (Int, Int)

Type Classes

e.g. for sum:

Num a => [a] -> a`

Type Definitions

Define a new type with the data keyword. Possible values are separated by |

-- e.g. our own implementation of Bool
data MyBool = MyTrue | My Falsek

-- e.g. point to store 2D Cartesian coordinates
data Point = Pt Float Float

Here we have defined a Point, which can be a Pt which also carries two Floats

Typically, you use the same name for the type and data constructor:

data Point = Point Float Float

newtype

Comparison of type, newtype, data

Recursive Data Types

e.g. implementation of linked list: here’s a type List, which can be a ListNode carrying with it an Int, and another List value. Otherwise, it can be a ListEnd (just a constant)

data List = ListNode Int List | ListEnd

To make this polymorphic with respect to type, introduce type parameter a:

data List a = ListNode a (List a) | ListEnd

Now List is a type constructor, rather than a type. To get a type, you need to provide List with the type to use, e.g. List Int.

Defining operations on custom types

data List a = ListNode a (List a) | ListEnd
    deriving (Eq, Show)

Binary Tree

data Tree a = Node a (Tree a) (Tree a) | Empty
    deriving Show

tree :: Tree Int
data Tree a = Node a (Tree a) (Tree a) | Empty
    deriving Show

-- returns contents of a tree
elements :: Tree a -> [a]
elements Empty = []
elements (Node x l r) = elements l ++ [x] ++ elements r

-- insert element into binary search tree
insert n Empty = (Node n Empty Empty)
insert n (Node x l r)
    | n == x = (Node x l r)
    | n <= x = (Node x (insert n l) r)
    | n > x = (Node x l (insert n r))

-- build a binary search tree from list of values
buildtree :: Ord a => [a] -> Tree a
buildtree [] = Empty
buildtree [x] = insert x Empty
buildtree (x:xs) = insert x (buildtree xs)


-- build a BST then return sorted values
treesort :: (Ord a) => [a] -> [a]
treesort [] = []
treesort x = elements (buildtree x)

List Comprehension

[ expression | generator ]

> [x^2 | x<- [1..6]]
[1,4,9,16,25,36]

> [(-x) | x <- [1..6]]
[-1,-2,-3,-4,-5,-6]

> [even x | x <- [1..6]]
[False,True,False,True,False,True]

> [x^2 | x <- [1..12], even x]
[4, 16, 36, 64, 100, 144]

[ x | x <- [1..4], y <- [x..5], even (x+y) ]

pyth :: [(Integer,Integer,Integer)]
pyth = [(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c], a^2 + b^2 == c^2]

Output:

Prelude> take 5 pyth
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13)]

zip

zip xs ys: returns a list of pairs of elements (x, y)

> zip [1,2,3,4] [5,6,7,8]
[(1,5), (2,6), (3,7), (4,8)]

dot xs ys = sum [x*y | (x, y) <- zip xs ys]

Modules

module Module.Name
where

Lazy evaluation

You can think of execution in a pure functional language as evaluation by rewriting through substitution

e.g. with the following definitions:

f x y = x + 2*y
g x = x^2

You can evaluate the following by applicative order/call by value, rewriting the expression at the innermost level first:

g (f 1 2) 
= g (1 + 2*2) -- use f's definition
= g (1 + 4) 
= g 5 
= 5^2         -- use g's definition
= 25

Alternatively, you can evaluate it using normal order/call by name, where you pass an un-evaluated expression, rewriting the outermoost level first:

g (f 1 2) 
= (f 1 2)^2   -- use g's definition
= (1 + 2*2)^2 -- use f's definition
= (1 + 4)^2
= 5^2
= 25

Haskell uses normal order evaluation, unlike most programming languages. This will always produce the same value as applicative order evaluation, but sometimes produces a value when applicative order evaluation would fail to terminate (e.g. asking for a result on an infinite list).

Haskell uses call by need: a function’s argument is evaluated at most once if needed, otherwise never. This evaluation isn’t all-or-nothing: Haskell is lazy in that it only evaluates on demand. This allows Haskell to operate on infinite data structures: data constructors are simply functions that are also lazy (e.g. cons :)

e.g. take 3 [1..] evaluates to [1,2,3]

Infinite Lists

Here is an efficient Fibonacci implementation that uses a recursive definition of the infinite sequence as fibs:

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

fib n = fibs !! n

Here’s another example for an infinite sequence of powers of 2:

powers :: [Integer]
powers = 1 : map (*2) powers

What drives evaluation?

-- zipWith takes a 2-argument function and 2 lists and applies the function element-wise across the lists
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

Let’s consider how Haskell evaluates zipWidth f e1 e2:

Sieve of Eratosthenes

Algorithm for computing primes:

  1. write out list of integers [2..]
  2. put the list’s first number p aside
  3. remove all multiples of p from the list
  4. repeat from step 2

This works with infinite lists, removing an infinite number of multiples. Haskell can evaluate using it:

primes :: [Integer]
primes = sieve [2..]
  where sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]

Now you can generate lists of primes rapidly:

*Main> take 100 primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

I/O and Monads

To preserve purity in computation, Haskell:

Input Actions

Input returns a value. Something of type IO a is an input/output action which returns a result of type a to the caller.

getChar :: IO Char

Output Actions

Output actions have type IO (), an instance of a monad.

putChar :: Char -> IO ()
print :: Show a => a -> IO ()

(>>) :: IO () -> IO () -> IO ()

File I/O

type FilePath = String
readFile :: FilePath -> IO String
writeFile :: FilePath -> String -> IO ()
appendFile :: FilePath -> String -> IO ()

Binding and Sequencing

-- bind: pass result of first action to the next
(>>=) :: IO a -> (a -> IO b) -> IO b
-- sequence: second action doesn't care about result of the first action
(>>) :: IO a -> IO b -> IO b
return :: a -> IO b

Lambda abstraction for f: \x -> f x function that takes an argument x and return f x

>> is defined in terms of >>=:

m >> k = m >>= \_ -> k

e.g. read an input file and write to an output file, excluding non-ASCII characters:

main
  = readFile "inp" >>= \s ->
    writeFile "outp" (filter isAscii s) >>
    putStr "Filtering successful\n"

Do

Syntactic sugar time: write things under do

action1 >>= \x -> action2 using x

becomes:

x <- action1
action2 using x

action1 >> action2

becomes:

action1
action2

e.g. purely functional code that asks user for input, reads/writes a file, writes to standard out

import Data.Char(isAscii)

main
  = do
    putStr "Input file: "
    ifile <- getLine
    putStr "Output flie: "
    ofile <- getLine
    s <- readFile ifile
    writeFile ofile (filter isAscii s)
    putStrLn "All done"

Partial Application and Currying

Kind

Functors

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

Mapping over an IO action:

instance Functor IO where
  fmap f action = do
      -- get a result from the IO action
      result <- action
      -- inject the value of the function applied to the result
      return (f result)

Mapping over Maybe

-- lookup will return a Maybe Int
fmap sum (Map.lookup student marks)

Functions as Functors

instance Functor ((->) r) where
  fmap f g = (\x -> f (g x))

instance Functor ((->) r) where
  fmap = (.)

fmap perspectives

You can consider fmap in 2 ways:

Functor Laws

When you define a functor, you need to check that it conforms to the expected properties for it to be well-behaved:

Applicative Functors

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

    -- c.f. fmap :: (a -> b) -> f a -> f b

> (++) <$> ["a", "b", "c"] <*> ["1", "2"]
["a1", "a2", "b1", "b2", "c1", "c2"]

Maybe

instance Applicative Maybe where
  -- to wrap it in an applicative value, we use Just (the value constructor)
  pure = Just
  -- can't extract a function from Nothing
  Nothing <*> _ = Nothing
  -- pull out the function, and apply it to the functor something with fmap
  (Just f) <*> something = fmap f something

Applicative Style

> pure (+) <*> Just 3 <*> Just 5
Just 8

Lists

instance Applicative [] where
  -- pure inserts a value into a minimal context yielding the value, i.e. a singleton
  pure x = [x]
  -- applies functions in the list on the lhs to all values on the rhs
  fs <*> xs = [f x | f <- fs, x <-xs]

[ x*y | x <- [2,5,10], y <- [8,10,11]]
(*) <$> [2,5,10] <*> [8,10,11]

IO

instance Applicative IO where
    -- inject a value into a minimal context that still holds the value with return
    pure = return
    -- takes IO action a, which gives a function
    a <*> b = do 
        -- perform the function, bind the result to f
        f <- a
        -- perform b and bind the result to x
        x <- b
        -- apply f to x and yield that as the result
        return (f x)

Functions (->) r

> (+) <$> (+3) <*> (*100) $ 5
508

Monoid Type Class

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty

Lists

instance Monoid [a]
    mempty = []
    mappend = (++)

Boolean: Any and All

Edit this page.