FP101x - week 5 Recursive Functions


factorial 4
= product [1..4]
= product [1,2,3,4]
= 1*2*3*4

Recursive Function

factorial 3
= 3 * factorial 2
= 3 * ( 2 * factorial 1)
= 3 * ( 2 * ( 1 * factorial 0 ) )
= 3 * ( 2 * ( 1 * 1 ) )
= 3 * ( 2 * 1 )
= 3 * 2
= 6

why

Recursion of Lists

product :: [Int] -> Int
product [] = 1
product (n:ns) = n * product ns
product [2,3,4]
= 2 * product [3,4]
= 2 * ( 3 * product [4])
= 2 * ( 3 * ( 4 * product [] ) )
= 2 * ( 3 * ( 4 * 1 ) )
= 24

ex ) function length

length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
length [ 1 , 2 , 3 ]
= 1 + length [ 2 , 3 ]
= 1 + ( 1 + length [ 3 ] )
= 1 + ( 1 + ( 1 + length [ ] )
= 1 + ( 1 + ( 1 + ( 1 + 0 ) )
= 3

ex ) reverse

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
reverse [1,2,3]
= reverse [2,3] ++ [1]
= ( reverse [3] ++ [2] ) ++ [1]
= ( (reverse [] ++ [3] ) ++ [2] ) ++ [1]
= ( ([] ++ [3] ) ++ [2] ) ++ [1]
= [3,2,1]

Multiple Arguments

zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys  = x : (xs ++ ys)

Quicksort

qsort :: [Int] -> [Int]
qsort [] = []
qsort ( x : xs ) =
     sort smaller ++ [x] ++ sort larger
     where
          smaller = [ a | a <- xs, x <= x]
          larger = [ b | b <- xs, b > x ]
q [ 3,2,4,1,5 ]
q  [2,1] ++ [3] ++ q [4,5]
q[1] ++ [2] ++ q[] ++ [3] ++ q[] ++ [4] ++ q[5]
[1] ++ [2] ++ [] ++ [3] ++ [] ++ [4] ++ [5]
replicate :: Int -> a -> [a]
(!!) :: [a] -> Int -> a
elem :: Eq a => a -> [a] -> Bool