Scaled Code - Getting started with Scala: February 2014

Thursday, February 27, 2014

Currying

What is currying?

Let's assume we have function foo()

def foo = { ... }

Table of contents...

Wednesday, February 19, 2014

STM - Software Transactional Memory

Table of contents...

What is STM?

STM stands for Software Transactional Memory

ScalaSTM is inspired by Clojure STM

Configure project

Using sbt (Scala Build Tool)

libraryDependencies += ("org.scala-stm" %% "scala-stm" % "0.7")

Add dependency to pom.xml (for Scala 2.10)

<dependencies>
  <dependency>
    <groupId>org.scala-stm</groupId>
    <artifactId>scala-stm_2.10</artifactId>
    <version>0.7</version>
  </dependency>
</dependencies>

Prerequisites

Required imports

import scala.concurrent.stm._

Useful classes and methods

Ref, atomic, repeat

A Ref

A Ref wraps a value and makes it transactional. Once value is wrapped, it's impossible to get or set the value outside of transcation

val userCount = Ref(42)

Following attempt to call Ref.set() will not compile

userCount.get() //will not compile

Output

Exception:CompilerException: Compiler exception error: line 5: not enough arguments for method get: (implicit txn: scala.concurrent.stm.InTxn)Int.
Unspecified value parameter txn.
userCount.get() //will not compile
             ^

the same with Ref.set() method

userCount.set() //will not compile

Output

Exception:CompilerException: Compiler exception error: line 5: not enough arguments for method set: (v: Int)(implicit txn: scala.concurrent.stm.InTxn)Unit.
Unspecified value parameter v.
userCount.set() //will not compile
             ^

Compiler says that both methods have implicit parameter called txn. It represents current transaction. The only way to access value from ref is to call get/set method in transaction

Atomic - All or nothing

ScalaSTM allows you to make block of code atomic. That means from the rest of code you cannot see any partial change in this block. atomic block is marked by word "atomic"
Common template to make block of code atomic

val result = atomic { implicit tx => /*your code here*/ }

val x1 = atomic { userCount.get(_) }  //() (result)

val x2 = atomic { implicit tx => userCount.get }  //() (result)

Accessing value out of atomic

Following method will create transaction only for the duration of the call

userCount.single() //this will work //42 (result)

and is equivalent to

atomic { userCount.get(_) }  //42 (result)

Short forms of Ref.get/Ref.set

Ref.set

atomic { implicit tx => userCount.set(56) } //() (result)

has shorter form

atomic { implicit tx => userCount() = 56 } //() (result)

Ref.get

atomic { implicit tx => val x = userCount.get; x } //42 (result)

has shorter form

atomic { implicit tx => val x = userCount(); x } //42 (result)

Example

atomic { implicit tx => "Hello world!" }

Output

Hello world!

Conversions in scala

Table of contents...

Implicit keyword

implicit - keyword means that compiler should try to use function or variable even if it's not explicitly specified in code.
implicit variables and functions are:

used automatically by compiler

used only when there's no other explicit application available.

How to add implicit conversion

Let say we want to add special debug method to every object in code. That method should return toString of object followed by length of this string.

We could just add trait to each class (represented by X here)

trait HasDebugString {
    def toDebugString = 
        this.toString + " " + this.toString.length
}
class X extends HasDebugString

but it's impossible when we use third party code

We can extend existing classes and add trait

class XDebug extends X with HasDebugString

But we don't want to do this for each class in project, right?

Also we can wrap instance of class (represented by X here)

case class X(text : String) 
class DebugStringWrapper(instance : X) {
    def toDebugString =
        instance.toString + instance.toString.length
}
def wrap(instance : X) = new DebugStringWrapper(instance);
wrap(new X("ABC")).toDebugString
 //X(ABC)6 (result)

Again... But we don't want to do this for each class in project, right? We can use generic type parameter... (sponsored by letter T)

//written only once
class DebugStringWrapper[T](instance : T) {
    def toDebugString =
        instance.toString + instance.toString.length
}
def wrap[T](instance : T) = new DebugStringWrapper(instance);

Other parts of code can use wrapper

case class X(text : String)

