Functional Programming in Scala Exercises

.Functional Programming in Scala Exercises

All exercises are attempted on https://coderpad.io

2.1.scala

/**
 * Write a recursive function to get the nth Fibonacci number (http://mng.bz/C29s). The first two Fibonacci numbers are 0 and 1. The nth number is always the sum of the previous two—the sequence begins 0, 1, 1, 2, 3, 5. Your definition should use a local tail-recursive function.
   def fib(n: Int): Int
*/
def fib(n: Int): Int = {
    def go(n: Int, first: Int, second: Int): Int =
      if(n == 1) first
      else if (n == 2) second
      else go(n-1, second, first + second)
    go(n, 0, 1)
  }

/**
 * res26: Int = 0
@ fib(2)
res27: Int = 1
@ fib(3)
res28: Int = 1
@ fib(4)
res29: Int = 2
@ fib(5)
res30: Int = 3
@ fib(10)
res31: Int = 34 
 */

2.2.scala

/**
 * Implement isSorted, which checks whether an Array[A] is sorted according to a given comparison function:
    def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean 
 */
def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
    @annotation.tailrec
    def go(n: Int): Boolean =
      if (n == as.length - 1) ordered(as(n-1), as(n))
      else if (! ordered(as(n-1), as(n))) false
      else go(n + 1)
    if (as.size == 0 || as.size == 1) true
    else go(1)
  }

/**
 * @ isSorted[Int](Array(1,2,3,4), (a: Int, b: Int) => a <= b)
res18: Boolean = true
@ isSorted[Int](Array(1,2,3,4,1), (a: Int, b: Int) => a <= b)
res19: Boolean = false
@ isSorted[Int](Array(1), (a: Int, b: Int) => a <= b)
res20: Boolean = true
@ isSorted[Int](Array(), (a: Int, b: Int) => a <= b)
res21: Boolean = true
@ isSorted[Int](Array(2,1), (a: Int, b: Int) => a <= b)
res22: Boolean = false
@ isSorted[Int](Array(1,2,3,4,5,6,7,8,9,10), (a: Int, b: Int) => a <= b)
res23: Boolean = true
*/

2.3.scala

/**
 * Let’s look at another example, currying,9 which converts a function f of two arguments
   into a function of one argument that partially applies f. Here again there’s only one
   implementation that compiles. Write this implementation.
   def curry[A,B,C](f: (A, B) => C): A => (B => C)
*/
object Main {
    def curry[A,B,C](f: (A, B) => C): A => (B => C) = {
        a => b => f(a,b)
    }

    def main(args: Array[String]) = {
        val c = curry((a:Int, b:Int) => a == b)
        println("1 == 2? ", c(1)(2))
        println("2 == 2? ", c(2)(2))
        
        val c_partial = c(1)

        println("[partial] 1 == 2? ", c_partial(2))
        println("[partial] 1 == 1? ", c_partial(1))
    }
}

2.4.scala

/**
 * Implement uncurry, which reverses the transformation of curry. Note that since =>
    associates to the right, A => (B => C) can be written as A => B => C.
    def uncurry[A,B,C](f: A => B => C): (A, B) => C
*/
object HelloWorld {
       
    def uncurry[A,B,C](f: A => B => C): (A, B) => C = {
        (a,b) => f(a)(b)
    }
    
    def main(args: Array[String]) = {
        val sum = (a:Int) => (b:Int) => a + b
        val uncurried = uncurry[Int, Int, Int](sum)
        println("sum(1)(2)", sum(1)(2))
        println("uncurry(1,2)", uncurried(1,2))
    }
}

// Output
/**
 * (sum(1)(2),3)
 * (uncurry(1,2),3)
 * /

2.5.scala

/**
 * Implement the higher-order function that composes two functions.
    def compose[A,B,C](f: B => C, g: A => B): A => C
 */
object HelloWorld {
       
    def compose[A,B,C](f: B => C, g: A => B): A => C = {
        a => f(g(a))
    }    
    
    def main(args: Array[String]) = {
        val double = (a:Int) => 2 * a
        val toString = (a:Int) => "new value " + a
        val c = compose(toString, double)
        println("original value 2",c(2))
    }
}

// Output
/**
 * (original value 2,new value 4)
 */

3.1.scala

/**
 * What will be the result of the following match expression?
  val x = List(1,2,3,4,5) match {
    case Cons(x, Cons(2, Cons(4, _))) => x
    case Nil => 42
    case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
    case Cons(h, t) => h + sum(t)
    case _ => 101
  }
*/

3

3.10.scala

