Haskell Flashcards
let
Defines a function
let original = 2
let add x y = x + y
Other way:
let a = 1 in a + a
let a = 2; b = 4 in a * b
map
Map is a name of a higher-order function that applies a given function to each element of the list, returning a list of results.
let number = [2, 4 , 6]
map (+3) numbers = [5, 7, 9]
map (\x -> x*x) [1..5]
map function list
Filter
Filter is the name of a higher-order function that processes a data structure, typically a list, in some order to produce a new data structure containing those exact elements of the original data structure that match a given condition.
let numbers = [25,9,(-20),100,16,(-2)]
filter (<16) numbers = shows numbers below 16
filter f (x:xs)
|f x = x : rest
|otherwise = rest
where rest = filter f xs
square_even :: [Int] -> [Int]
square_even list = map (^2) (filter even list)
Fold
Reduce/Fold is the name of a higher-order function which reduces a list of values to a single value by repeatedly applying a combining function to the list values.
numbers = [2, 4, 6]
foldl (+) 0 numbers = adds all numbers including 0 from left to right.
sum’’ list = foldr (\ x acc -> acc + x) 0 list
Acc:
Actuator -> acc = 0 , then becomes 0 + whatever is on the right of the list
foldr1 = uses the last element in the list as the accumulator
foldr1 cannot change the type of the list
Side Effect
A side effects is anything that changes global state. This means that is could change a variable, a console etc, in which pure functions disallow things like prints, loops and variables. No control flow either, like if statements, because that makes the result indeterministic.
Pure Function
A functions with NO SIDE EFFECTS, meaning it is DETERMINISTIC and ALWAYS RETURNS A VALUE.
Subroutine
They predominately have side effects. These subroutines that have side effects cause issues for code refactoring, complier designers, optimization and parrelization.
**
Float (square)
Integer (square)
&&
||
AND statement
OR statement
Not
Gives opposite for boolean
==
Equality testing
/=
Not equal
Negatives
Must be in brackets
Priority
Functions
mod
Remainder
``
Allows function to become infix
Brackets
Allows add and sub to become prefix
Succ
Successor
::
Has type
:t True
True :: Bool
– and {–}
Allows comments
Show
Turn anything into a string
putStrLn
Prints
If
If True then 1 else 0, both branches must exist.
Lists
Contain items that all have the same type.
[]
They are linked (go through everything from the beginning)
Last, Init, Head, Tail
: = puts new head on (1: [2,3,4,5])
!! = index of list
Tuples
Allows us to bind two or move values together
Can contain different types
()
Fixed length
Range
[1..10]
Step Size
[2,4..20]
Would give = [2,4,6,8,10 etc]
Counting downwards always needs a step size.
take 4 [1..]
Infinite list, but returns the first four.
Repeat and Cycle
Repeats the input and repeats the list.
List Comprehension
Can produce more complex lists:
[ 2*x |x <- [1,2,3,4]] = [2,4,6,8]
Predicates
[2*x | x <- [1,2,3,4], x<2] = [2]
Using commas to filter results.
List Comprehension : Upper Case
st [c | c <- st, c ‘elem’ [‘A’…‘Z’]]
List Comprehension : Prime Numbers With Factorials
factors n = [x | x <- [1..n], n mod x == 0]
prime n = [x | x <- [1..n], length (factors x) == 2] (only got 2 factors)
Recursion
factorial n = if n > 1
then n * factorial (n-1)
else 1
Base case - not making recursive rule (else 1)
Another way:
factorial 1 = 1
factorial n = n * factorial (n-1)
Guards
Guards:
f x
| x < 1 = “strictly less”
| x > 1 = “strictly more”
| otherwise = “other”
n == 1 = 1 - used for guards (format)
Recursion With Lists
sum’ [] = 0 - base case
sum’ (x:xs) = x + sum’ xs
Where
f x = x + a
where a = x + 1
Defines a
Difference between where and let is that let can be used multiple times.
Zip’
zip’ takes two lists and returns a list of pairs
zip [1..10]”hello there”
[1,h][2,e] etc.
Mutual Recursion
even’ 0 = True
even’ n = odd’ (n-1)
odd’ = False
odd’ n = even’ (n-1)
Recursive methods that call each other.
Multiple Recursion
fib 0 = 0
fib 1=1
fib n = fib (n-1) + fib (n-2)
Multiple recursions in one line.
Quicksort
Sorts elements in a list.
pivot element p
lower = all elements smaller than p
upper = all element larger than p
return sorted_lower ++ [p] ++ sorted_upper
split pivot [] = ([],[])
split pivot (x;xs) etc etc. (x lower or higher)
qs [] = []
qs (x:xs) = qs lower ++ [x] ++ qs upper
where (lower,upper) = split x xs
:t
Will display the type
:t True = True :: Bool
is_lower c = c elem [a…z]
:t is_lower = char -> bool
Int
Integer
Double
Holds 64-bit but faster
Holds arbitrary but slower
Holds 64-bit float
Partial Application
plus a b = a+b
alternative:
plus2 = plus 1
plus2 2 = 3
Also known as currying
Polymorphism
:t length
length :: [a] -> int
Works on all lists that have different types.
[function name] :: [type]
fst
Returns first element of two ; tuple
snd
Returns second element of two ; tuple
:t take
take :: Int -> [a] -> [a]
Difference between : and ++
++ takes two lists, : takes a single value
:info …
Tells information on function.
:t (+)
(+) = Num a => a -> a -> a
if you give two a’s which are equal to Num a, then return a
f (x, y) = (x+1, y==2)
:t f
(eq a1, num a2, num a1) => ((the inputs)a2,a1) -> ((the results)a2, bool)
General Type Annotations
The most general type annotation is the one that is least restrictive:
equals_two a b = a + b == 2
equals_two :: (Eq a, Num a) => a -> a -> bool
fromIntegeral
Convert back to a more generic type.
Show and Read
Show = converts other types into strings
Read = converts strings into other types
x = [take 1, length] -> why does this not work?
Doesn’t work since they are different types ; take returns a list, length returns an integer
Dot Operator
((+1) . (*2)) 4 -> dot operator
Use of dot operator removes the need for nested brackets.
$
Used to evaluate the input.
Anonymous Function
(\ x -> x+1) 5 -> this is an anonymous function; a function that has no name. This is meant to represent lambda.
Scan
Like Fold, but prints the accumulator each time:
scanr (+) 0 [1,2,3,4]
[10,9,7,4,0]
scan1 (+) [1..10]
[0,1,3,6,10,15,21,28,36,45,55]
Takewhile
Takes from a list while a condition is true
takeWhile (<=5) [1..10]
[1,2,3,4,5]
Dropwhile
dropWhile drops from a list while a condition is true
dropWhile (==1) [1,1,2,2,3,3]
[2,2,3,3]
Zipwith
Zips two lists using a function
zipWith (+) [1,2,3] [4,5,6]
[5,7,9]
Type
type String’ = [char]
… :: String’ -> String’
type VoteResults = [(Int, String)]
results :: VoteResults
results = [(1, “Red”), …]
Data
data Bool’ = True | False
data Direction = North | East | South | West deriving Show
Adds Direction to show, since Direction is not part of a class at the beginning
Show, Read, Eq, Ord = all derivable : deriving (Show, Read, Eq, Ord)
data TwoThings = Things Int Char deriving Show
f (Things x _ ) = x
f (Things 2 ‘a’) = 2
= or
Record
Record Type:
data Person = Person String String Int String
get_first_name (Person x _ _ _) = x etc…
Record Type 2:
data Blah = Blah { one :: Int, two :: Char } deriving Show
Difference between pattern matching lists and tuples
Lists = (s:s)
Tuples = (s,s)
Use foldr to write a function product of evens that takes a list of
numbers, and multiplies all the even elements together.
Use foldr to write a function lt10 that takes a list of numbers and
returns the number of elements that are strictly less than 10.
You HAVE to use acc.
product_of_evens list = foldr (\ x acc -> if even x then x * acc else
acc) 1 list
lt10 list = foldr (\ x acc -> if x < 10 then 1 + acc else acc) 0 list
Maybe, Just, and Nothing
data Maybe a = Just a | Nothing
safe_head [] = Nothing
safe_head (x:_) = Just x
Case
h = safe_head list
case h of Just x -> x
Nothing -> 0
f x = case x of (x:xs) -> x
[] -> 0
Either’
data Either’ a b = Left a | Right B
ghci> let list = [Left “one”, Right 2,
Left “three”, Right 4]
is_left (Left _) = True
is_left _ = False
map unleft unright list *
Cannot be done as trying to combine two lists that contain different values will lead to an error.
Recursive Data Types
data IntList = Empty | Cons Int IntList deriving(Show)
Cons 4 ( Cons 5 ( Cons 6 Empty)))
data a = Empty | Cons a (List a) deriving(Show)
Cons “hi” Empty
data TwoList a b = TwoEmpty
|ACons a (TwoList a b)
|BCons b (TwoList a b)
deriving(Show)
Tree Search with Recursive Data Types
data TwoList a b = TwoEmpty
|ACons a (TwoList a b)
|BCons b (TwoList a b)
deriving(Show)
data Tree = Leaf | Branch Tree Tree deriving(Show)
size :: Tree -> Int
size (Leaf) = 1
size (Branch x y) = 1 + size x + size y
data DTree = DLeaf a | DBranch a (DTree a) (DTree a) deriving(Show)
tree_sum :: Num a => DTree a -> a
tree_sum (DLeaf x) = x
tree_sum (DBranch x l r) = x + tree_sum l + tree_sum r
getLine
Reads an input line from the console (input) ; requires an IO String
:t -> getLine :: IO String
putStrLn
Takes a string and prints out hi (print) ; requires a pure string
:t :: String -> IO ()
getChar
Gives back a char from input char
Conc two strings together via two inputs
print_two :: String -> String -> IO ()
print_two s1 s2 = putStrLn (s1 ++ s2)
do / do blocks
Allows sequence of actions followed by an IO ; only works with IO.
get_and_print :: IO ()
get_and_print =
do
x <- getLine
y <- getLine
putStrLn (x ++ “ “ ++ y)
return
Takes a pure value and returns the value in an IO box ; used for “do nothing”.
Return, in functional programming, does NOT stop the program running.
print_if_short :: String -> IO ()
print_if_short str =
if length str <= 2
then putStrLn str
else return ()
:: Monad m => a -> m a
Mutual Recursion
Two functions which call upon one another.
Multiple Recursion
Makes more than one recursive call in the actual function line.
Tail Recursion
Nothing left to do once the function has made the recursive call.
Lazy Evaluation
List recursion
A recursion using lists.
