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(
             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.

Friday 8 July 2011

Java Surprises

This post is all about Java surprises that I have collected while reading Java Puzzlers : Traps, Pitfalls, and Corner Cases By Joshua Bloch, Neal Gafter . You can use this post as a quick reference. I have listed only 40 items but please read this book for more details. I believe that you will enjoy ( the way I enjoyed ) when you read this book.

1. A char is an unsigned 16-bit primitive integer, nothing more.

2. The + operator performs string concatenation if and only if at least one of its operands is of type String  otherwise, it performs addition.

3. char arrays are not strings. To convert a char array to a string, invoke String.valueOf(char[]).

4. The == operator, however, does not test whether two objects are equal; it tests whether two object references are identical. In other words, it tests whether they refer to precisely the same object.

5. Compile-time constants of type String are interned [JLS 15.28]. In other words, any two constant expressions of type String that designate the same character sequence are represented by identical object references.

  class Test {
   public static void main(String[] args) {
   
    String pig = "length: 10";
    String dog = "length: 10";
    
    System.out.println("Animals are equal: "+(pig == dog));
   }  
 }

Output
Animals are equal: true

6. Java provides no special treatment for Unicode escapes within string literals. The compiler translates Unicode escapes into the characters they represent before it parses the program into tokens, such as strings literals [JLS 3.2].

 public class Test {

  public static void main(String[] args) {

   // \u0022 is the Unicode escape for double quote (")

   System.out.println("a\u0022.length() + \u0022b".length());
     
   System.out.println("a".length() + "b".length());
  
  }
 }

Output
2
2

7. Unicode escapes must be well formed, even if they appear in comments.

8. Every time a byte sequence is translated to a String, a charset is used, whether it is specified explicitly or not. To make the program behave predictably, a charset should be specified.

9. charset: is the combination of a coded character set and a character-encoding scheme. In other words, a charset is a bunch of characters, the numerical codes that represent them, and a way to translate back and forth between a sequence of character codes and a sequence of bytes. The translation scheme differs greatly among charsets. Some have a one-to-one mapping between characters and bytes; most do not. The only default charset that will make the program print the integers from 0 to 255 in order is ISO-8859-1, more commonly known as Latin-1.

10. String.replaceAll takes a regular expression as its first parameter, not a literal sequence of characters. (Regular expressions were added to the Java platform in release 1.4.) The regular expression "." matches any single character of a string.

11. The URL that appears in the middle of the program is a statement label [JLS 14.7] followed by an end-of-line comment [JLS 3.7].

  public class Test {

    public static void main(String[] args) {

        System.out.print("I like ");

        http://www.google.com;

        System.out.println("firefox");

    }
  }

Output:

I like firefox

12. The specification for Random.nextInt(int) says: "Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive)" [Java-API]
   Random rnd = new Random();

This means that the only possible values of the expression rnd.nextInt(2) are 0 and 1.

13. StringBuffer(char) constructor does not exist. There is a parameterless constructor, one that takes a String indicating the initial contents of the string buffer and one that takes an int indicating its initial capacity.

14. The float and double types have a special NaN value to represent a quantity that is not a number.

15. NaN is not equal to any floating-point value, including itself.
    float i = Float.NAN;

     /* This is not terminate */
 
    while(i != i){ }

16. Any floating-point operation evaluates to NaN if one or more of its operands are NaN.

17. The + operator is overloaded: For the String type, it performs not addition but string concatenation. If one operand in the concatenation is of some type other than String, that operand is converted to a string prior to concatenation [JLS 15.18.1].

18.
    System.out.println(new Integer(0) == new Integer(0));
Output: False

Because of identity comparison on the object references. Two distinct objects.

19. It is illegal to apply the unary minus operator to a non-numeric operand.

20. In a try-finally statement, the finally block is always executed when control leaves the try block [JLS 14.20.2]. This is true whether the try block completes normally or abruptly. Abrupt completion of a statement or block occurs when it throws an exception, executes a break or continue to an enclosing statement, or executes a return from the method as in this program. These are called abrupt completions because they prevent the program from executing the next statement in sequence.

21. It is a compile-time error for a catch clause to catch a checked exception type E if the corresponding Try clause can't throw an exception of some subtype of E [JLS 11.2.3].

22. The set of checked exceptions that a method can throw is the intersection of the sets of checked exceptions that it is declared to throw in all applicable types, not the union.

23. Instance initializers run before constructor bodies. Any exceptions thrown by instance initializers propagate to constructors. If initializers throw checked exceptions, constructors must be declared to throw them too.

24. StackOverflowError is a subtype of Error rather than Exception.

25. Java's exception checking is not enforced by the virtual machine. It is a compile-time facility designed to make it easier to write correct programs, but it can be circumvented at run time.

26. VM loads and initializes the class containing its main method. In between loading and initialization, the VM must link the class [JLS 12.3]. The first phase of linking is verification. Verification ensures that a class is well formed and obeys the semantic requirements of the language. Verification is critical to maintaining the guarantees that distinguish a safe language like Java from an unsafe language like C or C++.

27. To write a program that can detect when a class is missing, use reflection to refer to the class rather than the usual language constructs.

  try {
    Object m = Class.forName("Missing").newInstance();
  } catch (ClassNotFoundException ex) {
    System.err.println("Got it!");
  }

28. Class.newInstance method instantiates a class reflectively. Class.newInstance invokes a class's parameterless constructor. Class.newInstance can throw checked exceptions that it does not declare.

29. Java's overload resolution process operates in two phases. The first phase selects all the methods or constructors that are accessible and applicable. The second phase selects the most specific of the methods or constructors selected in the first phase. One method or constructor is less specific than another if it can accept any parameters passed to the other [JLS 15.12.2.5].

The test for which method or constructor is most specific does not use the actual parameters: the parameters appearing in the invocation. They are used only to determine which overloadings are applicable. Once the compiler determines which overloadings are applicable and accessible, it selects the most specific overloading, using only the formal parameters: the parameters appearing in the declaration.

More generally, to force the compiler to select a specific overloading, cast actual parameters to the declared types of the formal parameters.

30. A single copy of each static field is shared among its declaring class and all subclasses.

31. When in doubt, favor composition over inheritance.

32. There is no dynamic dispatch on static methods [JLS 15.12.4.4]. When a program calls a static method, the method to be invoked is selected at compile time, based on the compile-time type of the qualifier, which is the name we give to the part of the method invocation expression to the left of the dot.

33. The instanceof operator is defined to return false when its left operand is null.

  String s = null;
  
  System.out.println(s instanceof String);

Output: false

34. Class initialization executes static initializers in the order they appear in the source.

35. A qualifying expression for a static method invocation is evaluated, but its value is ignored.

  public class Null {
    
    public static void greet() {
      System.out.println("Hello world!");
    }
    
    public static void main(String[] args) {
      ((Null) null).greet();
    }
 
  }

Output: Hello world!

36. Java language syntax does not allow a local variable declaration statement as the statement repeated by a for, while, or do loop [JLS 14.12-14]. A local variable declaration can appear only as a statement directly within a block. (A block is a pair of curly braces and the statements and declarations contained within it.)

  // Does not compile
        
  for (int i = 0; i < 100; i++)
    Creature creature = new Creature();
    
  Two ways to fix this problem:
  
  for (int i = 0; i < 100; i++) {
    Creature creature = new Creature();
  }
 
  OR
 
  for (int i = 0; i < 100; i++)
    new Creature();
37. BigInteger instances are immutable. So are instances of String, BigDecimal, and the wrapper types: Integer, Long, Short, Byte, Character, Boolean, Float, and Double. So their values can't be changed. Instead of modifying existing instances, operations on these types return new instances.
  BigInteger fiveThousand  = new BigInteger("5000");
 
  BigInteger total = BigInteger.ZERO;

  total.add(fiveThousand);
 
  System.out.println(total);
Output: 0
  BigInteger fiveThousand  = new BigInteger("5000");
  
  BigInteger total = BigInteger.ZERO;
 
  total = total.add(fiveThousand);
  
  System.out.println(total);
Output: 5000 38. hashCode() method must be overridden whenever equals() method is overrridden, otherwise hashCode() implementation from Object will be inherited. This implementation returns an identity-based hash code. In other words, distinct objects are likely to have unequal hash values, even if they are equal.

39. When a variable and a type have the same name and both are in scope, the variable name takes precedence [JLS 6.5.2]. The variable name is said to obscure the type name [JLS 6.3.2]. Similarly, variable and type names can obscure package names.

40. A package-private method cannot be directly overridden by a method in a different package [JLS 8.4.8.1].