/**
 * Our implementation of foldRight is not tail-recursive and will result in a StackOverflowError
 * for large lists (we say it’s not stack-safe). Convince yourself that this is the
 * case, and then write another general list-recursion function, foldLeft, that is
 * tail-recursive, using the techniques we discussed in the previous chapter. Here is its
 * def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B
 */
def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
  case Nil => z
  case Cons(head, tail) => foldLeft(tail, f(z, head))(f)
}

// Run
object Solution extends App {
  import List._

  println("foldLeft Sum List(1,2,3): " + foldLeft(List(1,2,3), 0)(_+_))
  println("foldLeft Product List(1,2,3): " + foldLeft(List(1,2,3), 1)(_*_))
}

// Output
/**
 * foldLeft Sum List(1,2,3): 6
 * foldLeft Product List(1,2,3): 6
 */

3.11.scala

/**
 * Write sum, product, and a function to compute the length of a list using foldLeft.
 */
def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
  case Nil => z
  case Cons(head, tail) => foldLeft(tail, f(z, head))(f)
}

object Solution extends App {
  import List._

  println("foldLeft Sum List(1,2,3): " + foldLeft(List(1,2,3), 0)(_+_))
  println("foldLeft Product List(1,2,3): " + foldLeft(List(1,2,3), 1)(_*_))
  println("foldLeft Length List(1,2,3): " + foldLeft(List(1,2,3), 0)((x,_) => 1 + x))
  
}

// Output
/**
 * foldLeft Sum List(1,2,3): 6
 * foldLeft Product List(1,2,3): 6
 * foldLeft Length List(1,2,3): 3
 */ 

3.12.scala

/**
 * Write a function that returns the reverse of a list (given List(1,2,3) it returns
 * List(3,2,1)). See if you can write it using a fold.
 */
def reverse[A](l: List[A]): List[A] = reverse(l, Nil)
def reverse[A](in:List[A], out: List[A]): List[A] = in match {
  case Nil => out
  case Cons(h,t) => reverse(t, append(List(h), out))
}

def reverseFoldLeft[A](xs: List[A]): List[A] = 
  foldLeft(xs, List[A]())((b, a) => Cons(a,b))


// Run
object Solution extends App {

import List._
  println("reverse List(1,2,3): " + reverse(List(1,2,3)))
  println("reverse List(): " + reverse(List()))
  
  println("reverse with foldLeft List(1,2,3): " + reverseFoldLeft(List(1,2,3)))
  println("reverse with foldLeft List(): " + reverseFoldLeft(List()))
}

// Output
/**
 * reverse List(1,2,3): Cons(3,Cons(2,Cons(1,Nil)))
 * reverse List(): Nil
 * reverse with foldLeft List(1,2,3): Cons(3,Cons(2,Cons(1,Nil)))
 * reverse with foldLeft List(): Nil
 */ 

3.14.scala

/**
 * Implement append in terms of either foldLeft or foldRight.
 */
 def append[A](a1: List[A], a2: List[A]): List[A] =
  a1 match {
    case Nil => a2
    case Cons(h,t) => Cons(h, append(t, a2))
  }

def appendViaFoldLeft[A](l1: List[A], l2: List[A]): List[A] =
  foldLeft(reverse(l1),l2)((b, a) => Cons(a, b))

def appendViaFoldRight[A](l1: List[A], l2: List[A]): List[A] =
  foldRight(l1,l2)((a,b) => Cons(a, b))

// Run
object Solution extends App {

  import List._
  println("append: " + append(List(4,5,6), List(1,2,3)))
  println("append foldLeft: " + appendViaFoldLeft(List(4,5,6), List(1,2,3)))
  println("append foldRight: " + appendViaFoldRight(List(4,5,6), List(1,2,3)))
}

// Output
/**
 * append: Cons(4,Cons(5,Cons(6,Cons(1,Cons(2,Cons(3,Nil))))))
 * append foldLeft: Cons(4,Cons(5,Cons(6,Cons(1,Cons(2,Cons(3,Nil))))))
 * append foldRight: Cons(4,Cons(5,Cons(6,Cons(1,Cons(2,Cons(3,Nil))))))
 */ 

3.15.scala

/**
 * Hard: Write a function that concatenates a list of lists into a single list. Its runtime
 * should be linear in the total length of all lists. Try to use functions we have already
 * defined.
 */
def concatFoldLeft[A](l: List[A], r: List[A]): List[A] =
  foldLeft(reverse(l), r)((b, a) => Cons(a, b))

def concatFoldRight[A](l: List[A], r: List[A]): List[A] =
  foldRight(l, r)(Cons(_, _)) 

// Run
object Solution extends App {

