FP in Scala - exercises

exercise_2.01.scala

def fib(n:Int):Int = {
	@annotation.tailrec
	def _fib(count:Int, x1:Int, x2:Int):Int = {
		val current = x1+x2
		if (count == n)  current
		else _fib(count+1, x2, current)
	}

	if (n == 1) 0
	else if (n == 2) 1
	else _fib(3, 0, 1)
}

exercise_2.02.scala

def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean = {
	@annotation.tailrec
	def _isSorted(head:A, rest:Array[A], previous:Boolean): Boolean = {
		if (!previous || rest.isEmpty) previous
		else {
			val newHead = rest.head
			_isSorted(newHead, rest.tail, ordered(head, newHead))
		}
	}
	if (as.isEmpty) true
	else _isSorted(as.head, as.tail, true)
}

exercise_2.03.scala

def curry[A,B,C](f: (A, B) => C): A => (B => C) = {
	(a: A) => ((b:B) => f(a,b))
}

exercise_2.04.scala

def uncurry[A,B,C](f: A => B => C) : (A, B) => C = {
	(a: A, b: B) => f(a)(b)
}

exercise_2.05.scala

def compose[A,B,C](f: B => C, g: A => B): A => C = {
	(a: A) => f(g(a))
}

exercise_3.01.scala

3 // ;-)

exercise_3.02.scala

def tail[A](as: List[A]): List[A] = {
	as match {
		case Nil => Nil
		case Cons(_, t) => t
	}
}

exercise_3.03.scala

def setHead[A](as: List[A], h:A): List[A] = {
	as match {
		case Nil => Cons(h, Nil) // List(h) as well
		case Cons(_, t) => Cons(h, t)
	}
}

exercise_3.04.scala

def drop[A](as: List[A], n:Int): List[A] = {
	as match {
		case Nil => Nil
		case Cons(_, t) if n == 0 => as
		case Cons(_, t) => drop(t, n-1)
	}
}

exercise_3.05.scala

def dropWhile[A](as: List[A], f: A => Boolean): List[A] = {
	as match {
		case Nil => Nil
		case Cons(h, t) if !f(h) => as
		case Cons(h, t) => dropWhile(t, f)
	}
}

exercise_3.09.scala

def length[A](as: List[A]): Int = {
	foldRight(as, 0)((_, acc) => 1+acc)
}

exercise_3.10.scala

@annotation.tailrec
def foldLeft[A,B](as: List[A], z: B)(f:(B, A) => B) : B = {
	as match {
		case Nil => z
		case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
	}
}

exercise_3.11.scala

def sum(ints:List[Int]): Int = foldLeft(ints, 0)(_ + _)
def product(ints:List[Int]): Int = foldLeft(ints, 1)(_ * _)
def length[A](as:List[A]): Int = foldLeft(as, 0)((acc, _) => acc+1)

exercise_3.12.scala

def reverse[A](as:List[A]): List[A] = 
	foldLeft(as, Nil:List[A])((acc, a) => Cons(a, acc)) 

exercise_3.14.scala

def append[A](a1: List[A], a2: List[A]): List[A] = 
	foldRight(a1, a2)((a, acc) => Cons(a,acc))

exercise_3.15.scala

def concat[A](aas: List[List[A]]): List[A] = 
	foldRight(aas, Nil:List[A])(append)

exercise_3.16.scala

def addOne(ints: List[Int]): List[Int] = 
	foldRight(ints, Nil:List[Int])((a, acc) => Cons(a+1, acc)) 

exercise_3.17.scala

def doubleToString(doubles: List[Double]): List[String] = 
	foldRight(doubles, Nil:List[String])((d, acc) => Cons(d.toString, acc)) 

exercise_3.18.scala

def map[A, B](as: List[A])(f: A => B): List[B] = 
	foldRight(as, Nil:List[B])((a, bs) => Cons(f(a), bs)) 

exercise_3.19.scala

def filter[A](as:List[A])(f: A => Boolean): List[A] = 
  foldRight(as, Nil:List[A])((a, acc) => if (f(a)) Cons(a,acc) else acc)

exercise_3.20.scala

def flatMap[A,B](as:List[A])(f: A => List[B]): List[B] = 
	foldRight(as, Nil:List[B])((a,acc) => append(f(a),acc))

exercise_3.21.scala

def filter[A](as:List[A])(f: A => Boolean): List[A] = {
	flatMap(as)(a => if (f(a)) List(a) else Nil)
}

exercise_3.22.scala

def zip(int1:List[Int], int2:List[Int]): List[Int] = {
	(int1, int2) match {
		case (a,Nil) => a
		case (Nil,b) => b
		case (Cons(h1,t1),Cons(h2,t2)) => append(List(h1 + h2), zip(t1, t2))
	}
}

exercise_3.23.scala

def zipWith[A](a1:List[A], a2:List[A])(f: (A, A) => A): List[A] = 
	(a1, a2) match {
		case (a,Nil) => a
		case (Nil,b) => b
		case (Cons(h1,t1),Cons(h2,t2)) => append(List(f(h1,h2)), zipWith(t1, t2)(f))
	}

exercise_3.24.scala

def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
	def _match[A](as:List[A], seq:List[A]): Boolean = {
		(as, seq) match {
			case (_, Nil) => true
			case (Nil, _) => false
			case (Cons(h1, t1), Cons(h2, t2)) if (h1 == h2) => _match(t1, t2)
			case (Cons(h1, t1), Cons(h2, t2)) if (h1 != h2) => _match(t1, sub)
		}
	}
	_match(sup, sub)
}

exercise_3.25.scala

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

exercise_3.26.scala

def maximum(tree:Tree[Int]): Int = 
	tree match {
		case Leaf(a) => a
		case Branch(l, r) => maximum(l) max maximum(r)
	}

exercise_3.27.scala

def depth[A](tree:Tree[A]): Int = 
	tree match {
		case Leaf(a) => 1
		case Branch(l, r) => 1 + (depth(l) max depth(r))
	}

exercise_3.28.scala

def map[A, B](tree:Tree[A])(f:A => B): Tree[B] = {
	def mapT = map(_:Tree[A])(f)
	tree match {
		case Leaf(a) => Leaf(f(a))
		case Branch(l, r) => Branch(mapT(l), mapT(r))
	}
}

exercise_3.29.scala

def size[A](tree:Tree[A]): Int = fold(tree)(Function.const(1))((a,b) => 1 + size(a) + size(b))
def maximum(tree:Tree[Int]): Int = fold(tree)(identity)((a, b) => maximum(a) max maximum(b))
def depth[A](tree:Tree[A]): Int = fold(tree)(Function.const(1))((a,b) => 1 + (depth(a) max depth(b)))
def map[A, B](tree:Tree[A])(f:A => B): Tree[B] = fold(tree)(a => Leaf(f(a)):Tree[B])((a,b) => Branch(map(a)(f), map(b)(f)))
def fold[A, B](tree:Tree[A])(f1: A => B)(f2: (Tree[A], Tree[A]) => B): B = {
	tree match {
		case Leaf(a) => f1(a)
		case Branch(left, right) => f2(left, right)
	}
}