wrap(new X("ABC")).toDebugString //X(ABC)6 (result)

wrap(new X("ABC")).toDebugString //X(ABC)6 (result)

wrap(6).toDebugString //61 (result)

wrap("ABC").toDebugString //ABC3 (result)

wrap(List(1,2)).toDebugString //List(1, 2)10 (result)

wrap is annoying, can we tell compiler to use wrap every time when we use toDebugString method on object?

wrap(6).toDebugString == 6.toDebugString

Actually we can... implicit magic...

implicit def hiddenwrap[T](instance : T) = new DebugStringWrapper(instance);

wrap(List(1,2)).toDebugString //List(1, 2)10 (result)

hiddenwrap(List(1,2)).toDebugString //List(1, 2)10 (result)

List(1,2).toDebugString //List(1, 2)10 (result)

We've declared DebugStringWrapper class and we use it only in 1 place. It can be replaced with anonymous class

implicit def hiddenwrap[T](instance : T) = new {
    def toDebugString = instance.toString + instance.toString.length
}

List(1,2,3).toDebugString //List(1, 2, 3)13 (result)

How to add operator to existing class

In Scala operators are just methods
Postfix operators are bound to left of operand. They're easy to implement

implicit def opwrap[T](instance : T) = new {
    def ! = instance.toString + instance.toString.length
}

List(1,2,3).! //List(1, 2, 3)13 (result)

The difference is that you can skip a dot

List(1,2,3)! //List(1, 2, 3)13 (result)

How to add prefix operator to existing class

Prefix operator method name has to start with "unary_"

implicit def opwrap2[T](instance : List[T]) = new {
    def unary_! = instance.isEmpty
}

println(!List(1,2,3)) //() false(result)

println(!Nil) //() true(result)

println(List(1,2,3).!) //() List(1, 2, 3)13(result)

How to add infix operator to existing class

Infix operators take two operands one from left and one from right.
Here operator (!) takes two lists with elements of type TR and TL and returns smaller of them

implicit def opwrap3[TL](instance : List[TL]) = new {
    def ![TR](other : List[TR]) = 
        if (instance.length > other.length) instance else other
}

List(1,2,3) ! List("A","B") //List(1, 2, 3) (result)

List(1,2,3).!(List("A","B")) //List(1, 2, 3) (result)

opwrap3(List(1,2,3)).!(List("A","B")) //List(1, 2, 3) (result)

Infix operator names with colons

If infix operator name ends with colon (":") then operator is bound to right term

implicit def opwrap4[TL](instance : List[TL]) = new {
    def !:[TR](other : List[TR]) = 
        instance + ".!:(" + other + ")"
}

List(1,2,3) !: List("A","B") //List(A, B).!:(List(1, 2, 3)) (result)

List("A","B").!:(List(1,2,3)) //List(A, B).!:(List(1, 2, 3)) (result)

opwrap4(List("A","B")).!:(List(1,2,3)) //List(A, B).!:(List(1, 2, 3)) (result)

Common errors

You've declared 2 implicit methods hiddenwrap, hiddenwrap2 and both can be applied

List(1,2,3).toDebugString

found : List[Int]
required: ?{def toDebugString: ?}
Note that implicit conversions are not applicable
because they are ambiguous:
 both method hiddenwrap2 of type 
     [T](instance: T)AnyRef{def toDebugString: String}
 and method hiddenwrap of type 
     [T](instance: T)DebugStringWrapper[T]
 are possible conversion functions 
     from List[Int]to ?{def toDebugString: ?}

Implicit conversion does not work with existing methods...
You cannot use implicit methods to override existing methods. Implicit method is applied only if method does not exists in class

implicit def happystring[T](instance : T) = new {
	override def toString = instance.toString + ":)"
	def withSmiley = instance.toString + ":)"
}

//BAD: X has toString method

println(X("I'm sad").toString) //() X(I'm sad)(result)

//GOOD: toString is not found in X, so implicit conversion will be applied

println(X("I'm happy").withSmiley) //() X(I'm happy):)(result)

Tuesday, February 18, 2014

Dictionary

Type parameters- Types in scala can be parametrized. That means you can add additional information that goes with main type.

