CSCE 314 Lecture 7

« previous | Monday, September 12, 2011 | next »

Defining Functions

Lambda Expressions

Basic definitions of inline functions:

-- Lambda function to add two items together
\x y = x + y

Let Expressions

Creates a local scope within a function:

reserved s = 
    let keywords           = words "if then else for while"
        relops             = words "=== != < > <> <= >="
        elemInAny w []     = False
        elemInAny w (l:ls) = w `elem` l || elemInAny w ls
    in elemInAny s [keywords, relops]

unzip :: [(a,b)] ->  ([a], [b])
unzip []     = ([], [])
unzip ((a,b):rest) = 
    let (as, bs) = unzip rest
    in (a:as, b:bs)

Where Expressions

Identical to let, except the definitions come after the expression:

reserved s = elemInAny s [keywords, relops]
    where keywords           = words "if then else for while"
          relops             = words "=== != < > <> <= >="
          elemInAny w []     = False
          elemInAny w (l:ls) = w `elem` l || elemInAny w ls

Sections

Creates a lamda function with an operator

For any operator, put parentheses around it and pass in some arguments:

(x:) -- append x to something passed in
(+1) -- add 1 to something passed in
(3^) -- raise 3 to some power

List Comprehension

A convenient syntax for defining lists:

$\{(x^{2},y^{2})|x\in \{1,2,\ldots ,10\},y\in \{1,2,\ldots ,10\}\}$

can be defined in Haskell:

[ (x^2, y^2) | x <- [1..10], y <- [1..10] ]<code>

Where the <tt>x &lt;- [1..10] is a '''generator'''
* Generators can be infinite (<tt>take 3 [x | x <- [1..]]
* They can take values of previously defined generated variables (<tt>x &lt;- [1..3], y <- take x "abc"</tt>)

Predicates can be defined in list comprehensions, along with <tt>let</tt> statements and guards

<syntaxhighlight lang="haskell">factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

prime :: Int -> Bool
prime n = factors n == [1,n]

primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]

> primes 20
[2,3,5,7,11,13,17,19]

Recursion

There are no while loops or for loops in Haskell. The only way to express iteration is to do so recursively.

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

zip :: [a] -> [b] -> [(a,b)]
zip [] _          = []
zip _ []          = []
zip (x:xs) (y:ys) = (x, y) : zip xs ys

Performance

Recursive functions can be slow. Using tail recursion can help the compiler optimize performance

Stack overflow can occur if recursion goes too far

expensiveLen [] = 0
expensiveLen (_:xs) = 1 + expensiveLen xs

-- lazy evaluation prevents z+1 from being evaluated
stillNotCheapLen ls = len 0 ls
    where len z [] = z
          len z (_:xs) = len (z + 1) xs

cheapLen ls = len 0 ls
    where len z [] = z
          len z (_:xs) = let z' = z + 1
                         in z' `seq` len z' xs