FP in Scala and Recursion in FP

Question 1

write a sum function in Scala

Answer 1

def sum (xs : List[Int]) : Int = 
       xs match { 
              case Nil => 0
              case x :: ys => x + sum(ys)
       }
}

Question 2

define the type of length in Scala using a generic type

Answer 2

length :: [T] (xs : List [T]) Int

Question 3

what type of list is also possible in Scala?

Answer 3

heterogenous lists

Question 4

What is list comprehension called in Scala?

Answer 4

sequence comprehension

Question 5

Write a quicksort function in Scala

Answer 5

def qsort ( xs : List[Int]) : List[Int] = 
        xs match { 
                 case Nil => Nil
                 case x :: ys => qsort(for(i  x) yield j)

Question 6

what is the basic looping mechanism in fp?

Answer 6

recursion

Question 7

define zip with recursion

Answer 7

zip :: [a] -> [b] -> [(a, b)]
zip [] _ = []
zip _ [] = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys

Question 8

define qsort with recursion

Answer 8

qsort :: [Int] -> [Int]
qsort [] = []
qsort(x : xs) = qsort smaller ++ [x] ++ qsort larger
where
smaller = [a | a  x]

Question 9

5 steps for writing recursions

Answer 9

1. define the type
2. enumerate the cases
3. define the base cases
4. define the step cases
   5 generalise / simplify

Question 10

write a recursive sum in Scala

Answer 10

def sum (xs : List[Int]) : Int =
      xs match {
            case Nil => 0
            case x :: ys => x + sum(ys)
      }

sum: (xs : List[Int]) Int

Question 11

what are the 2 styles of typing?

Answer 11

church style and curry style

Question 12

Describe Church-style typing

Answer 12

\x:A.b

with domain’s type label (A)

Question 13

Describe Curry-style typing

Answer 13

\x.b

without somain’s type label

Question 14

describe typing in Scala

Answer 14

we need the type label of the domain and range

\x:A.(b:B)

Question 15

what is a μ-recursive function?

Answer 15

a general recursive function.

partial functions that take finite tuples of Nat numbers and return one Nat number

Question 16

how can μ-recursive functions be generates?

Answer 16

> primitive functions (constant, successor, and projection functions)

> operators (composition, primitive recursion, and minimization operators)

Question 17

what is a primitive recursion operatot?

Answer 17

where only f(0) and f(n + 1) are defined

Question 18

what is a minimization operator?

Answer 18

μ(f) = z if f(z) = 0 and f(k) > 0 for k < z