Scala by code and comments - Part 3

This article is part 3 of a 4-part series called Scala code and comments

Preface

Please check the previous articles of the series if you haven't already.

Best way to learn a new language is to code it. I've found this helpful blog The digital cat that has 20 scala problems and solutions (not 99 despite the title) and from what I saw, he got them from this blog and it also influenced from another list for prolog! So I decided to look at them. But like always, I had some different methods and notes, too.

So I decided to share them here. I choose a different style here. Since it is already explained in the original blog, I just wanted to share my codes (and tests) with my comments. I want to try this style and see what happens. At the end of the file you can see my WHAT I LEARNED? part which you can find some interesting facts and sources about the theme.

Tests

 1package org.eleventofifteen
 2
 3import org.scalatest._
 4import ElevenToFifteen._
 5
 6class ElevenToFifteenSuite extends FunSuite {
 7  test("11. Modified run-length encoding") {
 8    assert(encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e)))
 9  }
10
11  test("12. Decode a run-length encoded list") {
12    assert(decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))) == List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
13    assert(decode_either(List(Right((4, 'a)), Left('b), Right((2, 'c)), Right((2, 'a)), Left('d), Right((4, 'e)))) == List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
14  }
15
16  test("13. Run-length encoding of a list (direct solution)") {
17    assert(encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e)))
18    assert(encodeDirect_tailRecursive(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e)))
19  }
20
21  test("14. Duplicate the elements of a list") {
22    assert(duplicate(List('a, 'b, 'c, 'c, 'd)) == List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd))
23  }
24
25  test("15. Duplicate the elements of a list a given number of times") {
26    assert(duplicate(List('a, 'b, 'c, 'c, 'd), 3) == List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd))
27  }
28}

Solutions

 1package org.eleventofifteen
 2
 3import scala.annotation.tailrec
 4import org.sixtoten.SixToTen.{ pack_foldRight => pack }
 5
 6object ElevenToFifteen extends App {
 7  // assert(encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e)))
 8  // author decides to use Either monad to represent a proper type system.
 9  // when your list has more than one consequtive element than your type is a tuple, in the other case is just the element
10  // we can read this type List[Either[A, (Int, A)]] as => List of elements that either A or (Int, A)
11  def encode_either[A](l: List[A]): List[Either[A, (Int, A)]] = {
12    pack(l).map(e => if (e.length == 1) Left(e.head) else Right((e.length, e.head)))
13  }
14
15  // assert(encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e)))
16  // I just want my simple List, than I need to use more general type which in this case is Any
17  def encode[A](l: List[A]): List[Any] = encode_either(l).map{ case Right(x) => x; case Left(x) => x }
18
19  // assert(decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))) == List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
20  def decode[A](l: List[(Int, A)]): List[A] = l.flatMap{ case (length, s) => List.fill(length)(s) }
21
22  // that was so easy. I want to try the either case
23  def decode_either[A](l: List[Either[A, (Int, A)]]): List[A] = l.flatMap{
24    case Right((length, s)) => List.fill(length)(s)
25    case Left(s) => List(s)
26  }
27
28  // now it's time to write an encode function with a built-in scala function: span
29  // assert(encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)) == List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e)))
30  def encodeDirect[A](xs: List[A]): List[(Int, A)] = xs match {
31    case Nil => Nil
32    case _ => {
33      val (first, rest) = xs.span(_ == xs.head)
34      (first.length, first.head) :: encodeDirect(rest)
35    }
36  }
37
38  // this version is better because it is now tail recursive
39  // we should take attention to the order of the accumulator List that is added in reverse order in contrast to above
40  def encodeDirect_tailRecursive[A](xs: List[A]): List[(Int, A)] = {
41    @tailrec
42    def iterate(acc: List[(Int, A)], ys: List[A]): List[(Int, A)] = ys match {
43      case Nil => acc
44      case _ => {
45        val (first, rest) = ys.span(_ == ys.head)
46        iterate((first.length, first.head) :: acc, rest)
47      }
48    }
49
50    iterate(List(), xs).reverse
51  }
52
53
54  def duplicate[A](xs: List[A], n: Int = 2): List[A] = xs.flatMap(List.fill(n)(_))
55
56  /*
57   WHAT I LEARNED?
58
59   * Either is a abstract type that can be used for exceptions or like in this case for conditional types
60   * I can import and alias it like: original => alias
61   * I can use default parameter values and override them when necessary
62
63  */
64}

Wanna try?

You can clone my git repository and run tests with sbt.

1git clone https://github.com/dhalsim/scala-exercises.git
2cd scala-exercises
3sbt test

This article is part 3 of a 4-part series called Scala code and comments


blog comments powered by Disqus