knowledge

• lazy evaluation is when the value of a variable is not evaluated until it is used
• Guards let functions behave differently in different situations. They are a convenient notation for conditional evaluation (as in if-then-else)

  func :: Integer -> Integer

  func x

  | x < 0 = 0

  | otherwise = x
• example of a recursion

  func :: Integer -> Integer

  func x

  | x < 0 = 0

  | otherwise = x + func (x-1)
• curried functions: able to take multiple arguments
• The type arrow is right-associative

  Lambda function application is left-associative
• The type of a pair is (a,b) for any types a and b and can be distinct

  eg

  pair :: (a, b)

  pair = (123, "qwer")

  ie (x,y) :: (a,b) for any x :: a and y :: b
• uncurry is defined as:

  func :: (Int -> Int -> Int) -> (Int,Int) -> Int

  func f (x,y) = f x y

  eg

  add :: (Int,Int) -> Int

  add (x,y) = x + y
• curry is defined as:

  func :: ((Int,Int) -> Int) -> Int -> Int -> Int

  func f x y = f (x,y)

  eg

  add :: Int -> Int -> Int

  add x y = x + y
• A tuple with n elements has length n
• insertion sort:

  f1 :: Int -> [Int] -> [Int]

  f1 x [] = [x]

  f1 x (y:ys)

  | x <= y = x:y:ys

  | otherwise = y : f1 x ys

  
  

  f2 :: [Int] -> [Int]

  f2 [] = []

  f2 (x:xs) = f1 x (f2 xs)
• where clauses are useful for naming intermediate calculations that are used in multiple places.
• accumulator: a register that holds the result of an operation
• recursive calls embedded inside incomplete calculations would require the computer to work a bit to store these incomplete calculations, which could cause space leak
• example of using the accumulator

  factorial :: Int -> Int

  factorial = afact 1

  where

  afact a 0 = a

  afact a n = afact (a * n) (n-1)
• lazy evaluation: delaying the execution of computations until their values are needed
• tail recursion is when a function makes only one recursive call with the same number of arguments as the original function call, and its result becomes the value returned by the calling function
• tail recursion means that the recursive call is the last thing the function has to compute and it is not buried inside a larger calculation
• in tail recursion, we can use the accumulator to hold the intermediate results instead of storing them on the stack
• an example of tail recursive function

  goodreverse :: [Int] -> [Int]

  goodreverse = areverse []

  where

  areverse a [] = a

  areverse a (x:xs) = areverse (x:a) xs
• recursion is a programming technique that allows a program to call itself to perform a task
• list comprehension

  [ 3*n + 1 | n <- [0..10] , even n ]

  n <- [0..10] : take each element from the list

  even n : is a condition/filter

  3*n + 1 : computation on the filtered elements
• benefits of list comprehension: easy to understand, easy to debug, easy to write, easy to read, and is efficient
• A constructor takes a fixed number of arguments of a fixed type

  Its name must be unique — this allows Haskell to infer the type
• Sections are partially-applied infix functions

  eg

  addsix :: Int -> Int

  addsix = (6+)
• Backquotes make a regular function into an infix one

  eg

  mod3 x = mod x 3 -> mod3 x = x ‘mod‘ 3
• Function composition

  f · g = x -> f(g(x))

  (f · g)(x) = f(g(x))
• data declarations can be recursive
• A wild card _ represents any value
• Haskell has no loops or iteration constructs like while or do..while. Instead it uses recursion and lazy evaluation.
• Infix functions can be defined using backticks (`). For example `+` is equivalent to (+)
• mod 12 5

  prefix function
• 3 `mod` 2

  infix function