Scala by code and comments - Part 4
- Part 1 - Scala by code and comments - Part 1
- Part 2 - Scala by code and comments - Part 2
- Part 3 - Scala by code and comments - Part 3
- Part 4 - Scala by code and comments - Part 4
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
Next page? NoSuchElementException
I have been finished The digital cat series. Now I need to continue from another source or finish the series altogether.
- Go on to the Original 99 Problems
- A topic from Scala Exercises
- Go back to the theory
- Something else
These are the ones that I could find. If you want to help me to decide, or recommend something, please leave a comment below.
- Part 1 - Scala by code and comments - Part 1
- Part 2 - Scala by code and comments - Part 2
- Part 3 - Scala by code and comments - Part 3
- Part 4 - Scala by code and comments - Part 4