Коллекции
- списки
- множества
- массивы
- вектора
- Option
Списки. List
- однородны
- List[String] не может содержать элементы Int
- ковариантны
- если T подтип S, то и List[T] подтип List[S]
List. Создание 1
val list0 = List()
//list0: List[Nothing] = List()
val list1 = List(1, 2, 3)
//list1: List[Int] = List(1, 2, 3)
val list2 = List.range(1,5)
//list2: List[Int] = List(1, 2, 3, 4)
val list2a = List.range(1, 5, 2)
//list2a: List[Int] = List(1, 3)
val list3 = List.fill(5)("lol")
//list3: List[String] = List("lol", "lol", "lol", "lol", "lol")
val list4 = List.tabulate(5)(n => n/2.0)
//list4: List[Double] = List(0.0, 0.5, 1.0, 1.5, 2.0)
List. Создание 2
Nil - пустой список
val empty = Nil
//empty: Nil.type = List()
val list = 3 :: 2 :: 1 :: Nil
//list: List[Int] = List(3, 2, 1)
val d = Nil
//d: Nil.type = List()
val c = 3 :: d
//c: List[Int] = List(3)
val b = 2 :: c
//b: List[Int] = List(2, 3)
val a = 1 :: b
//a: List[Int] = List(1, 2, 3)
List. Шаблоны
val List(a, b, c) = List(1, 2, 3)
//a: Int = 1
//b: Int = 2
//c: Int = 3
val x :: y :: z = List(1, 2, 3)
//x: Int = 1
//y: Int = 2
//z: List[Int] = List(3)
List. Шаблоны
val List(a, b, c) = List(1, 2, 3, 4)
//scala.MatchError: List(1, 2, 3, 4) (of class
// scala.collection.immutable.$colon$colon)
// ammonite.$sess.cmd33$.<clinit>(cmd33.sc:1)
val x :: y :: z = List(1, 2, 3, 4, 5)
//x: Int = 1
//y: Int = 2
//z: List[Int] = List(3, 4, 5)
val x :: y :: z = List(1, 2)
//x: Int = 1
//y: Int = 2
//z: List[Int] = List()
Методы. head, tail, isEmpty
val head = List(1, 2, 3, 4, 5).head
//head: Int = 1
val tail = List(1, 2, 3, 4, 5).tail
//tail: List[Int] = List(2, 3, 4, 5)
val isEmpty = List(1, 2, 3, 4, 5).isEmpty
//isEmpty: Boolean = false
val isEmptyNil = Nil.isEmpty
//isEmptyNil: Boolean = true
List. много других методов
- Scala предоставляет множество методов для работы с коллекциями
- Начнем с методов первого порядка
::: Объединение списков
val `2list1` = List(1, 2) ::: List(3, 4, 5)
//`2list1`: List[Int] = List(1, 2, 3, 4, 5)
val `2list2`= List() ::: List(1, 2, 3)
//`2list2`: List[Int] = List(1, 2, 3)
val `2list3` = Nil ::: List(1, 2, 3)
//`2list3`: List[Int] = List(1, 2, 3)
length, indices
val len1 = List(1, 2, 3).length
//len1: Int = 3
val len2 = List().length
//len2: Int = 0
val len3 = Nil.length
//len3: Int = 0
val idx1 = List(1, 2, 3).indices
//idx1: Range = Range(0, 1, 2)
val idx2 = Nil.indices
//idx2: Range = Range()
init, last. Конец и начало
val abcde = List('a', 'b', 'c', 'd', 'e')
//abcde: List[Char] = List('a', 'b', 'c', 'd', 'e')
val last1 = abcde.last
//last1: Char = 'e'
val init1 = abcde.init
//init1: List[Char] = List('a', 'b', 'c', 'd')
List().init
//java.lang.UnsupportedOperationException: init of empty list
// scala.collection.immutable.Nil$.init(List.scala:596)
// ...
List().last
//java.util.NoSuchElementException: last of empty list
// scala.collection.immutable.Nil$.last(List.scala:595)
// ...
reverse
val edcba = List("e", "d", "c", "b", "a")
//edcba: List[String] = List("e", "d", "c", "b", "a")
val reverse1 = edcba.reverse
//reverse1: List[String] = List("a", "b", "c", "d", "e")
reverse для внимательных
lst.reverse.init <=> lst.tail.reverse
lst.reverse.tail <=> lst.init.reverse
lst.reverse.head <=> lst.last
lst.reverse.last <=> lst.head
drop, take и splitAt
val abcde = List('a', 'b', 'c', 'd', 'e')
val teke1 = abcde.take(2)
//teke1: List[Char] = List('a', 'b')
val drop1 = abcde.drop(2)
//drop1: List[Char] = List('c', 'd', 'e')
val splitat1 = abcde.splitAt(2)
//splitat1: (List[Char], List[Char]) = (List('a', 'b'), List('c', 'd', 'e'))
flatten
val flatten1 = List(List(1, 2), List(3), List(), List(4,5)).flatten
//flatten1: List[Int] = List(1, 2, 3, 4, 5)
val flatten2 = List(1, 2, 3).flatten
//cmd22.sc:1: No implicit view available from Int => scala.collection.IterableOnce[B].
//val flatten2 = List(1, 2, 3).flatten
// ^
//Compilation Failed
val flatten3 = List(List(List(), List(1)), List(List(2))).flatten
//flatten3: List[List[Int]] = List(List(), List(1), List(2))
zip и unzip
val abcde = List('a', 'b', 'c', 'd', 'e')
val zip1 = abcde.indices.zip(abcde)
//zip1: IndexedSeq[(Int, Char)] = Vector((0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e'))
val zip2 = abcde.zip(List(1, 2, 3))
//zip2: List[(Char, Int)] = List(('a', 1), ('b', 2), ('c', 3))
val zipIdx = abcde.zipWithIndex
/zipIdx: List[(Char, Int)] = List(('a', 0), ('b', 1), ('c', 2), ('d', 3), ('e', 4))
val unzip = zip2.unzip
//unzip: (List[Char], List[Int]) = (List('a', 'b', 'c'), List(1, 2, 3))
toString
val abcde = List('a', 'b', 'c', 'd', 'e')
val abcStr = abcde.toString
//abcStr: String = "List(a, b, c, d, e)"
val list = List(1, 2, 3, 4, 5)
val lstStr = list.toString
//lstStr: String = "List(1, 2, 3, 4, 5)"
mkSting
val str1 = abcde.mkString ("[", ",", "]")
//str1: String = "[a,b,c,d,e]"
val str2 = abcde.mkString ("", ",", "")
//str2: String = "a,b,c,d,e"
val str3 = abcde.mkString (",")
//str3: String = "a,b,c,d,e"
val str4 = abcde.mkString (",", "]")
//cmd37.sc:1: overloaded method value mkString with alternatives:
//val str4 = abcde.mkString (",", "]")
// ^
//Compilation Failed
List. методы высшего порядка
map, foreach
val abc = List(97 ,98, 99).map(_.toChar)
//abc: List[Char] = List('a', 'b', 'c')
abc.foreach(println)
//a
//b
//c
filter, partition
val filter1 = List(1, 2, 3, 4, 5).filter(_ % 2 == 0)
//filter1: List[Int] = List(2, 4)
val filter2 = List(1, 2, 3, 4, 5).filter(_ < 0)
/filter2: List[Int] = List()
val partition1 = List(1, 2, 3, 4, 5).partition(_ % 2 == 0)
//partition1: (List[Int], List[Int]) = (List(2, 4), List(1, 3, 5))
val partition2 = List(1, 2, 3, 4, 5).partition(_ < 0)
//partition2: (List[Int], List[Int]) = (List(), List(1, 2, 3, 4, 5))
find
val find1 = List(1, 2, 3, 4, 5).find(_ % 2 == 0)
//find1: Option[Int] = Some(2)
val find2 = List(1, 2, 3, 4, 5).find(_ <= 0)
//find2: Option[Int] = None
takeWhile, dropWhile
val takeWhile1 = List(1, 2, 3, -4, 5).takeWhile(_ > 0)
//takeWhile1: List[Int] = List(1, 2, 3)
val dropWhile1 = List("banana", "pear", "apple", "orange")
.dropWhile(_.startsWith("b"))
//dropWhile2: List[String] = List("pear", "apple", "orange")
span
val lst = List(1, 2, 3, -4, 5)
val span1 = lst.span(_ > 0)
//span1: (List[Int], List[Int]) = (List(1, 2, 3), List(-4, 5))
val span2 = (lst.takeWhile(_ > 0), lst.dropWhile(_ > 0) )
//span2: (List[Int], List[Int]) = (List(1, 2, 3), List(-4, 5))
forall, exist, contains
val forall1 = List(1, 2, 3).forall( _ > 0)
//forall1: Boolean = true
val forall2 = List(1, 2,-3).forall( _ > 0)
//forall2: Boolean = false
val exists1 = List(1, 2,-3).exists( _ < 0)
//exists1: Boolean = true
val exists2 = List(1, 2, 3).exists( _ < 0)
//exists2: Boolean = false
val contains1 = List(1, 2, 3).contains(3)
//contains1: Boolean = true
val contains2 = List(1, 2, 3).contains(0)
//contains2: Boolean = false
foldLeft foldRight
val num = List(1, 2, 3)
val foldLeft1 = num.foldLeft(0)(_ + _)
//foldLeft1: Int = 6
val foldLeft2 = num.foldLeft(-6)(_ + _)
//foldLeft2: Int = 0
val foldRight1 = num.foldRight(0)(_ + _)
//foldRight1: Int = 6
val foldRight2 = num.foldRight(-6)(_ + _)
//foldRight2: Int = 0
foldLeft fildRight. нагляднее
val lst = List("a", "b", "c", "d")
val foldLeft1 = lst.foldLeft("z")(_ + _)
//foldLeft1: String = "zabcd"
//op(op(op(z, a), b), c)
val foldRight1 = lst.foldRight("z")(_ + _)
//foldRight1: String = "abcdz"
//op(a, op(b, op(c, z)))
val foldLeft2 = lst.tail.foldLeft(lst.head)(_ + " " + _)
//foldLeft2: String = "a b c d"
val foldRight2 = lst.tail.foldRight(lst.head)(_ + " " + _)
//foldRight2: String = "b c d a"
reduceLeft reduceRight
val num = List(1, 2, 3)
val reduceLeft1 = lst.reduceLeft(_ + _)
//reduceLeft1: Int = 6
val reduceLeft2 = num.reduceLeft(_ min _)
//reduceLeft2: Int = 1
val reduceRight1 = num.reduceRight(_ + _)
//reduceRight1: Int = 6
val reduceRight2 = num.reduceRight(_ max _)
//reduceRight2: Int = 3
reduce vs fold
val emptyLst = List.empty[String]
val foldLeftEmpty = emptyLst.foldLeft("i")(_ + _)
//foldLeftEmpty: String = "i"
val reduceLeftEmpty = emptyLst.reduceLeft(_ + _)
//java.lang.UnsupportedOperationException: empty.reduceLeft
// at scala.collection.IterableOnceOps.reduceLeft(IterableOnce.scala:721)
// at scala.collection.IterableOnceOps.reduceLeft$(IterableOnce.scala:718)
// at scala.collection.AbstractIterable.reduceLeft(Iterable.scala:921)
// ... 28 elided
sortWith
val sort1 = List(10, 5, 8, 1, 7).sortWith(_ > _)
//res22: List[Int] = List(10, 8, 7, 5, 1)
val sort2 = List("banana", "pear", "apple", "orange")
.sortWith(_ < _)
//sort2: List[String] = List("apple", "banana",
// "orange", "pear")
val sort3 = List("banana", "pear", "apple", "orange")
.sortWith(_.length < _.length)
//sort3: List[String] = List("pear", "apple",
// "banana", "orange")
sorted
val a = List(10, 5, 8, 1, 7).sorted
//sort4: List[Int] = List(1, 5, 7, 8, 10)
не всё умеет sorted*
case class Cat (name: String, age: Int)
val s = List(Cat("Мурзик", 2), Cat("Murka", 1)).sorted
// error: No implicit Ordering defined for Cat.
не всё умеет sorted, решение
implicit class CatOrdered (cat: Cat) extends Ordered [Cat] {
val m1 = -1
def compare (that: Cat): Int = {
if (cat.name == that.name)
0
else if (cat.name > that.name)
1
else
m1 //ammonite ломается
}
}
sorted по максимому
val s = List(Cat("Мурзик", 2), Cat("Murka", 1)).sorted
//s: List[Cat] = List(Cat("Murka", 1), Cat("Мурзик", 2))
Array
val arr1 = new Array[Int](5)
//arr1: Array[Int] = Array(0, 0, 0, 0, 0)
val arr2 = Array(5, 4, 3, 2, 1)
//arr2: Array[Int] = Array(5, 4, 3, 2, 1)
val arr3 = Array(5)
//arr3: Array[Int] = Array(5)
Set, Map
- Set - множество уникальных значений
- Map - множество уникальных отображений
Set
val str = "Беги Лола, беги!"
//str: String = "Беги Лола, беги!"
val split = str.toLowerCase.split("[ !,]+")
//split: Array[String] = Array("беги", "лола", "беги")
var set = collection.mutable.Set.empty[String]
//set: collection.mutable.Set[String] = HashSet()
for (word <- split)
set += word
//set: collection.mutable.Set[String] = HashSet("беги", "лола")
Map
val map1 = Map("one" -> 1, "two" -> 2)
//map1: Map[String, Int] = Map("one" -> 1, "two" -> 2)
val map2 = Map("one" -> 1, "two" -> 3, "three" -> 3, "two" -> 2)
//map2: Map[String, Int] = Map("one" -> 1, "two" -> 2, "three" -> 3)
TreeSet, TreeMap
SortedSet
import scala.collection.immutable.TreeSet
val tSet1 = TreeSet(9, 4, 5, 3, 2, 5, 8)
//tSet1: TreeSet[Int] = TreeSet(2, 3, 4, 5, 8, 9)
val tSet2 = TreeSet('h', 'e', 'l', 'l', 'o')
//tSet2: TreeSet[Char] = TreeSet('e', 'h', 'l', 'o')
SortedMap
import scala.collection.immutable.TreeMap
var tMap = TreeMap(3 -> 'c', 1 -> 'b', 4 -> 'a')
//tMap: TreeMap[Int, Char] = TreeMap(1 -> 'b', 3 -> 'c', 4 -> 'a')
iterator
val it = Iterator("су", "е", "фа")
while (it.hasNext)
println(it.next())
//су
//е
//фа
mutable immutable
- scala.collection
- immutable
- mutable
- generic
- concurrent
scala.collection.immutable.List // Полное объявление
scala.List // объявление через псевдоним
List // тк scala._ всегда автоматически импортируется
// можно просто указать имя коллекции
Иерархия trait
Иерархия immutable
Иерархия mutable
Равенство
Set(1, 2, 3) != List(1, 2, 3)
Set(1, 3, 2) == Set(1, 2, 3)
Равенство
- mutable
- immutable
- НЕ-ВА-ЖНО
Равенство
List(1, 2, 3) == Vector(1, 2, 3)
HashSet(1, 2) == TreeSet(2, 1)
Отображение.
val v = Vector(1 to 10: _ * )
//v: scala.collection.immutable.Vector[Int] =
// Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val v2 = v.map(_ + 1).map(_ * 2)
//v2: scala.collection.immutable.Vector[Int] =
// Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
Отображение Ленивость
def lazyMap[T, U](coll: Iterable[T], f: T => U) =
new Iterable[U] {
def iterator = coll.iterator.map(f)
}
Отображение. Делаем ленивым
val vv = v.view
//vv: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
val vv2 = vv.map(_ + 1)
//vv2: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
val vv3 = vv2.map(_ * 2)
//vv3: scala.collection.IndexedSeqView[Int] = IndexedSeqView(<not computed>)
Отобржение. Вычисляем.
val vv5 = vv3.to(Vector)
//vv5: scala.collection.immutable.Vector[Int] =
// Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
val vv6 = vv3.to(List)
//vv6: List[Int] =
// List(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)
Performance. Seq. Immutable
| |
head |
tail |
apply |
update |
prepend |
append |
insert |
List |
C |
C |
L |
L |
C |
L |
- |
LazyList |
C |
C |
L |
L |
C |
L |
- |
ArraySeq |
C |
L |
C |
L |
L |
L |
- |
Vector |
eC |
eC |
eC |
eC |
eC |
eC |
- |
Queue |
aC |
aC |
L |
L |
C |
C |
- |
Range |
C |
C |
C |
- |
- |
- |
- |
String |
C |
L |
C |
L |
L |
L |
- |
Performance. Seq. Mutable
| |
head |
tail |
apply |
update |
prepend |
append |
insert |
ArrayBuffer |
C |
L |
C |
C |
L |
aC |
L |
ListBuffer |
C |
L |
L |
L |
C |
C |
L |
StringBuilder |
C |
L |
C |
C |
L |
aC |
L |
Queue |
C |
L |
L |
L |
C |
C |
L |
ArraySeq |
C |
L |
C |
C |
- |
- |
- |
Stack |
C |
L |
L |
L |
C |
L |
L |
Array |
C |
L |
C |
C |
- |
- |
- |
ArrayDeque |
C |
L |
C |
C |
aC |
aC |
L |
Performance. Set/Map. Immutable
| |
lookup |
add |
remove |
min |
HashSet/HashMap |
eC |
eC |
eC |
L |
TreeSet/TreeMap |
Log |
Log |
Log |
Log |
BitSet |
C |
L |
L |
eC* |
VectorMap |
eC |
eC |
aC |
L |
ListMap |
L |
L |
L |
L |
Performance. Set/Map. Mutable
| |
lookup |
add |
remove |
min |
HashSet/HashMap |
eC |
eC |
eC |
L |
WeakHashMap |
eC |
eC |
eC |
L |
BitSet |
C |
aC |
C |
eC* |
TreeSet |
Log |
Log |
Log |
Log |
Scala <=> Java
import scala.jdk.CollectionConverters._
// import collection.JavaConverters._ //2.12 и ниже
val j1 = java.util.Arrays.asList("hey", "lol")
//j1: java.util.List[String] = [hey, lol]
val j1s = j1.asScala
//j1s: collection.mutable.Buffer[String] = Buffer("hey", "lol")
val s1 = Seq("one", "dva")
val s1j = s1.asJava
//java.util.List[String] = SeqWrapper(List("one", "dva"))
Scala <=> Java
Iterator <=> java.util.Iterator
Iterator <=> java.util.Enumeration
Iterable <=> java.lang.Iterable
Iterable <=> java.util.Collection
mutable.Buffer <=> java.util.List
mutable.Set <=> java.util.Set
mutable.Map <=> java.util.Map
mutable.ConcurrentMap <=> java.util.concurrent.ConcurrentMap
Scala => Java
Seq => java.util.List
mutable.Seq => java.util.List
Set => java.util.Set
Map => java.util.Map
сортируем пузырьком
ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1
F=0
ЦИКЛ ДЛЯ I=1 ДО N-J-1 ШАГ 1
ЕСЛИ A[I] > A[I+1] ТО ОБМЕН A[I],A[I+1]:F=1
СЛЕДУЮЩЕЕ I
ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА
СЛЕДУЮЩЕЕ J
Scala в лоб
def bubblesort[A](arr: Array[A])(implicit ord: Ordering[A]): Array[A] = {
import ord._
for (j <- 1 to arr.length - 1) {
for (i <- 0 to (arr.length - 1 - j)) {
if (arr(i) > arr(i + 1)) {
var t = arr(i)
arr(i) = arr(i + 1)
arr(i + 1) = t
}
}
}
arr
}
Scala, когда не убъют
def bubblesort[A](list: List[A])(implicit ord: Ordering[A]): List[A] = {
import ord._
def sort(as: List[A], bs: List[A]): List[A] =
if (as.isEmpty) bs
else bubble(as, Nil, bs)
def bubble(as: List[A], zs: List[A], bs: List[A]): List[A] = as match {
case h1 :: h2 :: t =>
if (h1 > h2) bubble(h1 :: t, h2 :: zs, bs)
else bubble(h2 :: t, h1 :: zs, bs)
case h1 :: Nil => sort(zs, h1 :: bs)
}
sort(list, Nil)
}