CSCE 314 Lecture 8

« previous | Wednesday, September 14, 2011 | next »

Recursion

Many repeating patterns:

product []     = 1
product (n:ns) = n * product ns

sum []     = 0
sum (n:ns) = n + sum ns

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

This pattern is captured in the higher order functions foldr and foldl. The only difference between them is that foldr is right-associative in its recursion and foldl is left-associative.

foldr :: (a -> b -> b) -> b -> a -> b
foldr f v []     = v
foldr f v (x:xs) = f x (foldr f v xs)

foldl :: (a -> b -> b) -> b -> a -> b
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

-- the functions above can be redefined as
product ls = foldr (*) 1 ls
sum ls = foldr (+) 0 ls
length ls = foldr (\_ n -> 1 + n) 0 ls

Composition

Uses the . operator:

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

Identical to mathematical definition:

$(f\circ g)(x)=f(g(x))$

Standalone Script

module Main where

import Char



hello :: IO ()
hello = 
    do
        putStr "Hello, "
        putStrLn "World!"
        str <- getLine
        let uc = map Char.toUpper str
        putStrLn uc

main :: IO ()
main = hello