infinite lists Flashcards
Fibonacci of n
fib::Int->Int
fib::Int->Int
fib 0 = 0
fib 1 = 1
fib n = (fib n-2) + (fib n-1)
quicksort
qsort::Ord a => [a] -> [a]
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]
reverse
reverse::[a] -> [a]
reverse::[a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
or
reverse = foldr (\x xs -> xs ++ [x]) []
find (dictonary)
find::Eq a => a -> [(a,b)] -> [b]
find::Eq a => a -> [(a,b)] -> [b]
find k t = [v | (k’,v) ← t, k’ == k]
factors (all factors of a number from 1 to n)
factors:: Int -> [Int]
factors:: Int -> [Int]
factors n = [x | x ← [1..n], n mod x == 0]
rotate (move n letters from front to back)
rotate:: Int -> String -> String
rotate:: Int -> String -> String
rotate n xs = drop n xs ++ take n xs
factoral
fac::Int -> Int
fac::Int -> Int fac n = product [1..n] or fac 0 = 1 fac n = n * fac (n-1)
(*) (defined recursively with +)
(*):: Int -> Int -> Int
(*):: Int -> Int -> Int
m * 0 = 0
m * n = m + (m * (n-1))
product (multiply all items in list)
product::Num a => [a] -> a
product::Num a => [a] -> a
product [] = []
product (n:ns) = n * product ns
or
product = foldr (*) 1
length (of list)
length::[a] -> Int
length::[a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
or
length = foldr (_ n -> 1 + n) 0
(++) append lists
(++):: [a] -> [a] -> [a]
(++):: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
insert (into ordered list)
insert:: Ord a=> a -> [a] -> [a]
insert:: Ord a=> a -> [a] -> [a] insert x [] = [x] insert x (y:ys) | x <= y = x : y : ys | otherwise = y : insert x ys
insert sort (using insert::Ord=> a -> [a] -> [a]) isort:: Ord a => [a] -> [a]
isort:: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)
zip
zip::[a] -> [b] -> [(a,b)]
zip::[a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
drop (first n of a list)
drop:: Int -> [a] -> [a]
drop:: Int -> [a] -> [a]
drop 0 _ = []
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
map (functions over a list)
map::(a -> b) -> [a] -> [b]
map::(a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = (f x) : map f xs
or
map f xs = [f x | x ← xs]
filter (from a list based on predicate)
filter::(a -> Bool) -> [a] -> [a]
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]
foldr - fold a function to right across list
foldr::(a -> b -> b) -> b -> [a] -> b
foldr::(a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
sum (of list)
sum::Num a => [a] -> a
sum::Num a => [a] -> a
sum [] []
sum (n:ns) = n + sum ns
or
sum = foldr (+) 0
or (on list of Bool)
or::[Bool] -> Bool
or::[Bool] -> Bool
or [] = False
or (x:xs) = x || or xs
or
or = foldr (||) False
and (on list of bool)
and::[Bool] -> Bool
and::[Bool] -> Bool
and [] = True
and (x:xs) = x && and xs
or
and = foldr (&&) True
(.) composition
.)::(b->c) -> (a->b) -> (a -> c
(.)::(b->c) -> (a->b) -> (a -> c)
f . g = \x -> f (g x)
id (the identity function)
id::a -> a
id::a -> a
id = \x -> x
iterate (apply function to result of previous function)
iterate::(a -> a) -> a -> [a]
iterate::(a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
primes (inefficient)
primes :: Int -> [Int]
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]
