infinite lists

Question 1

Fibonacci of n

fib::Int->Int

Answer 1

fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = (fib n-2) + (fib n-1)

Question 2

quicksort

qsort::Ord a => [a] -> [a]

Answer 2

qsort::Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
where 
smaller = [a | a ← xs, a <= x]
larger = [b | b ← xs, b > x]

Question 3

reverse

reverse::[a] -> [a]

Answer 3

reverse::[a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

or

reverse = foldr (\x xs -> xs ++ [x]) []

Question 4

find (dictonary)

find::Eq a => a -> [(a,b)] -> [b]

Answer 4

find::Eq a => a -> [(a,b)] -> [b]

find k t = [v | (k’,v) ← t, k’ == k]

Question 5

factors (all factors of a number from 1 to n)

factors:: Int -> [Int]

Answer 5

factors:: Int -> [Int]

factors n = [x | x ← [1..n], n mod x == 0]

Question 6

rotate (move n letters from front to back)

rotate:: Int -> String -> String

Answer 6

rotate:: Int -> String -> String

rotate n xs = drop n xs ++ take n xs

Question 7

factoral

fac::Int -> Int

Answer 7

fac::Int -> Int
fac n = product [1..n]
or
fac 0 = 1
fac n  = n * fac (n-1)

Question 8

(*) (defined recursively with +)

(*):: Int -> Int -> Int

Answer 8

(*):: Int -> Int -> Int
m * 0 = 0
m * n = m + (m * (n-1))

Question 9

product (multiply all items in list)

product::Num a => [a] -> a

Answer 9

product::Num a => [a] -> a
product [] = []
product (n:ns) = n * product ns

or

product = foldr (*) 1

Question 10

length (of list)

length::[a] -> Int

Answer 10

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

or

length = foldr (_ n -> 1 + n) 0

Question 11

(++) append lists

(++):: [a] -> [a] -> [a]

Answer 11

(++):: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Question 12

insert (into ordered list)

insert:: Ord a=> a -> [a] -> [a]

Answer 12

insert:: Ord a=> a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) 
| x <= y        = x : y : ys
| otherwise = y : insert x ys

Question 13

insert sort (using insert::Ord=> a -> [a] -> [a])
isort:: Ord a => [a] -> [a]

Answer 13

isort:: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)

Question 14

zip

zip::[a] -> [b] -> [(a,b)]

Answer 14

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

Question 15

drop (first n of a list)

drop:: Int -> [a] -> [a]

Answer 15

drop:: Int -> [a] -> [a]
drop 0 _ = []
drop _ [] = []
drop n (_:xs) = drop (n-1) xs

Question 16

map (functions over a list)

map::(a -> b) -> [a] -> [b]

Answer 16

map::(a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

or

map f xs = [f x | x ← xs]

Question 17

filter (from a list based on predicate)

filter::(a -> Bool) -> [a] -> [a]

Answer 17

filter::(a -> Bool) -> [a] -> [a]
filter [] = []
filter p (x:xs) 
| p x = p : filter p xs
| otherwise = filter p xs

or

filter p xs = [x | x ← xs, p x]

Question 18

foldr - fold a function to right across list

foldr::(a -> b -> b) -> b -> [a] -> b

Answer 18

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

Question 19

sum (of list)

sum::Num a => [a] -> a

Answer 19

sum::Num a => [a] -> a
sum [] []
sum (n:ns) = n + sum ns

or

sum = foldr (+) 0

Question 20

or (on list of Bool)

or::[Bool] -> Bool

Answer 20

or::[Bool] -> Bool
or [] = False
or (x:xs) = x || or xs

or

or = foldr (||) False

Question 21

and (on list of bool)

and::[Bool] -> Bool

Answer 21

and::[Bool] -> Bool
and [] = True
and (x:xs) = x && and xs

or

and = foldr (&&) True

Question 22

(.) composition

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

Answer 22

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

f . g = \x -> f (g x)

Question 23

id (the identity function)

id::a -> a

Answer 23

id::a -> a

id = \x -> x

Question 24

iterate (apply function to result of previous function)

iterate::(a -> a) -> a -> [a]

Answer 24

iterate::(a -> a) -> a -> [a]

iterate f x = x : iterate f (f x)

Question 25

primes (inefficient)

primes :: Int -> [Int]

Answer 25

primes :: Int -> [Int] 
primes n = [x | x ← [2..n], prime x]
where
prime  n = factors n == [1,n]
factors n = [x | x ← [1..n], n ‘mod‘ x == 0]