List[Double](1,2,3) //List(1.0, 2.0, 3.0) (result)

List[String]("A","B","C") //List(A, B, C) (result)

This information is not available at runtime. Instead are types are replaced with "Any" type

Pure function - does not have any side effects.
- rest of code can affect processing only by giving input - functions can affect rest of code only by result

Traversable- Base type for all Scala collections
- contains foreach method
- might be strict (List) or non-strict (Stream)
- might be ordered (Seq) or non-ordered (Set)

strict collection- all elements are computed when collection is computed.

non-strict collection- (lazy collection) - computation of elements may be deferred.

persistent collection
- immutable
- operations on collection return new updated structure
- updated structure reffers to original and contains only differences
- memory efficient

val items1 = List(1,2,3)
val items2 = items1.updated(1, "A")

- there's no way to modify original collection (items1)
- though update method returns new collection (items2)
- new collection contain only changes and reference to original
- old items are shared by both collections

immutable- once created object does not change

REPL- (Run-Eval-Print Loop) - shell for Scala.
Simple programming enviroment where user enters expressions, next they are evaluated, results are printed and process is repeated.

scala
Welcome to Scala version 2.10.3 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_25).
Type in expressions to have them evaluated.
Type :help for more information.

scala> println("Hello world")
Hello world

scala> exit

Flatmap

flatMap is map then flatten

flatten requires that each element is traversable

flatMap has something to do with burrito

Table of contents...

flatten

Flatten reduces one level of any Traversable

List(List(1),List(2),List(3))
	.flatten //List(1, 2, 3) (result)

Option is Traversable with 0 or 1 elements

Some("A").size //1 (result)

None.size //0 (result)

List(Some(1),Some(2),Some(3))
	.flatten //List(1, 2, 3) (result)

Flatten can be applied to any Traversable

List(Map(1->3),Map(1->8),Map(5->"A"))
	.flatten //List((1,3), (1,8), (5,A)) (result)

flatten can be applied to Nil

Nil.flatten //List() (result)

flatten and map

define items...

val items = List(List("X"),List(2),List(3))

items //List(List(X), List(2), List(3)) (result)

typeOf(items) //List[List[Any]] (result)

and function foo. Function must return a traversable

def foo(x : List[Any]) : List[String]= List("foo(" + x + ")")

apply map to each item

val mapitems = items.map(foo)

mapitems

Output

List(List(foo(List(X))), List(foo(List(2))), List(foo(List(3))))

typeOf(mapitems) //List[List[String]] (result)

apply flatten to the result of map

val flatmapitems = mapitems.flatten

flatmapitems

Output

List(foo(List(X)), foo(List(2)), foo(List(3)))

typeOf(flatmapitems) //List[String] (result)

flatMap

flatMap is map then flatten...

val flatmapitems2 = items.flatMap(foo)

flatmapitems2

Output

List(foo(List(X)), foo(List(2)), foo(List(3)))

typeOf(flatmapitems2) //List[String] (result)

flatMap usecases

join few lists...

Monday, February 17, 2014

Map, Scan, Fold and Reduce functions

Map, Scan, Fold and Reduce

Assume we have items var

items //List(1, 2, 6, 4, 2, 1) (result)

Map function

We can map each item to another value, but we need to define how to do it. We need unary operator or single argument function

def how1(currentItem : Int) = currentItem * 2

and then apply it to each item

items.map(how1) //List(2, 4, 12, 8, 4, 2) (result)

items.map(how1(_)) //List(2, 4, 12, 8, 4, 2) (result)

We can replace

items.map(how1) //List(2, 4, 12, 8, 4, 2) (result)

with

val result0 = how1(items(0)) // 2
val result1 = how1(items(1)) // 4
val result2 = how1(items(2)) // 12
// ...
val resultn = how1(items(n)) // 2
val result = List(result0, ..., resultn) // List(2, 4, 12, 8, 4, 2)

Since vars result0, result1, ... resultn are independent we can evaluate them in any order.

Scan function

If we assume some processing order of items (e.g. from left (first to last) or from right (last to first)), then we can make use of previous result in subsequent calculation. That means we can scan items.



