haskell Flashcards
3.0 + 4
7.0
8.0 / 2
4.0
negation
not True
or
False || True
and
&&
not equal
/=
4 ways to concatenate. Hint: add, colon, colon tuple, colon all the way
[1,2,3] ++ [4,5] ⇒ [1,2,3,4,5]
[] ++ [1,2] ⇒ [1,2]
3 : [4,5] [3,4,5]
2 : (3 : (4 : [])) [2,3,4]
2 : 3 : 4 : [] [2,3,4]
whats the type for ‘abc’
errro
whats the output for ‘a’ ++ “bcd”
error
write two ways to add a list of characters to a string.
hint: concat operator and colon.
“ab” ++ [‘c’,’d’]
compare list of chars with a string. tell me whats the output
[‘X’, ‘Y’] == “XY” True
write me a function that takes a and b and returns a list of a and b
listify a b = [a, b]
write a two line recursie mylength function
myLength [] = 0
myLength (_:xs) = 1 + myLength xs
write a are two lists equal recursive function considering edge cases
listEqual [] [] = True
listEqual (x:xs) (y:ys) = x == y && listEqual xs ys
listEqual [] (:) = False
listEqual (:) [] = False
(or listEqual _ _ = False and use the first-match-only behaviour.)
write a even odd length function:
two ways:
- recursively
- using the even function
hasEvenLength [] = True – base case: length 0 is even
hasEvenLength [ _ ] = False – base case: length 1 is odd
hasEvenLength (_ : _ :rest) = hasEvenLength rest
or:
hasEvenLength xs = even (length xs)
what are the 3 Rules for pattern matching:
plain identifier (argument name, like x): matches anything and captures the value.
_: matches anything but we don’t need the value.
literal value (like 1, [], etc): matches if equal.
what are the 4 ways to match lists
hint:
match 0 elements
match 1,
match 2,
or match all of the rest of the elements
[]: matches an empty list.
[a]: matches a one-element list.
(a:tail): matches a list with at least one element. First is a, rest of list is tail (and could be an empty list).
(a:b:tail): matches a list with at least two elements. First is a, second is b, remainder of list is tail (could be empty).
if we have (a:b:c), what is the result for the following arguments:
a b c
[6, 7, 8, 9]
[‘a’,’b’]
“ab”
[100]
6, 7, [8,9]
‘a’ ‘b’ []
‘a’ ‘b’ [] (==””)
[100]: ERROR
write a simple mySigNum function using conditional
mySignum x
| x>0 = 1
| x<0 = -1
| otherwise = 0
write using a case expression that matches 1, 2, 3 with their words, everything else with ????. and finally, concatenate it with “X”
wordWithX n = (case n of
1 -> “one”
2 -> “two”
3 -> “three”
_ -> “???”) ++ “X”
write the describe llist function. concatenate “the list is “ with corresponding list length
describeList lst = “The list is “ ++ case lst of
_ : _ : _ : _ : _ -> “fairly long” – >= 4 elements
_ : _ -> “short” – >= 1 element
[] -> “empty”
write a list comprehension for x^2+1 with x = 1 to 7
[ x^2+1 | x <- [1, 2, 3, 4, 5, 6, 7] ]
use more than one generator to fwrite 10*x + y
[ 10*x + y | x <- [3,4,5], y <- [6,7,8,9]]
create a list by using the even guard x in x^2+1
[ x^2+1 | x <- [1, 2, 3, 4, 5, 6, 7], even x ]
build a list function
n = [ i*i | i <- [2,4..n]]
write a quick sort example with where clause
qs [] = []
qs (x:xs) = smaller ++ [x] ++ larger
where smaller = qs [a | a<-xs, a<=x]
larger = qs [a | a<-xs, a>x]
write a quick sort example in one line with list comprehension
qs (x:xs) = qs [a | a <- xs, a <= x] ++ [x] ++ qs [a | a <- xs, a > x]
write quicksort it with let clause:
BASE CASE
qs’ [] = []
qs’ (x:xs) =
let smaller = qs’ [a | a<-xs, a<=x]
larger = qs’ [a | a<-xs, a>x]
in smaller ++ [x] ++ larger
write a simple myPower recursive function
myPower _ 0 = 1
myPower x y = x * myPower x (y-1)
write an OlogN myPower’ using conditional
myPower’ x y
| y==0 = 1
| even y = halfhalf
| odd y = xhalf*half
where half = myPower’ x (div y 2)
whats the flag to optimize haskell code
ghc -O2
write tail recursive my power
myPowerTailRec a _ 0 = a
myPowerTailRec a x y = myPowerTailRec (x*a) x (y-1)
write complete tail recursive factorial function with where clause
factorial’ n = factorialTailRec 1 n
where
factorialTailRec a 0 = a
factorialTailRec a n = factorialTailRec (n*a) (n-1)
what overhead does tail recursion avoid
overhead of maintaining the call stack
write a function that takes n nums from list, use split function
split :: Int -> [Int]
myTake n xs: start
where (start, _) = split n xs
write a myGCD function
myGCD 0 b = b
myGCD a 0 = a
myGCD a b = gcd b r
Where (q,r) = a divMod b
filter even numbers from a list using the even function and filter
Filter even [1..8]
filter even numbers from a list using list comprehension
[ n | n <- [1..8], even n]
map sqrt to a list
map sqrt [1..8]
map sqrt to a list with list comprehension
[ sqrt n | n <- [1..8]]
give me an example of foldr
foldr (+) 0 [1,2,34,5]
know how to user foldl
write the operators that you can perform on for these type classes:
Ord:
Num:
Integral:
Fractional:
Show:
Enum:
Ord: Eq plus can be ordered ((<), (>=), min, …).
Num: Number-like things ((+), (*), abs, …).
Integral: Integer-like things (div, mod, …).
Fractional: Num plus true division ((/), recip).
Show: can be converted to a string for display.
Enum: has previous/next elements (pred, succ)
what is Join / intercalate.
give an example
join is actually a function that takes a String and returns a function [String] -> String.
let words = [“Hello”, “World”]
putStrLn $ intercalate “ “ words
implement comajoin on a list
commajoin :: [String] -> String
commajoin = join “, “
what is map sqrt someList equivalent to
(map sqrt) someList
what are equivalent calculations for this: div 10 2
Prelude> (div 10) 2
5
Know that this works:
Prelude> let d10=(div 10) in d10 2
5
implement myConcat using foldl
myConcat :: [[a]] -> [a]
myConcat :: [[a]] -> [a]
myConcat xs = foldl (++) [] xs
myConcat’ :: [[a]] -> [a]
myConcat’ = foldl (++) []
write a divors function, that returns a list of nums from 2 to n using filter
use the following type
divisors :: Integral a => a -> [a]
divisors n = filter (divides n) [2..(n div 2)]
where divides a b = (a mod b) == 0
write function as argument with operators for (/) operator using map
Prelude> map (12/) [6,2,12]
[2.0,6.0,1.0]
Prelude> map (/12) [6,2,12]
[0.5,0.16666666666666666,1.0]
curry and uncurry on div
addPair :: (Int, Int) -> Int
addPair (x, y) = x + y
addCurried :: Int -> Int -> Int
addCurried = curry addPair
*Main> (uncurry div) (10,2)
5
*Main> (curry myDiv) 10 2
5
(uncurry (+)) (2, 4)
how do you zip these two elements and what is the output:
[1,2,3] [‘a’,’b’,’c’]
*Main> zip [1,2,3] [‘a’,’b’,’c’]
[(1,’a’),(2,’b’),(3,’c’)]
implement a unzip function that takes two arrays and adds them together. hint: use zip and uncurry
addPairwise :: Num a => [a] -> [a] -> [a]
addPairwise xs ys = map (uncurry (+)) (zip xs ys)
addPairwise [1,2,3] [4,5,6]
== map (uncurry (+)) (zip [1,2,3] [4,5,6])
== map (uncurry (+)) [(1,4), (2,5), (3,6)]
== [(uncurry (+)) (1,4), (uncurry (+)) (2,5), (uncurry (+)) (3,6)]
== [(+) 1 4, (+) 2 5, (+) 3 6]
== [5, 7, 9]
write function composition examples, for hailLen
hailLen = length . hailSeq
meaning:
hailSeq on n
then length on hailSeq n
what does intercalate do
import Data.List (intercalate)
example1 = intercalate “, “ [“apple”, “banana”, “orange”]
– Output: “apple, banana, orange”
example2 = intercalate “ | “ [“Haskell”, “is”, “fun”]
– Output: “Haskell | is | fun”
example3 = intercalate “” [“a”, “b”, “c”, “d”, “e”]
– Output: “abcde”
what does flip do
In this example, flip intercalate flips the order of the arguments for the intercalate function
example1 = flip (-) 5 3
– Output: -2
example2 = flip (++) “world” “hello, “
– Output: “hello, world”
example3 = flip const 42 “ignored”
– Output: 42
write a function composition example for join primes where it joins prime numbers up to 11 with a string
hint use flip
joinPrimes :: String -> String
joinPrimes = (flip intercalate) [“2”, “3”, “5”, “7”, “11”]
or
joinPrimes = flip intercalate [“2”, “3”, “5”, “7”, “11”]
write a myReverse function
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (x:xs) = myReverse xs ++ [x]
write a half of lambda function
half_of’ :: Float -> Float
half_of’ = \x -> x/2
write a addToEach function using lambda
addToEach :: Num a => a -> [a] -> [a]
addToEach n lst = map (\x -> x+n) lst
write comma join using lambda, partial function, and normal function
commajoin0, commajoin1, commajoin2 :: [String] -> String
commajoin0 = \xs -> join “, “ xs
commajoin1 = join “, “
commajoin2 xs = join “, “ xs
what is a thunk
Thunk: represents the calculation that could happen
what does this evaluate:
Prelude> fst (1+2, 3+4)
Prelude> fst (1+2, [1..])
Prelude> fst (1+2, 3+4)
3
Prelude> fst (1+2, [1..])
3
implement a myTake function recursively
myTake 0 _ = []
myTake n (x:xs) = x : myTake (n-1) xs
myTake 2 [1..]
== take 2 (1:[2..]) – arg 2 matches x:xs?
== 1 : take (2-1) [2..] – recursive case
== 1 : take 1 [2..] – arg 1 matches 0?
== 1 : take 1 (2:[3..]) – arg 2 matches x:xs?
== 1 : 2 : take (1-1) [3..] – recursive case
== 1 : 2 : take 0 [3..] – arg 1 matches 0?
== 1 : 2 : [] == [1, 2] – base case
how do you combine element with array
list = 1 : [2, 3, 4, 5]
– Output: [1, 2, 3, 4, 5]
write a function that duplicates the first element in the list
[1,2,3]
output:
[1,1,2,3]
duplicateFirst :: [a] -> [a]
duplicateFirst [] = []
duplicateFirst (x:xs) = x : x : xs
write a prepend to all function that gives the following input ouptut
prependToAll 0 [1, 2, 3, 4, 5]
– Output: [0, 1, 0, 2, 0, 3, 0, 4, 0, 5]
use map
prependToAll :: a -> [a] -> [a]
prependToAll x xs = map (x:) xs
do thunk analysis on this:
foldl (+) 0 [1,2,3]
foldl (+) 0 [1,2,3]
== foldl (+) (0+1) [2,3]
== foldl (+) ((0+1)+2) [3]
== foldl (+) (((0+1)+2)+3) []
== ((0+1)+2)+3
== (1+2)+3
== 3+3
== 6
what is the symbol to force non lazy evaluation
force strict evaluation with $! Operator
write a non lazy myPowerTailRec as myPowerTailRecStrict using $!
myPowerTailStrict a _ 0 = a
myPowerTailStrict a x y = (myPowerTailStrict $! (a*x)) x (y-1)
what does Seq a b do
returns b, but forces strict evaluation of a. It can be used like this to force a let/where value to be strictly evaluated:
write an example myPower with seq a b and where clause
myPowerSeq a _ 0 = a
myPowerSeq a x y = seq newacc (myPowerSeq newacc x (y-1))
where newacc = a*x
or:
myPower a _ 0 = a
myPower a x n = myPower (a seq a*x) x (n-1)
write the equivalent of
myPowerTailStrict a _ 0 = a
myPowerTailStrict a x y = (myPowerTailStrict $! (a*x)) x (y-1)
using seq
myPowerSeq a _ 0 = a
myPowerSeq a x y = seq newacc (myPowerSeq newacc x (y-1))
where newacc = a*x
write this using the $ notation
funnyDivisors n = map pred (divisors (n*2))
funnyDivisors n = map pred $ divisors $ n*2
what is the difference between $ vs (.)
Note: ($) combines a function and an argument; (.) combines two functions
write the following function using the (.) notation:
funnyDivisors n = map pred (divisors (n*2))
funnyDivisors’’ n = (map pred) . divisors . (* 2) $ n
or
funnyDivisors’’’ = (map pred) . divisors . (* 2)
what is the (.) notation called
composite function
what is the $ notation called
function application operator
what is a free variable
A free variable is any value used that isn’t a function argument.
what are two pure function properties
1 was a slight lie: function results depend on their arguments and free variables. A free variable is any value used that isn’t a function argument.
Given the same arguments, they always return the same results.
They have no side effects: do not modify the external state of the program.
what enables lazy evaluation in haskell?
Purity is what allows lazy evaluation. Haskell can choose to calculate a value or not since there are no side effects to worry about.
what does pseq do and what does it stand for
pseq a b: like seq but evaluates a before returning b.
what is the difference between seq, pseq, and par
seq (short for “sequence”) is used to control the order of evaluation. The expression seq a b first evaluates a, then b, and finally returns the value of b. If a is a large data structure, then seq can be used to force that structure to be evaluated, avoiding the creation of a large number of thunks (a thunk in Haskell is a data expression that has not been evaluated yet).
par (short for “parallel”) introduces parallelism. The expression par a b “sparks” off a to potentially run in parallel with b, and returns b. This doesn’t guarantee that a will be evaluated in parallel, but it’s a hint to the runtime system that it could be beneficial to do so.
pseq (short for “parallel sequence”) is a combination of par and seq. The expression pseq a b evaluates a before b, like seq, but also arranges that a is evaluated in parallel with the current computation, like par.
what does par do
par a b: evaluate a and b concurrently, and return b.
what is the typical usage for par
Typical usage: use these to express do A and B in parallel and then combine them.
how to enable parallel execution in command line
ghc -O2 -with-rtsopts=”-N8” -threaded concurrent1.hs
how to calculate this in parallel
calcA = a + b
where a = calculation 1
b = calculation 2
calcB = (a par b) pseq (a + b)
where a = calculation 1
b = calculation 2
how to run this in parallel
calcC = map slowCalc [0..100]
calcD = parMap rseq slowCalc [0..100]
is parallel always faster?
Example 3: breaking the problem down too small will cause too much overhead when coordinating threads
Breaking the problem into chunks that are too small causes overhead coordinating threads. e.g. these take about the same amount of time to complete:
Too small: too much overhead starting/stopping/communicating. Too big: not enough parallelism.
calcE = map fastCalc [0..1000000]
calcF = parMap rseq fastCalc [0..1000000]
what are the two operations a monad must do
Wrap and unwrap its values (e.g. convert between 2 and Just 2)
Chain together operations from one monad value to another.
The return function wraps a non-monad value in the appropriate monad
explain this in 4 steps:
(»=) :: (Monad m) => m a -> (a -> m b) -> m b
It takes the result of the previous step (of type m a);
unwraps it automatically (to type a);
a function takes the unwrapped value and produces the result of this step (a function a -> m b);
The m b is the result of this step.
write this:
secondLine :: IO String
secondLine = do
line1 <- getLine
line2 <- getLine
return line2
with:
- function unwrapping and without the return value
- and the»_space;= expression
secondLine’ :: IO String
secondLine’ =
getLine > > = (\ line1 -> getLine > > = (\ line2 -> return line2))
secondLine’’ :: IO String
secondLine’’ = do
line1 <- getLine
getLine
what does (»=) do
(»=) :: Monad m => m a -> (a -> m b) -> m b
And then (»=):
Basically joins the do notation
write a function that takes 3 elements as argument that you want to find in a list of elements w
findElt
findThree :: Eq a => a -> a -> a -> [a] -> Maybe (Int, Int, Int)
findThree v1 v2 v3 xs = do
pos1 <- findElt v1 xs
pos2 <- findElt v2 xs
pos3 <- findElt v3 xs
return (pos1, pos2, pos3)
*Main> findThree 1 2 3 [1,6,2,5,3,4]
Just (0,2,4)
*Main> findThree 1 2 3 [1,6,2,5,4]
Nothing
what is the function to generate random seed
newStdGen :: IO StdGen
write a function that generates three random values
threeRand’ :: IO [Int]
threeRand’ = do
gen0 <- newStdGen
let
(rand0, gen1) = randomR (1, 100) gen0
(rand1, gen2) = randomR (1, 100) gen1
(rand2, _) = randomR (1, 100) gen2
return [rand0, rand1, rand2]
return a list of 3 int values by generating an infinite list with randomRs
threeRand’’ :: IO [Int]
threeRand’’ = do
gen0 <- newStdGen
return $ take 3 $ randomRs (1, 100) gen0
generate random values within range min max and take n elements from it
use this type
randInts :: Int -> Int -> Int -> IO [Int]
import System.Random
– generate n random integers
– make sure the get the type right
randInts :: Int -> Int -> Int -> IO [Int]
randInts n minval maxval = do
gen <- newStdGen
return $ take n $ randomRs (minval, maxval)
