Sunday, 31 July 2011

Scala - Lists

In this session I am going to tell you about Scala's List. Lists support fast addition and removal of items to the begining of the list, but they do not provide fast access to arbitrary indexes because the implementation must iterate through the list linearly.

Scala's List, scala.List differs from Java's java.util.List type in that Scala Lists are always immutable whereas in Java Lists can be mutable.

Since Lists are immutable in Scala, they behave a bit like Java's strings: when a method is called on a list, it creates and returns a new list with the new value.The immutability of lists helps to develop correct, efficient algorithms bacause it is never needed to make copies of a list.

The below examples show how to create list in Scala:

scala> val capital = List("London", "Delhi");
fruit: List[java.lang.String] = List(London, Delhi)

scala> println(capital)
List(London, Delhi)

scala> val testMatrix =
             List(1, 0, 0),
             List(0, 1, 0),
             List(0, 0, 1)
testMatrix: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))

scala> println(testMatrix)
List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
scala> val empty = List()
empty: List[Nothing] = List()

Lists are homogeneous - the elements of a list all have the same type. The type of a list that has elements of type T is written as List[T].

The list type in Scala is covariant. This means that for each pair of types S and T, if S is a subtype of T, then List[S] is a subtype of List[T].

For Example:

List[String] is a subtype of List[Object].

List[Nothing] is a subtype of every other Scala type. Nothing is the bottom type in Scala's class hierarchy.

Constructing lists

All lists are built from two fundamental building blocks:

(1) Nil =>  represents the empty
(2) : : (pronounced "cons")  =>  the infix operator expresses list extension at the front.

For Example:

 x : : xs represents a list whose first element is x, followed by ( the elements of ) list xs.
The above example can be written like this.

scala> val myfruits = "apple" :: ("orange" :: Nil)
myfruits: List[java.lang.String] = List(apple, orange)
scala> println(myfruits)
List(apple, orange)

Parentheses can be dropped.

For Example: the below list is same as above:

scala> val myfruits = "apple" :: "orange" :: Nil
myfruits: List[java.lang.String] = List(apple, orange)

Basic Operations on lists

head  =>     returns the first element of a list

tail  =>    returns a list consisting of all elements except the first

isEmpty =>    returns true if the list is empty

scala> myfruits.head
res3: java.lang.String = apple

scala> myfruits.tail
res4: List[java.lang.String] = List(orange)

scala> myfruits.isEmpty
res5: Boolean = false

scala> myfruits.tail.head
res6: java.lang.String = orange

scala> empty.isEmpty
res7: Boolean = true

The head and tail methods are defined for non-empty lists. So when selected from an empty list, they throw an exception.

List Patterns

List(...) can be used to match all elements of a list.

scala> val fruits = List("orange", "apple", "pear")
fruits: List[java.lang.String] = List(orange, apple, pear)

scala> val List(a, b, c) = fruits
a: java.lang.String = orange
b: java.lang.String = apple
c: java.lang.String = pear

In the above example the pattern List(a, b, c) matches lists of length 3, and binds the three elements to the pattern variables a, b, and c.

If the number of list elements is not known beforehand, it is better to match with :: instead.

For Example: the pattern a :: b :: rest matches lists of length 2 or greater.

scala> val e :: f :: rest = fruits
e: java.lang.String = orange
f: java.lang.String = apple
rest: List[java.lang.String] = List(pear)

Concatenating two lists

List has a method named ':::' for list concatenation.

scala> val oneTwo = List(1,2)
oneTwo: List[Int] = List(1, 2)

scala> val threeFour = List(3,4)
threeFour: List[Int] = List(3, 4)

scala> val oneTwoThreeFour = oneTwo ::: threeFour
oneTwoThreeFour: List[Int] = List(1, 2, 3, 4)

Length of a List

scala> List(2, 3, 5).length
res3: Int = 3

It is slower. It traverses the full list to find out the empty list.

Accessing the end of a list: init and last

last returns the last element of a list.

init returns the rest of the list except the last one.

scala> val abcde = List('a', 'b', 'c', 'd', 'e')
abcde: List[Char] = List(a, b, c, d, e)

scala> abcde.last
res0: Char = e

scala> abcde.init
res1: List[Char] = List(a, b, c, d)

Like head and tail, these methods throw an exception when applied to an empty list.

Unlike head and tail, which both run in constant time, init and last need to traverse the whole list to compute their result. They therefore take time proportional to the length of the list.

Reversing a list

reverse method is used to reversing a list.

scala> abcde.reverse
res2: List[Char] = List(e, d, c, b, a)

reverse creates a new list rather than changing the one it operates on. reverse has its own inverse.

scala> abcde.reverse.reverse
res3: List[Char] = List(a, b, c, d, e)

Prefixes and suffixes: drop, take and splitAt

The expression xs take n returns the first n elements of the list xs.

scala> abcde take 2
res4: List[Char] = List(a, b)

The operation xs drop n returns all elements of the list xs except the first n ones.

scala> abcde drop 2
res5: List[Char] = List(c, d, e)

The operation xs splitAt n splits the list at a given index, returning a pair of two lists.

scala> abcde splitAt 2
res6: (List[Char], List[Char]) = (List(a, b),List(c, d, e))

Element selection: apply and indices

apply is used for random element selection.

scala> abcde apply 2
res7: Char = c

apply method is rarely used in Scala because xs apply n takes time proportional to the index n. In fact apply is simply defined by a combination of drop and head.

abcde apply 2 => (abcde drop n).head

indices range from 0 up to the length of the list minus one.

scala> abcde.indices
res8:scala.collection.immutable.Range = Range(0, 1, 2, 3, 4)

Thank you for reading this article. I hope you have enjoyed it.

No comments:

Post a Comment