  import List._
  println("concatFoldLeft(List(1,2,3), List(4,5,6)): " + concatFoldLeft(List(1,2,3), List(4,5,6)))
  println("concatFoldRight(List(1,2,3), List(4,5,6)): " + concatFoldRight(List(1,2,3), List(4,5,6)))
}

// Output
/**
 * concatFoldLeft(List(1,2,3), List(4,5,6)): Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Cons(6,Nil))))))
 * concatFoldRight(List(1,2,3), List(4,5,6)): Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Cons(6,Nil))))))
 */ 

3.16.scala

/**
 * Write a function that transforms a list of integers by adding 1 to each element.
 * (Reminder: this should be a pure function that returns a new List!)
 */

def addOne(l: List[Int]) = foldRight(l, List[Int]())((a, b) => Cons(a + 1, b))

// Run
object Solution extends App {

  import List._
  println("addOne List(1,2,3): " + addOne(List(1,2,3)))
  println("addOne List(): " + addOne(List()))
}

// Output
/**
 * addOne List(1,2,3): Cons(2,Cons(3,Cons(4,Nil)))
 * addOne List(): Nil
 */ 

3.17.scala

/**
 * Write a function that turns each value in a List[Double] into a String. You can use
 * the expression d.toString to convert some d: Double to a String.
 */
def doubleToString(l: List[Double]): List[String] = foldRight(l, List[String]())((a, b) => Cons(a.toString, b)) 

// Run
object Solution extends App {

  import List._
  println("doubleToString List(1.1,2.2,3.3): " + doubleToString(List(1.1,2.2,3.3)))
  println("doubleToString List(): " + doubleToString(List()))
}

// Output
/**
 * doubleToString List(1.1,2.2,3.3): Cons(1.1,Cons(2.2,Cons(3.3,Nil)))
 * doubleToString List(): Nil
 */

3.18.scala

/**
 * Write a function map that generalizes modifying each element in a list while maintaining
 * the structure of the list. Here is its signature
 * def map[A,B](as: List[A])(f: A => B): List[B]
 */
def map[A,B](l: List[A])(f: A => B): List[B] = l match {
  case Nil => Nil
  case Cons(h, t) => Cons(f(h), map(t)(f))
}

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = // Utility functions
  as match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
  }

def mapFoldRight[A,B](l: List[A])(f: A => B): List[B] =
  foldRight(l, List[B]())((a, b) => Cons(f(a), b))


// Run
object Solution extends App {
  import List._
  println("map List(1,2,3) * 2: " + map(List(1,2,3))(_ * 2))
  println("mapFoldRight List(1,2,3) * 2: " + mapFoldRight(List(1,2,3))(_ * 2))
}

// Output
/**
 * map List(1,2,3) * 2: Cons(2,Cons(4,Cons(6,Nil)))
 * mapFoldRight List(1,2,3) * 2: Cons(2,Cons(4,Cons(6,Nil)))
 */ 

3.19.scala

/**
 * Write a function filter that removes elements from a list unless they satisfy a given
 * predicate. Use it to remove all odd numbers from a List[Int].
 * def filter[A](as: List[A])(f: A => Boolean): List[A]
 */
def filter[A](l: List[A])(f: A => Boolean): List[A] = 
  foldRight(l, List[A]()){ 
    (a, b) => if (f(a)) Cons(a, b) else b
  }

// Run
object Solution extends App {
  import List._
  println("filter List(1 to 10), remove odd numbers: " + filter((List(1,2,3,4,5,6,7,8,9,10)))(_ % 2 == 0))
}

// Output
// filter List(1 to 10), remove odd numbers: Cons(2,Cons(4,Cons(6,Cons(8,Cons(10,Nil)))))

3.2.scala

/**
 * Implement the function tail for removing the first element of a List. Note that the
   function takes constant time. What are different choices you could make in your
   implementation if the List is Nil? We’ll return to this question in the next chapter.
*/

def tail[A](l: List[A]): List[A] = l match {
    case Nil => Nil
    case Cons(head, tail) => tail
  }
  
  // Run
  object Solution extends App {
  import List._

  println("Tail List(1,2,3,4): " + List.tail(List(1,2,3,4)))
  println("Tail List(1): " + List.tail(List(1)))
  println("Tail List(): " + List.tail(List()))
  println("Tail Nil: " + List.tail(Nil))
}
  
  // Output
  /**
   * Tail List(1,2,3,4): Cons(2,Cons(3,Cons(4,Nil)))
     Tail List(1): Nil
     Tail List(): Nil
     Tail Nil: Nil
*/

3.20.scala

