Scala Hacking: Computing min and max of a List

There are several ways to accomplish this. Next code snippet shows how to compute min and max using reduceLeft.

val ls = List(1,2,3,4,5)

ls.reduceLeft(_ min _) // is equivalent to ls.min

ls.reduceLeft(_ max _) // is equivalent to ls.max

Same can be accomplished via foldLeft or foldRight.

ls.foldLeft(Int.MaxValue) (_ min _)

ls.foldLeft(Int.MinValue) (_ max _)

However, can we compute both min and max in one line? Check out the following snippet.

ls.map(
x=>(x,x)).reduceLeft(
(x,y) => (x._1 min y._1, x._2 max y._2)

An alternative is to use foldLeft:

ls.foldLeft
((Int.MaxValue, Int.MinValue))
((acc:(Int,Int),y:Int) => (acc._1 min y, acc._2 max y))

Constructing a balanced Binary Search Tree from a sorted List in O(N) time

This post discusses a O(n) algorithm that construct a balanced binary search tree (BST) from a sorted list. For instance, consider that we are given a sorted list: [1,2,3,4,5,6,7]. We have to construct a balanced BST as follows.

        4
        |
    2        6 
    |        |
  1   3   5     7

To do so, we use the following definition of Tree, described in Scala By Example book.

abstract class IntSet
case object Empty extends IntSet
case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet

One straight-forward approach would be to repeatedly perform binary search on the given list to find the median of the list, and then, to construct a balanced BST recursively. Complexity of such approach is O(nlogn), where n is the number of elements in the given list.

A better algorithm constructs balanced BST while iterating the list only once. It begins with the leaf nodes and construct the tree in a bottom-up manner. As such, it avoids repeated binary searches and achieves better runtime complexity (i.e., O(n), where n is the total number of elements in the given list). Following Scala code outlines this algorithm, which effectively converts a list ls to an IntSet, a balanced BST:

def toTree(ls: List[Int]): IntSet = {
def toTreeAux(ls: List[Int], n: Int): (List[Int], IntSet) = {
if (n <= 0)
(ls, Empty)
else {
val (lls, lt) = toTreeAux(ls, n / 2) // construct left sub-tree
val x :: xs = lls // extract root node
val (xr, rt) = toTreeAux(xs, n - n / 2 - 1) // construct right sub-tree
(xr, IntSet(x, lt, rt)) // construct tree
}
}
val (ls_1, tree) = toTreeAux(ls, List.length(ls))
tree
}
view raw toTree.scala hosted with ❤ by GitHub

Any comment or query regarding this post is highly appreciated. Thanks.

“Functional Scala” by Mario Gleichmann

"Functional Scala" is a set of tutorials on Scala programming language by Mario Gleichmann. Although a bit verbose, it introduces the key constructs of Scala, and outlines Scala’s primary features from the perspective of functional programming.

Welcome to the first part of a series of episodes about ‘Functional Scala’. While positioning itself as a so called object-functional language, most of the discussion and articles about Scala centered around its object oriented features so far. If you’re reading this, chances are you want to learn more about the functional side of Scala. Well, you’ve come to the right place.

The idea for the following episodes arose out of some talks i gave about ‘Functional Scala’. I decided to write and talk about it because I wanted to solidify my own knowledge about Functional Programming in general and about Scala in particular … and because I thought I could help some people new to Scala to learn its functional features from my perspective.

Not least, there were some critical discussions in the past whether Scala is rightfully characterized as a functional Language. For this to decide, we firstly have to be clear about the core ideas, you’ll regularly come across within widely accepted functional Languages, like Haskell. We’re going to see if and how they are offered in Scala and try to push them to its limits. So without any further ado, let’s enter the world of Functional Programming (FP) in Scala.

Cheers!

“The Neophyte’s Guide to Scala” by Daniel Westheide

This Scala tutorial, called "The Neophyte’s Guide to Scala" can be considered as an auxiliary resource of #progfun. It is particularly good at getting started with Scala, and to delve a bit deeper with it.

From November 2012 to April 2013, I created and published a blog series called , targeted at aspiring Scala enthusiasts who have already made their first steps with the language and are looking for more detailed explanations.

Enjoy!

Project Euler 03. Largest prime factor with Scala

Problem Definition

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Source: https://projecteuler.net/problem=3

Solution

object Euler03 {

  type Factor = Long
  type Number = Long
  type Factors = List[Factor]

  /* Returns the largest prime factor of the given
   * number.It first computes all the prime factors of the given
   * number and then returns the largest among them.
   */
  def largestPrimeFactor (x: Number): Factor = 
    primeFactors(x).max


  /* Returns the prime factors of the given number x. For instance
   * if the number x equals to 5, it returns List(2,3).
   */
  def primeFactors(x: Number): Factors = {
    val numUpToSqrt = (2L to math.sqrt(x).toLong)
    val divisibleBy = numUpToSqrt.find(x % _ == 0)

    divisibleBy match {
      case None =>  List(x) 
      // x is a prime number and not divisible by any
      case Some(d) => d :: primeFactors(x/d)
    }
  }
}