列表

• 1. 不同于數(shù)組蜒犯，列表的元素是不能改變的絮供，列表是鏈表子巾。
• 2. 同一個(gè)列表的所有元素都必須是相同類型的帆赢。元素類型為T的列表類型為List[T]。注意T可能是Any這樣的父類线梗。Scala的List是協(xié)變的椰于，List[Child]是List[Father]的子類∫巧Γ空列表的類型為List[Nothing]瘾婿，因此是任何List[T]的子類型。可以使用空列表List()也就是Nil來(lái)構(gòu)建列表偏陪。
• 3. 所有的列表都構(gòu)建自兩個(gè)基礎(chǔ)單元抢呆，一個(gè)是Nil，一個(gè)是::笛谦。::是中綴表示符抱虐，在列表前添加元素。

列表的基本操作

head饥脑，tail恳邀，isEmpty。head和tail只對(duì)非空列表有定義灶轰，否則會(huì)拋出異常轩娶。

列表模式

• 1. 列表也可以使用模式匹配解開(kāi)。
     a::b::list可以匹配長(zhǎng)度大于等于2的列表框往。a::Nil表示只有一個(gè)元素的列表，推薦使用列表模式來(lái)對(duì)列表進(jìn)行解構(gòu)闯捎。
• 2. 匹配列表最常見(jiàn)的方式是區(qū)分空列表和非空列表椰弊。

List的初階方法

入?yún)⒅袥](méi)有函數(shù)的方法成為稱為方法。

• 1. 拼接兩個(gè)列表:::
  • :::入?yún)閮蓚€(gè)列表瓤鼻，返回結(jié)果為包含了這兩個(gè)列表所有元素的一個(gè)列表秉版，列表的返回類型是兩個(gè)列表元素類型繼承樹(shù)上的最近公共父節(jié)點(diǎn)。也是右結(jié)合的操作符茬祷。
  • 對(duì)列表的操作用的比較多的是分而治之的思想清焕。許多對(duì)列表的算法都首先使用模式匹配將輸入的列表切分為更小的樣例，這是分的思想祭犯，然后對(duì)每個(gè)樣例構(gòu)建對(duì)應(yīng)的結(jié)果秸妥，如果結(jié)果是一個(gè)非空的列表，那么這個(gè)列表的局部可以通過(guò)遞歸的調(diào)用同一個(gè)算法來(lái)實(shí)現(xiàn)沃粗，這是治的思想粥惧。
• 2. 獲取列表長(zhǎng)度：length
     這個(gè)不同于數(shù)組，需要更長(zhǎng)的時(shí)間最盅，所以如果使用xs.isEmpty的時(shí)刻突雪，最好不要使用xs.length == 0。isEmpty直接定義在了::類和Nil類中涡贱。
• 3. 訪問(wèn)列表的末端：init和last咏删，和head以及tail是對(duì)偶方法。
     當(dāng)應(yīng)用到空列表的時(shí)候會(huì)出錯(cuò)问词。head和tail在訪問(wèn)的時(shí)候消耗的常量時(shí)間督函，但init和last消耗的是線性時(shí)間，所以一般使用的都是head和tail
• 4. 反轉(zhuǎn)列表：reverse
     如果在算法中需要頻繁的訪問(wèn)列表的末尾元素，可以先將列表進(jìn)行反轉(zhuǎn)侨核，然后再將列表反轉(zhuǎn)回原樣草穆。
• 5. 前綴和后綴：drop，take搓译，splitAt
take返回前n個(gè)元素悲柱，如果n>list.length，那么就返回整個(gè)列表些己；
     drop表示丟棄前n個(gè)元素豌鸡，如果n>list.length，那么就返回空列表段标；
     splitAt操作將列表從指定的位置切開(kāi)涯冠，生成對(duì)偶(list take n, list drop n)，spiltAt會(huì)避免list的兩次遍歷逼庞，結(jié)果是(list take n, list drop n)蛇更，并不代表實(shí)現(xiàn)也是這么實(shí)現(xiàn)的。
