首页 > 代码库 > Beginning Scala study note(6) Scala Collections
Beginning Scala study note(6) Scala Collections
Scala‘s object-oriented collections support mutable and immutable type hierarchies. Also support functional higher-order operations such as map, filter, and reduce that let you use expression-oriented programming in collections. Higher-order operations are not available with Java Collections library.
1. Scala Collection Hierarchy
Most collection classes exist in three packages: scala.collection, scala.collection.immutable, and scala.collection.mutable.
(1) package scala.collection
All types in scala.collections package are implemented in different ways in the Scala libraries based on whether the implementations are immutable or mutable. To keep these different implementations separate, there are packages called scala.collection.immutable and scala.collection.mutable.
1) Sequences
Sequences store a number of different values in a specific order. Sequences branch off into two main categories: indexed sequences and linear sequences.
# by default, Seq creates a List scala> val x = Seq(1,2,3) x: Seq[Int] = List(1, 2, 3) # by default, IndexedSeq creates a Vector scala> val x = IndexedSeq(1,2,3) x: IndexedSeq[Int] = Vector(1, 2, 3)
2) Sets
A Scala Set is a collection of unique elements. By default, Set creates an immutable Set.
# colletion.immutable.package is automatically added to the current namespace. The collection.mutable is not. scala> val x = Set(1,2,3) x: scala.collection.immutable.Set[Int] = Set(1, 2, 3)
3) Map
Scala Map is a collection of key/value pairs, where all the keys must be unique.
# creating an immutable Map without requiring an import scala> val map = Map(1 -> "a", 2 -> "b", 3 -> "c") map: scala.collection.immutable.Map[Int,String] = Map(1 -> a, 2 -> b, 3 -> c)
(2) package scala.collection.immutable
# immutable Seq
# immutable Set
# immutable Map
1) Immutable Sequence
If you want an immutable collection that has efficient indexing, your default choice would generally be Vector.
# an immutable IndexedSeq creates a Vector scala> val x = scala.collection.immutable.IndexedSeq(1,2,3) x: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3) # an immutable LinearSeq creates a List scala> val x = scala.collection.immutable.LinearSeq(1,2,3) x: scala.collection.immutable.LinearSeq[Int] = List(1, 2, 3) # an immutable Seq creates a List scala> val x = scala.collection.immutable.Seq(1,2,3) x: scala.collection.immutable.Seq[Int] = List(1, 2, 3)
A collection in package scala.collection.immutable will never change for everyone after it is created.
2) Immutable Set
# using an immutable Set scala> val m = collection.immutable.Set(1,2,3) m: scala.collection.immutable.Set[Int] = Set(1, 2, 3) # an immutable SortedSet creates a TreeSet scala> val m = collection.immutable.SortedSet(3,2,1) m: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 3) # using an immutable BitSet scala> val m = collection.immutable.BitSet(1,2,4) m: scala.collection.immutable.BitSet = BitSet(1, 2, 4)
3) Immutable Map
# using an immutable map without requiring an import scala> val m = Map(1->"a",2->"b") m: scala.collection.immutable.Map[Int,String] = Map(1 -> a, 2 -> b) # using an immutable Map with the prefix scala> val m = collection.immutable.Map(1->"a",2->"b") m: scala.collection.immutable.Map[Int,String] = Map(1 -> a, 2 -> b) # using an immutable.SortedMap scala> val m = collection.immutable.SortedMap(2->"a",1->"b") m: scala.collection.immutable.SortedMap[Int,String] = Map(1 -> b, 2 -> a)
(3) package scala.collection.mutable
By default, Scala always picks immutable collections. To get the mutable default versions, you need to write explicitly collection.mutable.Set or collection.mutable.Iterable.
Note that a useful convention if you want to use both mutable and immutable versions of collections is to import just the collection.mutable. Then a word like Set without a prefix still refers to an immutable collections, whereas mutable.Set refers to the mutable counterpart.
scala> import scala.collection.mutable
import scala.collection.mutable
1) mutable sequences
a) Buffer
There is no immutable Buffer. Two most significant subtypes of Buffer are ArrayBuffer and ListBuffer.
# creating a Buffer scala> val buffer = collection.mutable.Buffer(1,2,3) buffer: scala.collection.mutable.Buffer[Int] = ArrayBuffer(1, 2, 3) # a mutable Seq creates as ArrayBuffer scala> val x = scala.collection.mutable.Seq(1,2,3) x: scala.collection.mutable.Seq[Int] = ArrayBuffer(1, 2, 3) # a mutable LinearSeq creates as MutableList scala> val x = scala.collection.mutable.LinearSeq(1,2,3) x: scala.collection.mutable.LinearSeq[Int] = MutableList(1, 2, 3) # a mutable IndexedSeq creates an ArrayBuffer scala> val x = collection.mutable.IndexedSeq(1,2,3) x: scala.collection.mutable.IndexedSeq[Int] = ArrayBuffer(1, 2, 3) # a mutable Set scala> val m = collection.mutable.Set(1,2,3) m: scala.collection.mutable.Set[Int] = Set(1, 2, 3) # a mutable SortedSet create a TreeSet scala> val m = scala.collection.mutable.SortedSet(1,2,3) m: scala.collection.mutable.SortedSet[Int] = TreeSet(1, 2, 3) # a mutable BitSet scala> val m = scala.collection.mutable.BitSet(1,2,3) m: scala.collection.mutable.BitSet = BitSet(1, 2, 3) # a mutable Map scala> val m = collection.mutable.Map(1->"a",2->"b") m: scala.collection.mutable.Map[Int,String] = Map(2 -> b, 1 -> a)
2. Using Immutable Collection Classes
# List scala> val x = List(1,2,3,4) x: List[Int] = List(1, 2, 3, 4) # filtering through List scala> x.filter(a => a % 2 ==0) res0: List[Int] = List(2, 4) scala> x res1: List[Int] = List(1, 2, 3, 4) # Array scala> val a = Array(1,2,3) a: Array[Int] = Array(1, 2, 3) scala> a(1) res2: Int = 2 # Map scala> val m = Map("one"->1,"two"->2) m: scala.collection.immutable.Map[String,Int] = Map(one -> 1, two -> 2) scala> m("two") res3: Int = 2
Lazy collections have elements that may not consume memory until they are accessed(e.g., Range)
scala> 0 to 5 res7: scala.collection.immutable.Range.Inclusive = Range(0, 1, 2, 3, 4, 5)
The nifty(精巧的) thing about Ranges is that the actual elements in the Range are not instantiated until they are accessed.
# Using Range as Lazy Collection scala> (1 to Integer.MAX_VALUE - 1).take(5) res8: scala.collection.immutable.Range = Range(1, 2, 3, 4, 5)
Note that immutable collections may contain mutable items.
(1) Vector
# creating a Vector scala> val x = IndexedSeq(1,2,3) x: IndexedSeq[Int] = Vector(1, 2, 3) scala> x(0) res9: Int = 1
You can‘t modify a vector, so you add elements to an existing vector as you assign the result to a new variable.
scala> val a = Vector(1,2,3) a: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3) scala> val b = a ++ Vector(4,5) b: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5)
Use the updated method to replace one element in a vector while assigning the result to a new variable.
scala> val c = b.updated(0,"x") c: scala.collection.immutable.Vector[Any] = Vector(x, 2, 3, 4, 5) scala> val a = Vector(1,2,3,4,5) a: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5) scala> val b = a.take(2) b: scala.collection.immutable.Vector[Int] = Vector(1, 2) scala> val c = a.filter(_ > 2) c: scala.collection.immutable.Vector[Int] = Vector(3, 4, 5) # declare variable as a var and reassign the result back to the same variable scala> var a = Vector(1,2,3) a: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3) scala> a = a ++ Vector(4,5) a: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5)
When you create an immutable Vector as a var, it appears you can somehow add new elements to it:
scala> var int = Vector(1) int: scala.collection.immutable.Vector[Int] = Vector(1) scala> int = int :+ 2 :+ 3 int: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3) scala> int.foreach(println) 1 2 3
What‘s really happening is that the int variable points to a new collection each time you use the :+. The int variable is actually being reassinged to a new collection during each step.
(2) List[T]
scala> 1 :: 2 :: 3 :: Nil res11: List[Int] = List(1, 2, 3) # Anything that looks like an operator with a:(colon) as the first character is evaluated right to left. scala> new ::(1, new ::(2, new ::(3,Nil))) res12: scala.collection.immutable.::[Int] = List(1, 2, 3) # sometimes you need to help type inferencer along scala> List(1,44.5,8d) res13: List[Double] = List(1.0, 44.5, 8.0) scala> List[Number](1,44.5,8d) res14: List[Number] = List(1, 44.5, 8.0) # Note that the list referred to by the variable x is unchanged, but a new List is created with a new head and the old tail.You can also merge two lists to form a new list. The operation is O(n). scala> val x = List(1,2,3) x: List[Int] = List(1, 2, 3) scala> val y = List(99,98,97) y: List[Int] = List(99, 98, 97) scala> x ::: y res15: List[Int] = List(1, 2, 3, 99, 98, 97)
3. Getting Functional
scala> List(1,2,3).filter(x => x %2 == 1) res17: List[Int] = List(1, 3)
If filter returns true, the elements is included in the resulting collection. The resulting collection is the same type of collection that filter was invoked on.
scala> def isOdd(x: Int) = x % 2 == 1 isOdd: (x: Int)Boolean
Filter works with any collections that contain any type.
scala> "99 red balloons".toList.filter(Character.isDigit) res20: List[Char] = List(9, 9)
Another useful method for picking the right elements out of a List is takeWhile.
# 从左往右提取数据，直到条件不满足时停止 scala> "Elwood eat mice".takeWhile(c => c != ‘ ‘) res22: String = Elwood
4. Transformation
The map method on List (and Seq) transforms each element of a collection based on a function.
scala> List("A","Cat").map(s => s.toLowerCase) res23: List[String] = List(a, cat)
If the function passed into map returns a different type, then the resulting collection is a collection of the type returned from the function.
scala> List("A","Cat").map(_.length) res24: List[Int] = List(1, 3)
scala> trait Person {def first: String}
defined trait Person
We can extract data from a collection of complex objects.
scala> val d = new Person{def first = "David"}
d: Person = $anon$1@d6ae28
scala> val e = new Person{def first = "Elwood"}
e: Person = $anon$1@1281a0
scala> val a = new Person{def first = "Archer"}
a: Person = $anon$1@1845cfb
scala> List(a,d,e).map(_.first)
res25: List[String] = List(Archer, David, Elwood)
scala> List(a,d,e).map(a => <li>{a.first}</li>)
res26: List[scala.xml.Elem] = List(<li>Archer</li>, <li>David</li>, <li>Elwood</li>)
# find all the valid Person records, return the first names scala> trait Person{ | def first : String | def valid : Boolean | } defined trait Person scala> def validByAge(in: List[Person]) = in.filter(_.valid).map(_.first) validByAge: (in: List[Person])List[String]
5. Reduxio(简化)
reduceLeft method allows you to perform an operation on adjacent(临近的) of the collection where the result of the first operation is fed into the next operation.
# find the biggest number scala> List(8,6,22,2).reduceLeft(_ max _) res11: Int = 22 # find the longest word scala> List("moos","cow","A","cat").reduceLeft((a,b) => if(a.length > b.length) a else b) res13: java.lang.String = moos
reduceLeft throws an exception on an Nil List.
foldLeft starts with a seed value. The return type of the function and the return type of foldLeft must be same type as the seed.
# foldLeft feeds the seed and the first element of the List, 1, into the function, which returns 1. scala> List(1,2,3,4).foldLeft(0)(_ + _) res15: Int = 10 scala> List("b","a","elwood","archer").foldLeft(0)(_ + _.length) res19: Int = 14
Sometimes you may need to work with more than one collection at a time.
scala> val n =(1 to 3).toList n: List[Int] = List(1, 2, 3) scala> n.map(i => n.map(j => i * j)) res20: List[List[Int]] = List(List(1, 2, 3), List(2, 4, 6), List(3, 6, 9))
In order to nest the map operations but flatten the results of nested operations, we use flatMap method:
scala> n.flatMap(i => n.map(j => i * j)) res23: List[Int] = List(1, 2, 3, 2, 4, 6, 3, 6, 9)
However , syntactically, nested map, flatMap, and filter can get ugly.
scala> def isOdd(int: Int) = int % 2 == 1 isOdd: (int: Int)Boolean scala> def isEven(int: Int) = !isOdd(int) isEven: (int: Int)Boolean scala> val n = (1 to 10).toList n: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) scala> n.filter(isEven).flatMap(i => n.filter(isOdd).map(j => i * j)) res25: List[Int] = List(2, 6, 10, 14, 18, 4, 12, 20, ...,40, 56, 72, 10, 30, 50, 70, 90)
Using for comprehension, we can convert nested statements from the previous example into a syntactically pleasing statement.
scala> for{i <- n if isEven(i); j <- n if isOdd(j)} yield i * j res31: List[Int] = List(2, 6, 10, 14, 18, ..., 54, 8, 24, 40, 56, 72, 10, 30, 50, 70, 90)
6. Range
Ranges are often used to populate data structures, and to iterate over for loops.
scala> 1 to 10 res32: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) scala> 1 until 10 res33: scala.collection.immutable.Range = Range(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> 1 to 10 by 2 res34: scala.collection.immutable.Range = Range(1, 3, 5, 7, 9) scala> ‘a‘ to ‘c‘ res35: scala.collection.immutable.NumericRange.Inclusive[Char] = NumericRange(a, b, c) scala> val x = ( 1 to 10).toList x: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
7. Stream
A Stream is like a List, except that its elements are computed lazily. A Stream can be constructed with the #:: method, using Stream.Empty at the end of the expression instead of Nil.
# The number 1 and a ? to denote the end of the stream because the end of the stream hasn‘t # been evaluated yet. scala> val stream = 1 #:: 2 #:: 3 #:: Stream.empty stream: scala.collection.immutable.Stream[Int] = Stream(1, ?) # A Stream can be long ... infinitely long. scala> val stream = (1 to 1000000000).toStream stream: scala.collection.immutable.Stream[Int] = Stream(1, ?) # You can attempt access the head and tail of the stream. The head is returned immediately. But the tail isn‘t evaluated yet scala> stream.head res37: Int = 1 scala> stream.tail res38: scala.collection.immutable.Stream[Int] = Stream(2, ?)
8. Tuples
scala> def sumSq(in: List[Double]):(Int, Double, Double) = | in.foldLeft((0,0d,0d))((t,v) => (t._1 + 1, t._2 + v, t._3 + v * v)) sumSq: (in: List[Double])(Int, Double, Double)
The compiler will treat a collection of elements in parentheses as a Tuple. We seed the foldLeft with (0, 0d, 0d), which the compiler translates to a Tuples[Int, Double, Double]. The param t is a Tuple3, and v is a Double.
Using pattern matching to make the code a little more readable:
scala> def sumSq(in: List[Double]): (Int, Double, Double) = | in.foldLeft((0, 0d, 0d)){ | case ((cnt,sum,sq), v) => (cnt +1, sum + v, sq + v * v)} sumSq: (in: List[Double])(Int, Double, Double)
Create Tuples:
scala> Tuple(1,2) == Pair(1,2) res44: Boolean = true scala> Pair(1,2) == (1,2) res46: Boolean = true scala> (1,2) == (1 -> 2) res49: Boolean = true
9. Map[K,V]
The default Scala Map class is immutable. This means that you can pass an instance of Map to another thread, and that thread can access the Map without synchronizing.
scala> var p = Map(1 -> "David", 9 -> "Elwood") p: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> David, 9 -> Elwood)
We create a new Map by passing a set of Pair[Int, String] to the Map object‘s apply method. We create a var p other than a val p. This because the Map is immutable, so when we alter the contents on the Map, we have to assign the new Map back to p.
# add an element scala> p + (8 -> "Archer") res1: scala.collection.immutable.Map[Int,String] = Map(1 -> David, 2 -> Elwood, 8 -> Archer) # didn‘t change the immutable Map scala> p res2: scala.collection.immutable.Map[Int,String] = Map(1 -> David, 2 -> Elwood) # update p scala> p = p + (8 -> "archer") p: scala.collection.immutable.Map[Int,String] = Map(1 -> David, 2 -> Elwood, 8 -> archer) # get element out of the Map scala> p(2) res5: String = Elwood # Key not found scala> p(88) java.util.NoSuchElementException: key not found: 88
The get() Method on Map returns an Option(Some or Not) that contains the result:
scala> p.get(88) res7: Option[String] = None scala> p.get(2) res8: Option[String] = Some(Elwood)
You can return a default value if the key not found:
scala> p.getOrElse(99,"Nobody") res9: String = Nobody scala> p.getOrElse(1,"Nobody") res11: String = David scala> 1 to 5 flatMap(p.get) res13: scala.collection.immutable.IndexedSeq[String] = Vector(David, Elwood) # remove elements scala> p -= 1 scala> p res16: scala.collection.immutable.Map[Int,String] = Map(2 -> Elwood, 8 -> Archer) # check if Map contains a particular key scala> p.contains(2) res17: Boolean = true # find the largest key scala> p.keys.reduceLeft(_ max _) res18: Int = 8 # find the largest String scala> p.values.reduceLeft((a,b) => if (a>b) a else b) res19: String = Elwood # value contains the letter "z" scala> p.values.exists(_.contains("z")) res21: Boolean = false # add a bunch of elements using the ++ mthod scala> p ++= List(5 -> "Cat", 6 -> "Dog") scala> p res23: scala.collection.immutable.Map[Int,String] = Map(2 -> Elwood, 8 -> Archer, 5 -> Cat, 6 -> Dog) # remove a bunch of keys with the – metod scala> p --= List(8,6) scala> p res25: scala.collection.immutable.Map[Int,String] = Map(2 -> Elwood, 5 -> Cat) # a simpler way to remove unwanted elements from a Map def removeInvalid(in: Map[Int, Person]) = in.filter(kv => kv._2.valid)
10. Mutable Collections
The immutable collections can be transformed into new collections.
scala> val immutableMap = Map(1 -> "a", 2 -> "b", 3 -> "c") immutableMap: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b, 3 -> c) scala> val newMap = immutableMap - 1 + (4 -> "d") newMap: scala.collection.immutable.Map[Int,java.lang.String] = Map(2 -> b, 3 -> c, 4 -> d) # The original collection scala> immutableMap res0: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b, 3 -> c)
The List, Map and Set immutable collections can all be converted to the collection.mutable.Buffer type with the toBuffer method.
scala> val m = Map(1 -> "a", 2 -> "b") m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b) scala> val b = m.toBuffer b: scala.collection.mutable.Buffer[(Int, java.lang.String)] = ArrayBuffer((1,a), (2,b)) # The map, containing key-value pairs, is now a sequence of tuples. scala> b += (3 -> "c") res1: b.type = ArrayBuffer((1,a), (2,b), (3,c)) # changing the buffer to map again scala> val newMap = b.toMap newMap: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b, 3 -> c)
11. Mutable Queue
A queue is FIFO data structure. You can create an empty, mutable queue of any data type. Remind that make sure to include the full package name for the type.
# create a Queue scala> import scala.collection.mutable.Queue import scala.collection.mutable.Queue scala> var ints = Queue[Int]() ints: scala.collection.mutable.Queue[Int] = Queue()
Add elements to it using +=, ++= and enqueue
# add elements to the Queue scala> ints += 1 res2: scala.collection.mutable.Queue[Int] = Queue(1) scala> ints += (2,3) res3: scala.collection.mutable.Queue[Int] = Queue(1, 2, 3) scala> ints ++= Queue(4,5) res5: scala.collection.mutable.Queue[Int] = Queue(1, 2, 3, 4, 5) # use enqueue scala> ints.enqueue(6,7) scala> ints res15: scala.collection.mutable.Queue[Int] = Queue(1, 2, 3, 4,5,6,7)
You typically remove elements from the head of the queue, one element at a time, using dequeue.
scala> ints.dequeue res18: Int = 1 scala> ints res19: scala.collection.mutable.Queue[Int] = Queue(2, 3, 4, 5)
Queue extends from Iterable and Traversable, so it has all the usual collection methods, including foreach, map and so on.
12. Mutable Stack
A Stack is a LIFO data structure.
# create a Stack scala> import scala.collection.mutable.Stack import scala.collection.mutable.Stack scala> var ints = Stack[Int]() ints: scala.collection.mutable.Stack[Int] = Stack() scala> val ints = Stack(1,2,3) ints: scala.collection.mutable.Stack[Int] = Stack(1, 2, 3)
# push elements onto the stack with push scala> ints.push(4) res20: ints.type = Stack(4, 1, 2, 3) scala> ints.push(5,6,7) res21: ints.type = Stack(7, 6, 5, 4, 1, 2, 3) # To take elements off the stack, pop them off the top of the stack scala> val lastele = ints.pop lastele: Int = 7
Beginning Scala study note(6) Scala Collections