/**
 * Write a function flatMap that works like map except that the function given will return
 * a list instead of a single result, and that list should be inserted into the final resulting
 * list. Here is its signature:
 * def flatMap[A,B](as: List[A])(f: A => List[B]): List[B]
 * For instance, flatMap(List(1,2,3))(i => List(i,i)) should result in
 * List(1,1,2,2,3,3).
 */

def flatMap[A,B](xs: List[A])(f: A => List[B]): List[B] =
  foldRight(xs, List[B]())((a,b) => append(f(a), b))

// Run
object Solution extends App {
  import List._
  println("flatMap(List(1,2,3)(i => List(i,i))): " + flatMap(List(1,2,3))(i => List(i,i)))
}
// Output
// flatMap(List(1,2,3)(i => List(i,i))): Cons(1,Cons(1,Cons(2,Cons(2,Cons(3,Cons(3,Nil))))))

3.21.scala

/**
 * Use flatMap to implement filter.
 */
def filterViaFlatMap[A](l: List[A])(f: A => Boolean): List[A] =
  flatMap(l)(a => {if(f(a)) List(a) else Nil})

def flatMap[A,B](xs: List[A])(f: A => List[B]): List[B] =
  foldRight(xs, List[B]())((a,b) => append(f(a), b))

// Run
object Solution extends App {
  import List._
  print("filterViaFlatMap(List(1 to 10)) remove odd: " + 
       filterViaFlatMap(List(1,2,3,4,5,6,7,8,9,10))(_ %2 == 0))
}

// Output
// filterViaFlatMap(List(1 to 10)) remove odd: Cons(2,Cons(4,Cons(6,Cons(8,Cons(10,Nil)))))

3.22.scala

/**
 * Write a function that accepts two lists and constructs a new list by adding corresponding
 * elements. For example, List(1,2,3) and List(4,5,6) become List(5,7,9).
 */
def addByIndex(l1: List[Int], l2: List[Int]): List[Int] = (l1, l2) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1, t1), Cons(h2, t2)) => Cons(h1 + h2, addByIndex(t1, t2))
}

// Run
object Solution extends App {
  import List._
  println("addByIndex(List(1,2,3),List(4,5,6)): " + addByIndex(List(1,2,3),List(4,5,6)))
}

// Output
// addByIndex(List(1,2,3),List(4,5,6)): Cons(5,Cons(7,Cons(9,Nil)))

3.23.scala

/**
 * Generalize the function you just wrote so that it’s not specific to integers or addition.
 * Name your generalized function zipWith.
 */
def zipWith[A,B,C](l1: List[A], l2: List[B])(f: (A,B) => C): List[C] =
 (l1, l2) match {
   case(_, Nil) => Nil
   case(Nil, _) => Nil
   case(Cons(h1, t1), Cons(h2, t2)) => Cons(f(h1, h2), zipWith(t1, t2)(f))
 }

// Run
object Solution extends App {
  import List._
  println("zipWith(List(1,2,3),List(4,5,6)) Sum: " + zipWith(List(1,2,3),List(4,5,6))(_ + _))
  
  println("zipWith(List(1,2,3),List(4,5,6)) Product: " + zipWith(List(1,2,3),List(4,5,6))(_ * _))
}

// Output
/**
 * zipWith(List(1,2,3),List(4,5,6)) Sum: Cons(5,Cons(7,Cons(9,Nil)))
 * zipWith(List(1,2,3),List(4,5,6)) Product: Cons(4,Cons(10,Cons(18,Nil)))
 */

3.25.scala

/**
 * Write a function size that counts the number of nodes (leaves and branches) in a tree
 */

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {
  def size[A](tree: Tree[A]): Int = tree match {
    case Leaf(_) => 1
    case Branch(left, right) => size(left) + size(right) + 1
  }
}

// Run
object Solution extends App {
  import Tree._
  val left: Tree[Int] = Leaf(1)
  val right: Tree[Int] = Leaf(3)
  val branch: Tree[Int] = Branch(left, right)
  
  println("size: " + size(branch))
}

// Output
size: 3

3.3.scala

/**
 * Using the same idea, implement the function setHead for replacing the first element
   of a List with a different value.
*/
def setHead[A](l: List[A], h: A): List[A] = l match {
    case Nil => Nil
    case Cons(_, tail) => Cons(h, tail)
  }

// Run
object Solution extends App {
  import List._

  println("setHead List(1,2,3,4), 0: " + List.setHead(List(1,2,3,4),0))
  println("setHead List(1), 0: " + List.setHead(List(1),0))
  println("setHead List(), 0: " + List.setHead(List(),0))
  println("setHead Nil, 0: " + List.setHead(Nil,0))
}