• 6. 元素選擇：apply和indices
apply支持從對(duì)列表的隨機(jī)訪問(wèn)赛糟，相對(duì)于數(shù)組而言在列表中直接使用下標(biāo)并不是很常見(jiàn)派任。 a apply b可以簡(jiǎn)寫(xiě)為a(b)，編譯器會(huì)進(jìn)行展開(kāi)璧南。list(n)的耗時(shí)跟下標(biāo)n成正比掌逛。
     indices方法返回指令列表所有有效下標(biāo)的組合。
• 7. 扁平化列表：flatten
     接收一個(gè)列表的列表并將扁平化司倚，返回單個(gè)列表豆混。flatten函數(shù)只能扁平化一層的嵌套。只能應(yīng)用與所有元素都是列表的列表动知，否則會(huì)拋出異常皿伺。
• 8. 對(duì)列表使用zip和unzip
zip入?yún)閮蓚€(gè)列表，返回一個(gè)元素是對(duì)偶類型的列表拍柒。如果兩個(gè)列表長(zhǎng)度不同心傀，則丟棄沒(méi)有匹配上的元素，zipWithIndex拆讯，可以將元素和下標(biāo)zip起來(lái)脂男，是常見(jiàn)的應(yīng)用。元組的列表也可以只用unzip來(lái)轉(zhuǎn)換成為列表元組种呐。unzip和zip應(yīng)用的都是對(duì)偶宰翅，三個(gè)元素組成的元組是無(wú)法應(yīng)用的。
• 9. 顯示列表：toString和mkString爽室，addString
toString返回列表的標(biāo)準(zhǔn)字符串表現(xiàn)形式：List(a, b, c, d, e)汁讼。
     如需要不同的表現(xiàn)形式，則需要使用mkString，入?yún)⒂腥齻€(gè)嘿架，pre瓶珊，seperator，post耸彪。有重載的版本伞芹，xs.mkstring 表示元素之間的分隔符為空格，入?yún)⒂幸粋€(gè)的版本表示pre和post都是空字符串蝉娜。
     mkString還有一個(gè)變種唱较，就是addString，addString接受一個(gè)StingBuilder召川，將生成的字符串添加到StringBuilder上而不是直接返回南缓。addString和mkString這兩個(gè)方法繼承自List的超特質(zhì)Traversable，所以可以用在所有其他集合類型上荧呐。
• 10. 轉(zhuǎn)換列表：iterator, toArray, copyToArray
toArray可以轉(zhuǎn)換一個(gè)List到Array汉形；
      toList可以轉(zhuǎn)換一個(gè)Array到List；
      copyToArray有兩個(gè)入?yún)⒈恫渲幸粋€(gè)是目標(biāo)array获雕，目標(biāo)array必須足夠大，能夠容納整個(gè)列表收捣。可以通過(guò)iterator來(lái)使用迭代器訪問(wèn)列表中的元素庵楷。
      msort[T](less: (T, T) => Boolean)(xs: List[T])使用currying可以進(jìn)行函數(shù)的定制方便用戶使用罢艾，例如intSort = msort((x:Int, y:Int) => x < y) _是部分應(yīng)用函數(shù)，缺少一個(gè)參數(shù)尽纽，使用intSort(List(1, 3, 4))就可以進(jìn)行排序咐蚯。同樣的可以定制intReverseSort = msort((x:Int, y:Int) => x > y) _

List類的高階方法

許多對(duì)列表的操作都有相似的結(jié)構(gòu)，有一些模式反復(fù)出現(xiàn)弄贿。入?yún)⒅杏泻瘮?shù)的方法就是高階方法春锋。

• 1. 對(duì)列表做映射：map, flatMap, foreach
map操作接收T=>U函數(shù)，生成List[U]差凹。
     flatMap操作接收T=>List[U]期奔，將所有的結(jié)果拼起來(lái)生成List[U]。
     foreach的函數(shù)類型為T=>Unit危尿，并沒(méi)有列表類型的結(jié)果被組裝出來(lái)呐萌，賦值運(yùn)算的結(jié)果類型為Unit，值為()谊娇。