val result0 = do_something_with(???, items(1))
val result1 = do_something_with(result0, items(1))
val result2 = do_something_with(result1, items(2))
// ...
val resultn = do_something_with(resultn-1, items(n))
val result = List(result0, ..., resultn)

We must define how to do_something_with previous result and current item. We need binary operator or two argument function

def how2(prevResult : Int, currentItem : Int) 
 = prevResult * currentItem + 1

But for result0 there's no previous result, instead we provide some_input

val result0 = do_something_with(some_input, items(1))

Replace do_something_with with how2.

val input = ???
val result0 = how2(input, items(1))
val result1 = how2(result0, items(1))
val result2 = how2(result1, items(2))
// ...
val resultn = how2(resultn-1, items(n))
val result = List(input, result0, ..., resultn)

Then we can shorten to form

items.scan(input)(how2)

Time to provide input value

items.scan(0)(how2v)

Code result

List(0, 1, 3, 19, 77, 155, 156)

Output

how2(0, 1)=1
how2(1, 2)=3
how2(3, 6)=19
how2(19, 4)=77
how2(77, 2)=155
how2(155, 1)=156

Execution time: 1 Result scan returns input followed by calculated results

input :: results

Scan function examples

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.scan(0)(_+_)

Output

Product of items

items.scan(1)(_*_)

Output

As expression

items.scan("input")("f(" + _ + ", " + _ + ")")

Output

input
f(input, 1)
f(f(input, 1), 2)
f(f(f(input, 1), 2), 6)
f(f(f(f(input, 1), 2), 6), 4)
f(f(f(f(f(input, 1), 2), 6), 4), 2)
f(f(f(f(f(f(input, 1), 2), 6), 4), 2), 1)

empty list

List().scan(0)(_+_) //List(0) (result)

single element list

List(0).scan(0)(_+_) //List(0, 0) (result)

Fold function

Scan function returns input and all intermediate results. If we need only last of them then we can fold items.

items.scan(0)(how2)

Output

If we need only last result, we can use

items.scan(0)(how2).last //156 (result)

or shorter form fold instead of scan

items.fold(0)(how2) //156 (result)

Fold function examples

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.fold(0)(_+_) //16 (result)

Product of items

items.fold(1)(_*_) //96 (result)

As expression

items.fold("input")("f(" + _ + ", " + _ + ")")

Output

f(f(f(f(f(f(input, 1), 2), 6), 4), 2), 1)

empty list

List().fold(0)(_+_) //0 (result)

single element list

List(0).fold(0)(_+_) //0 (result)

Reduce function

We can split items

items //List(1, 2, 6, 4, 2, 1) (result)

into head

items.head //1 (result)

and tail

items.tail //List(2, 6, 4, 2, 1) (result)

then use scan function

items.tail.scan(items.head)(how2) //List(1, 3, 19, 77, 155, 156) (result)

if we need just last element...

items.tail.fold(items.head)(how2) //156 (result)

Or use shorter form

items.reduce(how2) //156 (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.reduce(_+_) //16 (result)

Product of items

items.reduce(_*_) //96 (result)

As expression

items.map(_.toString).reduce("f(" + _ + ", " + _ + ")")

Output

f(f(f(f(f(1, 2), 6), 4), 2), 1)

empty list

List[Int]().reduce(_+_)

Output

Exception:empty.reduceLeft

single element list

List[Int](0).reduce(_+_) //0 (result)

Left and Right functions

items.map is not left nor right items.scan is eqivalent to items.scanLeft

items.scan(0)(_+_) //List(0, 1, 3, 9, 13, 15, 16) (result)

items.scanLeft(0)(_+_) //List(0, 1, 3, 9, 13, 15, 16) (result)

items.fold is eqivalent to items.foldLeft

items.fold(0)(_+_) //16 (result)

items.foldLeft(0)(_+_) //16 (result)

items.reduce is eqivalent to items.reduceLeft

items.reduce(_+_) //16 (result)

items.reduceLeft(_+_) //16 (result)

scanRight

items.scanRight(0)(_+_) //List(16, 15, 13, 7, 3, 1, 0) (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.scanRight(0)(_+_)

Output

Product of items

