Hatena::ブログ(Diary)

でこすけの日記

2011-12-19

consリストとsnocリスト

この記事はScala Advent Calendar jp 2011 - PARTAKEの19日目の記事です。

概要

Scalaのリストと関数型っぽい操作について説明します。

一通りリストについて説明をした後、通常のリストとちょっと違った「Snocリスト」を作ってみます。

Listについて

Scalaのリストは連結リストです。どういうことかというと、

通常の配列はこんな感じです。

f:id:Dekosuke:20111219003844p:image

配列は、

  • 連続したメモリ空間を占有している
  • ランダムアクセス(番地指定でのアクセス)が定数時間で可能
  • サイズを拡大する場合、最悪全体が作り直しになる

という特徴があります。これに対してScalaのリストは、

f:id:Dekosuke:20111219003845p:image

  • ひとつ前の要素へのポインタでつながっている
  • 空リストを示すオブジェクト(Nil)がある
  • ランダムアクセスできない
  • 一番前の要素の挿入、削除が定数時間で可能

といった特徴があります。

実際のところリストは単純な構造です。リストには、次の2つの要素しかありません。つまり、

です。空リストNilから始まり、要素を数珠繋ぎにつないでゆきます。たとえば、

空のリストは

Nil

1,2,3,4の4つの要素を持つリストは

1 :: 2 :: 3 :: 4 :: Nil

のようになります。これの略記法として、それぞれ

List()
List(1,2,3,4)

のように書くこともできます。配列をArray(1,2,3,4)とかと略記するとListと同じように見えますが、実態としてはかなり違います。

Listの使い方

連結リストであるScalaのリストは、ランダムアクセスをしません*1。では、ランダムアクセスなしでどうやって使うの?って思うかもしれません。

たとえば、C言語でのループ

for(i=0;i<LOOP_MAX;i++){
	//ここに繰り返し処理
}

みたいなものはどうやって書けばいいのでしょうか?

Listには2つの宝刀、mapとfoldがあります。

mapは各要素に関数適用して結果を新しいリストにします。

//全部の要素を2倍にする関数doubleをリストに適用します
val double = (x:Int)=>2*x
List(1,2,3,4).map(double) //List(2, 4, 6, 8) 

//全部の要素を2乗する関数squareをリストに適用します
val square = (x:Int)=>x*x
List(1,2,3,4).map(square) //List(1, 4, 9, 16) 

foldは汎用的な繰り返し処理を提供します。

//要素を2乗して和をとる関数squareSumをリストに適用します
val squareSum = (xs:List[Int]) => xs.foldLeft(0)((x,y)=>x+y*y)
squareSum(List(1,2,3,4)) // 30

//リストをfoldLeftで反転させます
List(1,2,3,4).foldLeft(List():List[Int])((x,y)=>y::x) //List(4,3,2,1)

//要素のうち制限範囲内(rmin,rmax)にあるものだけを残します
val filterRange = (rmin:Int,rmax:Int,xs:List[Int]) => xs.foldRight(List():List[Int]
)((x,y)=>if(x>rmin && x<rmax) x::y else y)
filterRange(2,5,List(1,2,3,4,5,6,7,8)) //List(3,4)

とても使いやすいですね!

foldだと読みにくくなってしまうものは、万能の刀であるパターンマッチと再帰関数によって書くことが出来ます。

//リストから要素を探し、あるかどうかを返す関数findを定義します
val find:(List[Int],Int)=>Boolean = (xs, elem) => xs match {
  case Nil => false
  case (x::xss) => if(x==elem) true else find(xss,elem)
}
find(List(1,2,3,4), 3) //true
find(List(1,2,3,4), 5) //false

Cons演算子

ところで、先ほど説明したとおり、ListのConsは、

x :: xs

のように書きます。つまり、

要素(x) 連結演算子(::) リスト(xs)

の順番になっていますよね?

逆に、

リスト(xs) 連結演算子 要素(x)

のように、左にあるリストに要素を連結してもいいのではないでしょうか?

つまり、通常のリスト↓

f:id:Dekosuke:20111219003847p:image

より、末尾に要素を追加する↓のリストのほうが直観的ではないでしょうか。

f:id:Dekosuke:20111219003848p:image

なぜ、Consは最初に要素が来るのでしょうか。おそらく、関数型言語の慣習だと思います。Lispの時代からCons演算子の先には要素が来るのでした。

つまり・・・

俺たちは、そのしわ寄せでConsを使うことを・・・強いられているんだ!

はい、流行りのネタなので使いたかっただけです。すみません・・・

とにかく、このような対称性を破るCons記法に甘んじることは許されません。

リスト 連結演算子 要素

のように通常と逆順で連結するリストも、

リストと要素の平等権の確保のために必要とされているのではないでしょうか。

逆順のリスト(Snocリスト)を作りましょう

ここで、分かりやすさのために、

リスト 連結演算子 要素

のように連結するリストに名前を付けましょう。通常のリスト(Consリスト)の逆順で連結するので、Snocリストとかどうでしょうか?