• 2. 過(guò)濾列表：filter, partition, find, takeWhile, dropWhile, span
filter接收一個(gè)判斷函數(shù)肺孤，T => Boolean，列表元素的類型為T
partition類似filter，接收一個(gè)判斷函數(shù)赠堵，T => Boolean小渊，生成的是一對(duì)列表元組，元組中的第一個(gè)列表包含了所有前提條件為true的元素茫叭，第二個(gè)列表包含了所有前提條件為false的元素酬屉。
     find方法和``filter類似，返回滿足給定條件的第一個(gè)元素杂靶，而不是所有元素梆惯，接收一個(gè)判斷函數(shù)，返回的是Option類型的值吗垮。
     takeWhile和dropWhile接收一個(gè)判斷函數(shù)為前提條件垛吗，takeWhile返回列表中滿足條件的最長(zhǎng)前綴，dropWhile去除列表中滿足條件的最長(zhǎng)前綴烁登。
     span方法生成列表元組：(list takeWhile p怯屉，list dropWhile p)，類似于splitAt饵沧，span不會(huì)重復(fù)遍歷列表锨络。
• 3. 對(duì)列表的前提條件檢查：forAll和exists
     返回的都是布爾值
• 4. 折疊列表：/:和:\
/:為是左折疊，和foldLeft是一樣的狼牺，(num /: xs)(_ + _)
     可以使用(word.head /: word.tail)(_ + " " + _)去除最前面word之前多余的空格羡儿。
     :\為右折疊，和foldRight是一樣的是钥，(xs :\ num)(_ + _)
     對(duì)于結(jié)合性的操作掠归，右折疊和左折疊是等效的，對(duì)于不同的操作可能存在執(zhí)行效率上的差異悄泥。
• 5. 列表排序：sortWith
     接收一個(gè)比較函數(shù)compare虏冻，對(duì)列表進(jìn)行排序，表達(dá)式x compare y在x出現(xiàn)在y之前應(yīng)返回true

List伴生對(duì)象的方法

之前的都是List類的方法弹囚，List伴生對(duì)象中的方法是可以在全局訪問(wèn)的厨相。

• 1. 從元素創(chuàng)建列表：List.apply
     當(dāng)伴生對(duì)象存在apply函數(shù)時(shí)，可使用()來(lái)代替apply鸥鹉。也就是說(shuō)List(1,2,3)和List.apply(1,2,3)是相同的效果蛮穿。
• 2. 創(chuàng)建數(shù)值區(qū)間：List.range
List.range(from, until, step:option)，until不是列表的一部分毁渗。
• 3. 創(chuàng)建相同元素的列表：List.fill
fill方法創(chuàng)建包含0個(gè)或者多個(gè)同一個(gè)元素拷貝的列表绪撵，第一個(gè)參數(shù)列表確定列表的維度以及每一維度的長(zhǎng)度；第二個(gè)參數(shù)列表是需要拷貝的元素
• 4. 表格化一個(gè)函數(shù)：List.tabulate
     相同與fill方法祝蝠，但是列表中的值是通過(guò)給定函數(shù)計(jì)算出來(lái)的音诈，計(jì)算與維度長(zhǎng)度有關(guān)
• 5. 拼接多個(gè)列表：List.concat
     將多個(gè)列表的元素拼接起來(lái)

同時(shí)處理多個(gè)列表

元組的zipped方法將若干通用的操作一般化了幻碱，不再只是針對(duì)單個(gè)列表而是能夠同時(shí)處理多個(gè)列表。zip會(huì)將所有有值的元素zip起來(lái)细溅，多余的元素會(huì)被丟棄褥傍。

Scala類型推斷算法

• Scala的類型推斷是基于程序流的，局部的喇聊，對(duì)于方法調(diào)用m(args)恍风，如果知道m的類型，可以將該類型運(yùn)用到之后的運(yùn)算中誓篱。Scala類型推斷算法會(huì)考慮第一個(gè)參數(shù)列表里的所有入?yún)㈩愋团蟊幔?code>currying的函數(shù)中，后面的參數(shù)列表并不會(huì)用于類型推斷窜骄。
• 所以如果入?yún)⒅杏蟹呛瘮?shù)入?yún)⒑秃瘮?shù)入?yún)⒔跄迹瑢⒑瘮?shù)入?yún)为?dú)放在最后一個(gè)列表中，這樣方法的正確實(shí)例類型可以從非函數(shù)入?yún)⑼茢喑鰜?lái)邻遏，而這個(gè)類型又能被繼續(xù)用于對(duì)函數(shù)入?yún)⒆鲱愋蜋z查糠亩。