Author: corerootz - Ravi Kiran Krovvidi

scala – List – take, drop, splitAt

corerootz - Ravi Kiran Krovvidi Uncategorized

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

If n is greater than xs.length, the whole list xs is returned.

 

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

If n is greater than xs.length, the empty list is returned.

 

The splitAt operationsplitsthelistatagivenindex, returningapairof two lists.4 It is defined by the equality:
xs splitAt n equals (xs take n, xs drop n)

 

object List_TakeDropSplitAt extends App{

  val v1=List(1,2,3)
  println(v1.take(1))
  println(v1 take(10))

  println(v1.drop(1))

  println(v1.splitAt(1))

}

List(1)
List(1, 2, 3)
List(2, 3)
(List(1),List(2, 3))

scala – List – reverse

corerootz - Ravi Kiran Krovvidi Scala

like all other list operations, reverse creates a new list rather than changing the one it operates on. Lists are immutable

Reverse could be implemented using concatenation(:::),like in the following method, rev:
def rev[T](xs: List[T]): List[T] = xs match

{

case List() => xs

case x :: xs1 => rev(xs1) ::: List(x)

}

To study the complexity of rev, assume that the list xs has length n. Notice that there are n recursive calls to rev. Each call except the last involves a list concatenation. List concatenation xs ::: ys takes time proportional to the length of its first argument xs. Hence, the total complexity of rev is: n+(n−1)+…+1 = (1+n)∗n/2

rev’s complexity is quadratic in the length of its input argument. This is disappointing when compared to the standard reversal of a mutable, linked list, which has linear complexity

Scala – Concatenate – by pattern matching

corerootz - Ravi Kiran Krovvidi Scala

def append[T](xs: List[T], ys: List[T]): List[T] = xs match {

case List() => ys

case x :: xs1 => x :: append(xs1, ys)

}

So it will take the two lists to be concatenated as parameters. These two lists must agree on their element type, but that element type can be arbitrary.

This can be expressed by giving append a type parameter that represents the element type of the two input lists:
def append[T](xs: List[T], ys: List[T]): List[T]

Since lists are constructed from the back towards the front, ys can remain intact whereas xs will need to be taken apart and prepended to ys.

Thus, it makes sense to concentrate on xs as a source for a pattern match.

The most common pattern match over lists simply distinguishes an empty from a non-empty list

Scala – List – concatenation (:::)

corerootz - Ravi Kiran Krovvidi Scala

Concatenation (::: ) is implemented as method in class List

The result of xs ::: ys is a new list that contains all the elements of xs, followed by all the elements of ys.

Like cons, list concatenation associates to the right

xs ::: ys ::: zs
is interpreted like this:
xs ::: (ys ::: zs)

 

object List_Concatenation extends App{

  val l1 =List(1,2,3)
  val l2=List(3,4,5)
  val l3=l1:::l2

  println(l3)
  println(l3:::Nil)

  println(List():::l3)
  println(List(1,2,3):::List(4))
}

Scala – List patterns

corerootz - Ravi Kiran Krovvidi Uncategorized

List(…) is an instance of a library-defined extractor pattern.

The “cons” pattern x :: xs is a special case of an infix operation pattern. You know already that, when seen as an expression, an infix operation is equivalent to a method call.

 

When seen as a pattern, an infix operation such as p op q is equivalent to op(p, q). That is, the infix operator op is treated as a constructor pattern. In particular, a cons pattern such as x :: xs is treated as ::(x, xs).

There is a class named :: that corresponds to the pattern constructor. It is named scala.:: and is exactly the class that builds nonempty lists.

So :: exists twice in Scala, once as a name of a class in package scala, and again as a method in class List. The effect of the method :: is to produce an instance of the class scala.::.