ものはためし、ScalaでSnocリストを作ってみましょう。

object SnocList{
    def empty = SnocNil
}

sealed trait SnocList[+A] {
    def isEmpty : Boolean
    def head : A
    def tail : SnocList[A]

    def ::>[B >: A] (x: B): SnocList[B] = new ::>[B](this, x)

    def map[B](f: A=>B) : SnocList[B] = this match {
        case SnocNil => SnocNil
        case xs ::> x => xs.map(f) ::> f(x)
    }

    def foldLeft[B](z: B)(f: (B, A) => B): B = this match {
        case SnocNil => z
        case xs ::> x => f(xs.foldLeft(z)(f), x)
    }

    def foldRight[B](z: B)(f: (A, B) => B): B = {
        var acc = z
        var these = this
        while (!these.isEmpty) {
            acc = f(these.head, acc)
            these = these.tail
        }
        acc
    }

    override def toString() = {
        val contents = getContents()
        "SnocList(" + contents + ")" 
    }

    def getContents():String = this match {
        case SnocNil => ""
        case SnocNil ::> x => x.toString()
        case xs ::> x => xs.getContents() + ", " + x.toString()
    }
}

case object SnocNil extends SnocList[Nothing] {
    override def isEmpty = true
    def head: Nothing = throw new NoSuchElementException("head of empty list")
    def tail: SnocList[Nothing] = throw new NoSuchElementException("tail of empty list")
}

case class ::>[B](tl:SnocList[B], hd: B) extends SnocList[B] {
    override def isEmpty = false
    def head : B = hd
    def tail : SnocList[B] = tl
}

できました!

このSnocListには

  • SnocNil (通常のリストのNilにあたるもの)
  • ::> (通常のリストのConsにあたるもの)

があります。たとえば、1,2,3,4のリストを書くときは以下のようになります。

SnocNil ::> 1 ::> 2 ::> 3 ::> 4 

左から右に流れる矢印のような記号がとても美しいですね*2

何でこんな風に書くとSnocListが作れるかって?・・それは、「scalaスケーラブルプログラミング」の第22章を読みましょう*3

Scalaスケーラブルプログラミング第2版

Scalaスケーラブルプログラミング第2版

Snocリストでmap, foldLeft, パターンマッチ

先ほどのSnocリストでは、map、foldLeft、パターンマッチを実装してあります。実際に使ってみましょう。

val l = SnocNil ::> 1 ::> 2 ::> 3 //SnocList(1, 2, 3)
//map
l.map(x=>2*x) //SnocList(2, 4, 6)

//foldLeftを使ったリストをそのまま返す関数
val snocId = (xs:SnocList[Int]) => xs.foldLeft(SnocList.empty:SnocList[Int])((x,y)=>(x ::> y))
snocId(l) //SnocList(1, 2, 3)

//foldRightを使ったリストのreverse
let snocReverse (xs:SnocList[Int]) = xs.foldRight(SnocList.empty:SnocList[Int])((x,y)=>(y ::> x))
snocReverse(l) //SnocList(3, 2, 1)

通常のリストはfoldLeftでconsすると逆順に、foldRightでconsすると正順になりましたが、SnocListではfoldRightで逆順になります。

というわけで、リストの連結が逆になった世界を作ることが出来ました。この世界では、リストの畳み方が逆になるのでした。

まとめ

この記事では、要素の連結方法が通常のリストと逆なSnocリストを作成しました。

このSnocリストは通常のリストと同様にNil、結合演算子(Snoc)、パターンマッチによる再帰処理、

mapやfoldLeftを使うことができました。

Scalaでは、リストのような言語の組み込みに見える要素ですら自分で定義できることが分かります。この柔軟さは本当に素晴らしいですね。

今回のSnocListのソースのgistはここになります

余談

今回Snocリストというものを持ち出した理由は、HaskellRepaというライブラリがSnocリストだったからだったりします。

参考文献と謝辞

Snocリストを作るに当たってid:jacobi824が手伝ってくれたので、ここに感謝します。

また、この記事を書くにあたって、以下のものを参考にしました。

*1:可能ですが、ポインタを辿っていくため遅いです

*2:まるでイカのようです

*3:「scala スケーラブルプログラミング」の第22章では標準のListの実現方法についてかかれていますが、上記のSnocリストでも同じ技術で実現されています。NilがNothingクラスになっていたり、case classによるパターンマッチの実現がされていたり色々な工夫が見てとれます。

xuweixuwei 2011/12/20 00:22 なぜ標準ライブラリのListのリンクが2.7.5とだいぶ古いんですかね?(・ω・`)

https://github.com/scala/scala/blob/v2.9.1/src/library/scala/collection/immutable/List.scala

DekosukeDekosuke 2011/12/20 00:37 新しいほうにリンク変更しました。2.7.5を見ていたのは、ぐぐって最初に見つけた物が2.7.5の実装で、2.9とそれほど変らないんじゃないかと思っていたからですね・・

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/Dekosuke/20111219/1324300466