items.scanRight(1)(_*_)

Output

As expression

items.scanRight("input")("f(" + _ + ", " + _ + ")")

Output

f(1, f(2, f(6, f(4, f(2, f(1, input))))))
f(2, f(6, f(4, f(2, f(1, input)))))
f(6, f(4, f(2, f(1, input))))
f(4, f(2, f(1, input)))
f(2, f(1, input))
f(1, input)
input

empty list

List[Int]().scanRight(0)(_+_) //List(0) (result)

single element list

List(0).scanRight(0)(_+_) //List(0, 0) (result)

foldRight

items.foldRight(0)(_+_) //16 (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.foldRight(0)(_+_) //16 (result)

Product of items

items.foldRight(1)(_*_) //96 (result)

As expression

items.foldRight("input")("f(" + _ + ", " + _ + ")")

Output

f(1, f(2, f(6, f(4, f(2, f(1, input))))))

empty list

List[Int]().foldRight(0)(_+_) //0 (result)

single element list

List(0).foldRight(0)(_+_) //0 (result)

reduceRight

items.reduce(_+_) //16 (result)

Examples
List items

items //List(1, 2, 6, 4, 2, 1) (result)

Sum of items

items.reduceRight(_+_) //16 (result)

Product of items

items.reduceRight(_*_) //96 (result)

As expression

items.map(_.toString).reduceRight("f(" + _ + ", " + _ + ")")

Output

f(1, f(2, f(6, f(4, f(2, 1)))))

empty list

List[Int]().reduceRight(_+_)

Output

Exception:Nil.reduceRight

single element list

List[Int](0).reduceRight(_+_) //0 (result)

Wednesday, February 12, 2014

How to use lists in Scala

Lists are....

persistent (immutable) - you cannot change it, but you can create copy

one-way - you can take next element, but not previous

ordered - each element has position

not unique - elements can be repeated in list

list take 1 parameter - type of element

recursive - they are either empty or a head followed by list

Table of contents...

Empty list

Nil //Nil is "The empty list." in Scala //List() (result)

List() //Empty list //List() (result)

List[AnyVal]() //List of numeric values //List() (result)

List.empty[AnyVal]//same as above //List() (result)

Type of an empty list

typeOf(Nil) //scala.collection.immutable.Nil.type (result)

typeOf(List()) //List[Nothing] (result)

typeOf(List[Nothing]()) //List[Nothing] (result)

typeOf(List[Any]()) //List of anything //List[Any] (result)

typeOf(List[String]()) //List of strings //List[String] (result)

typeOf(List.empty[String]) //List of strings //List[String] (result)

Are empty lists equal?

Yes.

Nil == List() //true (result)

List() == List[AnyVal]() //true (result)

List[AnyVal]() == List.empty[AnyVal] //true (result)

Lists of different types are equal if they're empty

List[Int]() == List[String]() //true (result)

Non-empty lists

List of Int's

val int_list = List(1, 2, 3)

typeOf(int_list) //List[Int] (result)

List of Strings

val string_list = List("1", "2", "3")

typeOf(string_list) //List[String] (result)

Mixing element type

Scala will try to keep most of information about type of elements
List of Strings and Int's
(common type is Any)

val mixed_list_si = List("1", 2, "3")

typeOf(mixed_list_si) //List[Any] (result)

