Higher Order Functions Flashcards
what does map do?
applies a function to every element in a list.
map (+1) [ 1, 3, 5, 7]
[2, 4, 6, 8]
what does filter do?
selects every element in a list that satisfies a predicate
filter :: (a -> Bool) -> [a] -> [a]
filter even [1..10]
[2, 4, 6, 8, 10]
what is the pattern of recursion?
f[] = v
f(x : xs) = x ⊕ f xs
give a recursive definition of sum and its foldr version
recursive:
sum[] = 0
sum(x : xs) = x + sum xs
foldr:
sum = foldr (+) 0
give a recursive definition of and and its foldr version
recursive:
and[] = True
and (x : xs) = x && and xs
foldr:
and = foldr (&&) True
give the foldr definition of length
length = foldr (_ n -> 1 + n) 0
describe the difference between intesionality and extensionality in a sentence
\x.(1+x) is intensionally different from \x.(x+1) but extensionally equal
what does . do?
returns the composition of 2 funstions as a single function
.) :: (b -> c) -> (a -> b) -> (a -> c
f.g = \x -> f(g x)
use . to define odd
odd :: Int -> Bool
odd = not.even
what does all do?
check whether every element satisfies a predicate
all even [2, 4, 6]
True
what does any do?
check whether any element satisfies a predicate
any isSpace “ab c”
True
what does takeWhile do?
selects elements while the predicate holds all elements
takeWhile isAlpha “ab cd”
“ab”
what does dropWhile do?
teh opposite of takeWhile
dropWhile is Alpha “ab cd”
“ cd”
express [fx | x
map f( filter p xs)
what is ad-hoc polymorphism?
overloading
What are the 2 types of type declaration?
abbreviation type and new type
What is an abbreviation type?
an existing type with a new name.
declare a new type Bool that can be shown and compared
data Bool = False | True
deriving (Show, Eq)
give an example of a new type where the constructors have parameters
data Shape = Circle Float
| Rect Float Float
define a new inductive type for natural numbers
data nat = Zero | Succ Nat
where
Zero :: Nat
Succ :: Nat -> Nat
Succ = +1
define a binary tree type
data Tree = Leaf Int
| Node Tree Int Tree
write a function that determines whether in Int occurs in a tree
occurs :: Int -> Tree -> Bool occurs m (leaf n) = m == n occurs m (Node l n r ) = m == n || occurs m l || occurs m r
what does flatten do?
returns all of the Ints in a tree
write a definition of flatten
flatten :: tree -> [Int]
flatten (Leaf n) = [n]
flatten (Node l n r) = flatten l ++ [n] ++ flatten r
