[Scala]リストの操作

この記事はScalaスケーラブルプログラミングの16章、リストの操作の
抜粋というか復習用のメモです。

より詳しくわかりやすいものは本を参照してみてください。

リストの扱いや操作に関しては、関数型言語の特徴で他の
言語も共通・もしくは似ている機能が提供されています。

Scalaで型パラメータを受け取るトレイトを設計しているときに、
Listを参考にしたいな、と思って、List型を調べてみました。

リストの復習 -> 型パラメータ(別記事)という流れで書きたいと思います。

Scalaにおける配列とリストの違い

  1. リストはイミュータブルである
  2. 再帰的な構造(linked list)を持つ

※前回の記事でも書いたとおりScalaでの配列はArray型を用いる。
Array型はランダムアクセス。List型はシーケンシャルアクセス。

List型について

  • 配列と同様にリストの要素は全て同じ型になる(等質的=homegeneous)
  • S型がT型のサブ型であればList[S]型はList[T]型のサブクラスになる(共変=covariant)
  • 空のリストはList[Nothing]型
  • Nothing型はScalaクラス階層の最下部に存在し、全てのサブ型になる

リストの構築

リストはNilと::(コンス=cons)の2つから組み立てられ、Nilは空のリストを表す。
x :: xsは先頭の要素がxで、その後ろにリストxsが続いていることを表現している。

上記の例はこのように書き換えることが可能

::演算子は右結合でa :: b :: c は a:: (b :: c)と解釈されるので

このように括弧を省略することができる

リストに対する基本操作

リストの全ての操作は次の3つによって表現できる

  1. head リストの先頭を返す
  2. tail リストの先頭以外を除く要素を返す
  3. isEmpty リストが空ならtrueを返す

headやtailは空でないリストにのみ定義されている。
空のリストで実行すると例外が投げられる。

リストの処理の例として挿入ソート(insertion sort)のコードを挙げる

リストパターン

リストをパターンマッチで分解する。

左辺に右辺の長さがマッチすれば、そのまま値を束縛することができる。

リストの長さがわからない場合は

これを利用すれば先ほどの挿入ソートはhead,tail,isEmptyを使わずに実現することができる

Listクラスの一階メソッド

一階メソッドとは、引数に関数を取らないメソッドのこと。(高階関数ではないもの)
ここは全てサンプルコードを載せているととても長くなるので、メソッドの名前と概要だけ。
そして全部ではありません。

  • ::: リストの連結
  • length リストの長さ
  • reverse リストの反転
  • drop 先頭n個以外の要素を返す
  • take 先頭n個の要素を返す
  • splitAt n番目で要素を分割して返す
  • zip 二つのリストを受け取って、それを一つのリストにする
  • toString mkString リストの表示
  • toArray 配列へ変換する

Listクラスの高階メソッド

ここもざっくり

各要素のマッピング

  • map
    List[T]に対して T => U型の関数fを受け取りList[U]を返す
  • flatMap
    List[T]に対して T => List[U]型の関数fを受け取りfの戻り値であるList[U]を全て連結した値を返す
  • foreach
    List[T]に対して T => Unitの関数fを受け取り、単純にTに対して手続きを行う

フィルタリング

  • filter
    List[T]型のxsに対して T => Booleanの関数fを受け取り、f(x)がtrueになる全ての要素を返す
  • partition
    filterはtrueのものを返すのに対し、partitionはtrueとfalseになる要素をペアにしたものを返す
  • find
    List[T]型のxsに対して T => Booleanの関数fを受け取り、f(x)を満たす最初の要素を返す
  • takeWhile
    List[T]型のxsに対して T => Booleanの関数fを受け取り、先頭から順番にfalseが返るまでの要素を返す
  • dropWhile
    List[T]型のxsに対して T => Booleanの関数fを受け取り、先頭から順番にfalseが返るまでの要素を返す
  • span
    takeWhileとdropWhileの結果をそれぞれペアにして返す

述語関数

  • forall
    List[T]型のxsに対して T => Booleanの関数fを受け取り、xsの全ての要素xに対してf(x)がtrueを返すならtrueを返す
  • exists
    List[T]型のxsに対して T => Booleanの関数fを受け取り、xsの要素xのうちf(x)が1つでもtrueを返すならtrueを返す

畳込み

List[T]型のxsの各要素を結合する

  • /:(foldLeft) 左畳込み
    List[T]型のxsに対して、T型の初期値iと、(n:T, z:T) => Tの関数fを受け取り、初期値とリストの先頭(左から)から順番に計算した結果を返す
  • :(foldRight) 右畳み込み
    List[T]型のxsに対して、T型の初期値iと、(z:T, n:T) => Tの関数fを受け取り、初期値とリストの末尾(右から)から順番に計算した結果を返す

これの違いは前回のブログにも書いてあるのでそちらに。
加えてScala2.9で追加されたメソッドもあるので、参考リンクやリファレンスを参照いただければと思います。

参考リンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です