List of Int's and Double's
(common type is AnyVal, there's conversion from int to double)

val mixed_list_id = List(1, 2.0, 3)

typeOf(mixed_list_id) //List[Double] (result)

List of Int's and BigInt's
(common type is Any)

val mixed_list_ibi = List(1, BigInt(2), 3)

typeOf(mixed_list_ibi) //List[Any] (result)

Getting elements of list

val items = List(1, 2, 3, 4.0)

head of list (first element)

items.head // fast, complexity O //1.0 (result)

head cannot be used on empty list

List().head

Output

Exception:java.util.NoSuchElementException: head of empty list

head is a 0-th element of list

items(0) == items.head //true (result)

last element (we must iterate all elements to get there)

items.last // slow, complexity N //4.0 (result)

n-th element (we must iterate n elements to get there)

items(3) // slow, complexity N //4.0 (result)

Size of list

size and length are eqivalent. Scala does not keep a counter of elements. We must iterate over all elements count them.

items.size   // slow, complexity N //4 (result)

items.length // slow, complexity N //4 (result)

Splitting list into head and tail

Split list to head and tail

val items_head::items_tail = items

//this will create 2 val's

items_head //1.0 (result)

items_tail //List(2.0, 3.0, 4.0) (result)

Empty list cannot be split (no head)

val empty_head::empty_tail = List()

Output

Exception:scala.MatchError: List() (of class scala.collection.immutable.Nil$)

val empty_head::empty_tail = List[Int]()

Output

Exception:scala.MatchError: List() (of class scala.collection.immutable.Nil$)

Single element list can be split info element and Empty list

5 :: Nil == List[Int](5) //true (result)

val single_head::single_tail = List[Int](5)

single_head //5 (result)

single_tail //List() (result)

Lists are recursive

List items

items //List(1.0, 2.0, 3.0, 4.0) (result)

is equivalent to

1.0::(2.0::(3.0::(4.0::(Nil))))

Output

List(1.0, 2.0, 3.0, 4.0)

Getting part of list

items //List(1.0, 2.0, 3.0, 4.0) (result)

Ignore 2 first elements, take the rest

items.drop(2) //fast //List(3.0, 4.0) (result)

Take 3 first elements, ignore the rest

items.take(3) //fast //List(1.0, 2.0, 3.0) (result)

typeOf(items.take(3)) //List[Double] (result)

drop and take work with empty lists

List().drop(2) //List() (result)

List().take(2) //List() (result)

and with list smaller than given number of elements

items.drop(20) //empty //List() (result)

items.take(20) //all list //List(1.0, 2.0, 3.0, 4.0) (result)

take n last elements

items.takeRight(4) //slow //List(1.0, 2.0, 3.0, 4.0) (result)

items.reverse.take(4) //slow //List(4.0, 3.0, 2.0, 1.0) (result)

drop n last elements

items.dropRight(4) //slow //List() (result)

items.reverse.drop(4) //slow //List() (result)

Iteration

def funny(x : Double) = x * 2

for(x <- 0 until items.length) yield funny(x)

Output

Vector(0.0, 2.0, 4.0, 6.0)

def foo(l : List[Double]) : List[Double]= l match {
	case Nil => Nil
	case h::t => funny(h)::foo(t)
}

foo(items)

Output

List(2.0, 4.0, 6.0, 8.0)

Why not map?

items.map(funny)

Output

List(2.0, 4.0, 6.0, 8.0)

Or parallel map?

items.par.map(funny)

Output

ParVector(2.0, 4.0, 6.0, 8.0)

Get index of element

items.zipWithIndex

Output

List((1.0,0), (2.0,1), (3.0,2), (4.0,3))

Then we can use map

items.zipWithIndex.map {ei => 
	var (element,index) = ei
	"items[" + index + "]=" + element}

Output

List(items[0]=1.0, items[1]=2.0, items[2]=3.0, items[3]=4.0)

...and partial function to extract item and index

items.zipWithIndex.map{case (item,index) => s"items[$index]=$item"}

Output

List(items[0]=1.0, items[1]=2.0, items[2]=3.0, items[3]=4.0)

Joining lists

int_list //List(1, 2, 3) (result)

typeOf(int_list) //List[Int] (result)

string_list //List(1, 2, 3) (result)

typeOf(string_list) //List[String] (result)

Join of two lists (list style)

int_list ::: string_list //List(1, 2, 3, 1, 2, 3) (result)

typeOf(int_list ::: string_list) //List[Any] (result)

Join of two lists (universal style)

int_list ++ string_list //List(1, 2, 3, 1, 2, 3) (result)

Adding element to list

int_list //List(1, 2, 3) (result)

typeOf(int_list) //List[Int] (result)

list-style add as head

100::items //List(100, 1.0, 2.0, 3.0, 4.0) (result)

(100::items).head //100 (result)

universal append as head

100+:items //List(100, 1.0, 2.0, 3.0, 4.0) (result)

(100+:items).head //100 (result)

universal append as last

items:+200 //List(1.0, 2.0, 3.0, 4.0, 200) (result)

(items:+200).last //200 (result)

Operators

colon operators :: and ::: are designed for Lists

colon operators +:,:+ and ++ are designed for all Traversables

+: and :+ are designed for use with all Traversables. since Scala 2.10 you can use them in pattern matching.

C.O.L.T. - COlons Like Traversables You should always put list or traversable near colon. (operators are bound to the side with colon)

2+:List(3,7) //List(2, 3, 7) (result)

is equivalent to

List(3,7).+:(2) //List(2, 3, 7) (result)

but

List(3,7):+2 //List(3, 7, 2) (result)

is equivalent to

List(3,7).:+(2) //List(3, 7, 2) (result)

Common usecases

Create list of length 4, filled with element 3

List.make(4, 3) //List(3, 3, 3, 3) (result)

Join list into String

List(5,2,1).mkString(" and ") //5 and 2 and 1 (result)

Join list into String with prefix and postfix

List(5,2,1).mkString("list contains ", " and ", ".") //list contains 5 and 2 and 1. (result)

Remove duplicates from list

List(1,1,0,1,1,0,0,1,2).distinct //List(1, 0, 2) (result)

Tuesday, February 4, 2014

Fibonacci

Leonardo Fibonacci was born in 1170 AD. He was an Italian mathematican.

Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21...

What is Fibonacci Sequence?

1. first two numbers are 0 and 1
2. each next element is a sum of two previous elements

Fibonacci(n) is equal to n-th element in Fibonacci Sequence

F(0)=0, F(1), F(2), F(3), ...

F(0), F(1), F(0) + F(1), F(1) + F(2), ...

0, 1, 1, 2, ...

Code in Scala

//Fibonacci01.main(Array())
object Fibonacci01 extends App {

  def fib(a : Int) : Int = {
    if (a == 0) 0 else 
    if (a == 1) 1 else 
    return fib(a - 1) + fib(a - 2)
  }
  
  println(fib(35))
}

Code result

()

Console output (click)

Execution time: 712 ms

Match/Case

//Fibonacci02.main(Array())
object Fibonacci02 extends App {

  /**
   * using match/case
   */
  def fib(a : Int) : Int = {
    a match {
      case 0 => 0
      case 1 => 1
      case n => fib(n - 1) + fib(n - 2)
    }
  }
  
  println(fib(35)) 
  // but fib(-1) will throw java.lang.StackOverflowError 
}

Code result

()

Console output (click)

Execution time: 695 ms Calling fib(-1) causes infinite loop.
Function Fibonacci is not defined for n < 0.

Match/Case using if

//Fibonacci03.main(Array())
object Fibonacci03 extends App {

  /**
   * function using match/case with if
   */
  def fib(a : Int) : Int = {
    a match {
      case 0 => 0
      case 1 => 1
      case n if (n > 1) => fib(n - 1) + fib(n - 2)
    }
  }
  
  println(fib(35))
  //fib(-1) throws scala.MatchError: 
}

Code result

()

Console output (click)

Execution time: 593 ms
Ok, nice, calling fib(-1) now causes MatchError
since is not covered by any case.

Let's create sequence - naive approach

//Fibonacci04.main(Array())
object Fibonacci04 extends App {

  /**
   * function using match/case with if
   */
  def fib(a : Int) : Int = {
    a match {
      case 0 => 0
      case 1 => 1
      case n if (n > 1) => fib(n - 1) + fib(n - 2)
    }
  }
  
  val numbers  = 0 to 35 //for each number
  val sequence : Seq = numbers.map(fib)  //apply function fib
  
  println(sequence)  //Vector(0, 1, 1, 2, 3, 5, 8, 13, 21)
}

Code result

()

Console output (click)

Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465)

Execution time: 1042 ms
Much faster - Streaming and scanLeft

//Fibonacci05.main(Array())
object Fibonacci05 extends App {

  def fib : Stream = 0 #:: fib.scanLeft(BigInt(1))(_ + _)
  
  val sequence : Seq = fib.take(36)
  println(sequence.last)
  
}

Code result

()

Console output (click)

Execution time: 561 ms