#8 of 99 Problems – Eliminate consecutive duplicates of list elements.

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

This problem again relies on the functionality built into Scala collections and I don’t add much to the original solution.

Problem:
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
Example:

var result = compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
println("Result = " + result)

Output: Result = List(‘a, ‘b, ‘c, ‘a, ‘d, ‘e)

Answer:

object Class08 extends App {

  def compress[A](ls: List[A]): List[A] = ls match {
    case Nil       => Nil
    case h :: tail => h :: compress(tail.dropWhile(_ == h))
  }

  var result = compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

This is a good example of using dropWhile, classified as a ‘subiterator’ here – http://www.scala-lang.org/docu/files/collections-api/collections_43.html

Advertisements

#7 of 99 Problems – flatten a list

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

This problem is deeply rooted in the functional programming side of scala, which is not my strongest subject as I come from an OO background. I cannot add to the original solution given and merely post the solution here for completeness – there is no point posting 90 or so of 99 problems 🙂

Anyway, here it is…

Question:
Flatten a nested list structure.
Example:

var result = flatten(List(List(1, 1), 2, List(3, List(5, 8))))
println("Result = " + result)

Output: Result = List(1, 1, 2, 3, 5, 8)

Answer:

object Class07 extends App {
  def flatten(ls: List[Any]): List[Any] = ls flatMap {
    /* this is an example of pattern matching on type, here
     * the code says 'if this item is itself a list'
     */
    case ms: List[_] => flatten(ms)
    // this matches any other item
    case e => List(e)
  }
  var result = flatten(List(List(1, 1), 2, List(3, List(5, 8))))
  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

#6 of 99 Problems – is a list a palindrome in scala

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

This is more involved than previous problems. We are checking if a list is a palindrome and we will do this, as in previous problems, using pattern matching on the List. I use 3 scenarios which would be ifs in Java.

  1. If the list is less than 2 items it is empty or has 1 item. I count these as being palindromes.
  2. If the head (first item) and the last (last item) are the same then it might be – let’s recurse 🙂
  3. If 2 items or more and first and last differ then return false.

This means using an if in our case to check first and last items in the 2nd scenario.

A note on pattern matching: The line of code below will create 2 values from the list – head and tail – where head is the first item and tail is everything else. It makes matching and recursion simpler.

case head::tail => // do something...

Anyway, here’s the code:

Question:
Find out whether a list is a palindrome.
Example:

var result = isPalindrome(List(1, 2, 3, 2, 1))
println("Result = " + result)

Output: Result = true

Answer:

import scala.annotation.tailrec

object Class06 extends App {

  var result = isPalindrome(List(1, 2, 3, 2, 1))
 
  @tailrec // we expect tail-recursive optimization
  def isPalindrome(l:List[Any]):Boolean = l match {
    case yes if(l.length < 2) => true  // true if small enough
    case head::tail if (head==tail.last) => isPalindrome(tail.init) // recurse without first and last
    case _ =>  false // this is like an else
  }   

  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

This shows some of the features of pattern matching in scala. The word yes is just a name I’ve given to the first case which runs off the if condition. There is a convention to use an underscore for catch-all cases, a convention I follow here. The original list of questions doesn’t show anything beyond list==list.reverse but I think this answer is a good example of recursion and pattern matching.

#5 of 99 Problems – Reverse a List in scala

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

This example reverses the list purely as an example of writing a recursive function in scala. Like the other examples I’ve written, the aim is simple code, not necessarily the most performant and not using built in List functionality per se.

Question:
Reverse a List
Example:

var result = reverse(List(1, 1, 2, 3, 5, 8))
println("Result = " + result)

Output: Result = List(8, 5, 3, 2, 1, 1)

Answer:

object Class05 extends App {

  // l is Parameter of type List[Any] and return is of type List[Any]
  def reverse(l:List[Any]): List[Any] = l match {
    case Nil => l // if empty list passed return it and stop recursion
    case head :: tail => reverse(tail) ::: List(head)     // recurse with all but first items, appending first item.
  }   

  val result = reverse(List(1, 1, 2, 3, 5, 8))
  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

This is an example of a pattern of writing recursive functions but breaking out of the recursion when our list is exhausted. I must admit – the original 99 problem post provides more elegant solutions than I am capable of and is worth a look to see other ways of achieving the same thing,

#4 of 99 Problems – count items in a list

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

The easiest way to get the item count for a List in scala is to use the size or length functions provided by List. This answer is an example of writing a function in scala, more specifically a recursive function without side-effects.

Question:
Find the number of elements of a list.
Example:

var result = length(List(1, 1, 2, 3, 5, 8))
println("Result = " + result)

Output: Result = 6

Answer:

object Class04 extends App {

  // Outer function:  
  def length(l:List[Any]):Int = {

    // Inner function:
    @tailrec
    def length(count:Int, l:List[Any]):Int = l match {
      case head::tail => length(count + 1, tail) // recurse
      case Nil        => count                   // empty list so return count
    }

    // call that recursive inner function with initial state:
    length(0, l)
  }

  val result = length(List(1, 1, 2, 3, 5, 8))
  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

This is an example of a pattern of writing recursive functions – an outer and an inner function. The outer function creates the starting point and calls the inner recursive function which exhaustively iterates, in this case through a list.

#3 of 99 Problems

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

Question:
Find the Kth element of a list.
By convention, the first element in the list is element 0.
Example:

var result = nth(2, List(1, 1, 2, 3, 5, 8))
println("Result = " + result)

Output: Result = 2

Answer:

object Class03 extends App {

  @tailrec
  def nth(n:Int, l:List[Any]):Any = (n,l) match {
    case (0, head::tail) => head // return top item when counter reaches zero
    case (_, head::tail) => nth(n-1, tail) // recurse with counter-1 and list minus top element.
  }

  val result = nth(2, List(1, 1, 2, 3, 5, 8))
  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

This pattern for decrementing a counter without a temporary variable is common in functional programming.

#2 of 99 Problems

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

Question:
Find the last but one element of a list.
Example:

val result = penultimate(List(1, 1, 2, 3, 5, 8))
println("Result = " + result)

Output: Result = 5

Answer:

object Class02 extends App {

  @tailrec
  def penultimate(l:List[Any]):Any = l match {
    case head::tail if (tail.length == 1) => head // return top item if only 1 item left
    case head::tail                       => penultimate(tail) // otherwise recurse
  }

  val result = penultimate(List(1, 1, 2, 3, 5, 8))
  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

The @tailrec tells the compiler that we are expecting tail-recursion optimisation and to error if it is not able to perform this.