// Output
/**
 * setHead List(1,2,3,4), 0: Cons(0,Cons(2,Cons(3,Cons(4,Nil))))
   setHead List(1), 0: Cons(0,Nil)
   setHead List(), 0: Nil
   setHead Nil, 0: Nil
*/

3.4.scala

/**
 * Generalize tail to the function drop, which removes the first n elements from a list.
   Note that this function takes time proportional only to the number of elements being
   dropped—we don’t need to make a copy of the entire List.
   def drop[A](l: List[A], n: Int): List[A]
*/
def drop[A](l: List[A], n: Int): List[A] = l match {
    case Nil => Nil
    case _ if n == 0 => l
    case Cons(_, tail) => drop(tail, n-1)
  }

// Run
object Solution extends App {
  import List._

  println("drop List(1,2,3,4), 2: " + List.drop(List(1,2,3,4),2))
  println("drop List(1), 0: " + List.drop(List(1),0))
  println("drop List(1), 1: " + List.drop(List(1),1))
  println("drop List(1), 10: " + List.drop(List(1),10))
  println("drop List(), 10: " + List.drop(List(),1))
  println("drop Nil, 1: " + List.drop(Nil,1))
}

// Output
/**
 * drop List(1,2,3,4), 2: Cons(3,Cons(4,Nil))
   drop List(1), 0: Cons(1,Nil)
   drop List(1), 1: Nil
   drop List(1), 10: Nil
   drop List(), 10: Nil
   drop Nil, 1: Nil
*/

3.5.scala

/**
 * Implement dropWhile, which removes elements from the List prefix as long as they match a predicate.
 * def dropWhile[A](l: List[A], f: A => Boolean): List[A]
*/
def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
  case Nil => Nil
  case Cons(head, tail) if f(head) => dropWhile(tail, f)
  case _ => l
}

// Run
object Solution {
 def main(args:Array[String]): Unit = {
   import List._
   
   
   println("dropWhile (x<=3) in List(1,2,3,4,5) = " +
           dropWhile(List(1,2,3,4,5), (x:Int) => (x <= 3)))
  
   println("dropWhile (x<0) in List(1,2,3,4,5) = " +
           dropWhile(List(1,2,3,4,5), (x:Int) => (x < 0)))
   
   println("dropWhile (x<=3) in List() = " +
           dropWhile(List(), (x:Int) => (x <= 3))) 
 }
}

// Output
/**
 * dropWhile (x<=3) in List(1,2,3,4,5) = Cons(4,Cons(5,Nil))
 * dropWhile (x<0) in List(1,2,3,4,5) = Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))
 * dropWhile (x<=3) in List() = Nil
 * /

3.6.scala

/**
 * Not everything works out so nicely. Implement a function, init, that returns a List consisting of all but the last element of a List. So, given List(1,2,3,4), init will return List(1,2,3). Why can’t this function be implemented in constant time like tail?
 * def init[A](l: List[A]): List[A]
 */
def init[A](l: List[A]): List[A] = {
  init(l, Nil)
}

private def init[A](in: List[A], out: List[A]): List[A] = in match {
  case Nil => Nil
  case Cons(last, Nil) => out
  case Cons(head, tail) => init(tail, append(out, List(head)))
}

// Note: It makes use of append function provided in code
def append[A](a1: List[A], a2: List[A]): List[A] =
  a1 match {
    case Nil => a2
    case Cons(h,t) => Cons(h, append(t, a2))
  }

 // Run
 object Solution {
 def main(args:Array[String]): Unit = {
   import List._
   
   println("init for List(1,2,3,4): " + init(List(1,2,3, 4)))
   println("init for List(1): " + init(List(1)))
   println("init for List(): " + init(List()))
 }
}

//Output
/**
 * init for List(1,2,3,4): Cons(1,Cons(2,Cons(3,Nil)))
 * init for List(1): Nil
 * init for List(): Nil
 */

3.9.scala

/**
 * Compute the length of a list using foldRight.
 * def length[A](as: List[A]): Int
 */
def length[A](as: List[A]): Int = {
  foldRight(as, 0)((_, a) => a + 1)
}

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
  as match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
  }

// Run
object Solution extends App {
  import List._

  println("length List(1,2,3): " + length(List(1,2,3)))
  println("length List(1): " + length(List(1)))
  println("length List(): " + length(List()))
  println("length Nil: " + length(Nil))
}

// Output
/**
 * length List(1,2,3): 3
 * length List(1): 1
 * length List(): 0
 * length Nil: 0
 */