Scala の List クラスで map, filter, foldRight と シーケンス内包表記

1. Scala の覚えやすそうな点と、すぐに忘れそうな仕様

Scala に興味を持った理由は、「今からでも遅くない これから始めるScala（前編）」 で挙げられていた以下の特徴による。

• オブジェクト指向と関数型言語の特徴を組み合わせています。Scalaでは、関数をオブジェクトとして扱うことができますし、高階関数も利用できるなど、関数型言語からさまざまな特徴を取り入れています。
• Scalaは静的型付け言語ですが、型推論によって型の記述を省略することができます。変数や関数の宣言時に、コンパイラが型を推論してくれるため、型の指定をいちいち行わなくてもよいのです。
• Trait（トレイト）という、実装を持つことができるインターフェイスを利用して、Mix-Inができます。
• 暗黙の型変換（implict conversion）などを利用して、DSL（ドメイン固有言語,Domain-Specific Language）を作成しやすくなっています。
• マルチコア時代を意識した、分散処理ライブラリ（Actorライブラリ）が用意されています。

(太文字は引用者による)

オブジェクト指向
プログラマが次に読む本
-Scalaで学ぶ関数脳入門

Programming in Scala

Scalaスケーラブルプログラミング
[コンセプト&コーディング]
(Programming in Scala)

久しぶりに本を購入して読んでいる。しかし、いつもの如く頭に入らないし、覚えたものは身に付かず抜けていく。

Scala は、統一されていて覚えやすい仕様もあれば、「何だかごちゃごちゃしていて忘れること間違いなし」と感じるところもある。結果として見やすくなるコードのために覚えておくルールの多さに圧倒されてしまったり。。 (+_+)

Guido van Rossum は Neopythonic: Scala? で次のように述べている。

Perhaps my biggest disappointment in Scala is that they have so many rules to make it possible to write code that looks straightforward, while being anything but -- these rules all seem to have innumerable exceptions, making it hard to know when writing simple code will work and when not.

 

a. Haskell の関数と似た名前のメソッド名

Scala は関数型の特徴を持ち合わせている。しかも型推論をしてくれる。しかし、「Haskell ではこう書けるのに、何で Scala はだめなんだろう？」と疑問を抱くことがある。例えば、

• メソッドの引数は必ず型を指定しないといけない。

Haskell で関数を定義するとき、引数の型を省略しても型を推論してくれる。

Prelude> let add x y = x + y

Scala では引数の型を指定しなくてはならないので面倒。 (+_+)

scala> def add(x:Int, y:Int) = x + y

この辺り、オブジェクト指向と折衷しているのが理由なのだろうか？スクリプトを書くのにお手軽に使えると期待していただけにちょっと残念。

ところで、Haskell との比較で言えば、関数名が似ているのはなぜだろう？例えば、Haskell でリスト操作に不可欠な、

• map
• filter
• foldr

(cf. Prelude, Data.List)

各々の言語でこれに対応した関数、メソッドを比較すると、

Python	map	filter	reduce	2.1 組み込み関数
Ruby	collect, map	find_all, select	inject	Enumerable
Scala	map	filter	foldRight, :\	scala.collection.immutable.List

これを見ると Haskell の関数名に Scala が一番似ていて、次に Python 。Ruby のメソッド名はかなり異なる。

scala.collection.immutable.List  には、上記以外にも類似したメソッドが見受けられる。もちろん、Python でも関数型プログラミングを意識したモジュールには似た名前の関数が定義されているけれど。

• cf. Python における関数型プログラミング のための functools, itertools (1)

Scala と Haskell の言語設計者は何か関係でもあるんだろうか？

Martin Odersky
via kwout

Scala の設計者である Martin Odersky が The Origins of Scala で次のように述べている。

Bill Venners: How did Scala come about? What is its history?

Martin Odersky: Towards the end of my stay in Zurich, around 1988/89, I became very fond of functional programming. So I stayed in research and eventually became a university professor in Karlsruhe, Germany. I initially worked on the more theoretical side of programming, on things like call-by-need lambda calculus. That work was done together with Phil Wadler, who at the time was at the University of Glasgow. One day, Phil told me that a wired-in assistant in his group had heard that there was a new language coming out, still in alpha stage, called Java. This assistant told Phil: "Look at this Java thing. It's portable. It has bytecode. It runs on the web. It has garbage collection. This thing is going to bury you. What are you going to do about it?" Phil said, well, maybe he's got a point there.

The answer was that Phil Wadler and I decided take some of the ideas from functional programming and move them into the Java space. That effort became a language called Pizza, which had three features from functional programming: generics, higher-order functions, and pattern matching. Pizza's initial distribution was in 1996, a year after Java came out. It was moderately successful in that it showed that one could implement functional language features on the JVM platform.

(太字斜体は引用者による)

Philip Wadler
via kwout

一緒に仕事したという Philip Wadler と言えば、The Haskell 98 Language Report の Preface に名前があるように、Haskell の言語仕様を決める委員会の editor であり、Glasgow Haskell Compiler 発祥の University of Glasgow で教授をしていた人物。「モナドって何？」と調べていれば行き当たるであろう Monads for functional programming の著者。

… ということは、関数名が Haskell に似ていたとしても、あながち偶然でもないということだろうか？

 

b. 他によく似た名前の関数を持つ言語は？

Scala が影響を受けた言語について調べてみると、

Scala (programming language) - Wikipedia, the free encyclopedia via kwout

Java, Pizza, Haskell … と順にある。

Fold (higher-order function) - Wikipedia には fold 系の関数の各言語の一覧が載せられている。この中で Scala の foldRight に似ている名前を持つ言語は Ocaml と Scheme 。それぞれ関数名は fold_right と fold-right 。

Objective Caml は、

• List より : map, filter, fold_right

Scheme は、

• Revised^6 Report on the Algorithmic Language Scheme より
  • 11.9  Pairs and lists ： map
• — Standard Libraries — より
  • 3  List utilities : filter, fold-right

うーん、こちらの方が名前は似てるなぁ。結局、どの言語が一番影響を与えて関数名が決まったんだろう？？？

 

それはさておき、リスト操作における重要な関数である、

• Python の map, filter, reduce とリスト内包表記

で練習した関数を Scala でも手を動かして覚えることに。 (+_+)

 

c. Meadow で Scala のスクリプトを実行

… とその前に、「オブジェクト指向プログラマが次に読む本 -Scalaで学ぶ関数脳入門」には Scala の実行方法として以下の 3 つが挙げられていた。

• シェルで対話的に実行する
• スクリプトを記述して実行する
• プログラムを記述して実行する

対話的というのは REPL のことで、ちょっと試したいときに使う。それ以外は main メソッドを持つシングルトンオブジェクトを書いてコンパイルして実行しないといけない思っていた。その中間に位置する実行方法があったのに気づかず。。 (+_+)  これからはスクリプトとして書いて実行してみよう。

( cf. Getting Started with Scala の Script it! )

以前、エディタで Scala を実行する方法をいくつか見た。

• Notepad++ の NppExecプラグインで Scala のコンパイルと実行
• Meadow で Scala - 空白を含むパスはトラブルの元
• Eclipse で Scala

やはり、Meadow を使っていこうかな。

方法は、

1. REPL を使うときのようにエディタに書いて
2. M-x scala-run-scala を実行
3. C-c C-l でスクリプトを実行。

( cf. EmacsでつくるScala開発環境 前編(scala-mode) - tototoshiの日記 )

 

2. map

まずは、リストの要素を 2 倍にすることから。

Haskell で書くなら、

Prelude> let l = [1..5]
Prelude> map (\x –> x * 2) l

セクションを利用すると、

map (*2) l

 

a. map メソッドにおける型変数

map メソッドの型を見ると、(scala.collection.immutable.List)

def map [B] (f: (A) ⇒ B) : List[B]

メソッドで型変数 B が宣言されている。

なぜこの型変数 B が書かれているのかと言えば、List クラスの型変数 A

class List [+A] …

はリストの要素の型を表しており、map メソッドの引数で要素を変換する関数、

f: (A) ⇒ B

により、元の要素の型とは異なる型になる可能性があるため。(型変数の前に `+’ が付いている意味は横に置いておく。)

この辺り、Java で似たような実装を試したときを参考に。

• Java の型変数 とイレイジャ - 具体的な型の指定を忘れずに
• Java で型変数を利用して Cons , Nil クラスによるリスト表現 – map, filter, foldr, foldl の実装

とりあえず、map メソッドを使う分には詳細を理解する必要はない。

 

b. 無名関数と引数の型を省略

Scala で無名関数を定義するときは、以下のような形式。

(引数:型) => 式

例えば、数値が与えられたら 2 倍する関数を定義するなら、

val f = (x:Int) => x * 2

Haskell で

–>

と書くところを

=>

とすることに注意。また、面倒だけれど、無名関数の引数は型を指定しなければならない。

リストの要素を 2 倍するには、

val l = List(1,2,3,4,5)
l.map((x:Int) => x * 2)

(以下、上記変数 l を使う。)

map 関数の引数として無名関数を与えると、引数の型をしなくてもよい。

l.map((x) => x * 2)

これは変数 l が

List[Int]

という型であり、リストの要素が Int 型だとわかることを利用して、先ほどの map メソッドに当てはめると、

def map [B] (f: (Int) ⇒ B) : List[B]

となり、map メソッドの第1引数の関数の引数の型を推論できるため。

ついでに、引数が 1 つだと ( ) も省略できる。

l.map(x => x * 2)

 

c. 無名関数の引数の省略

また、Haskell のセクションに似た書き方も用意されている。無名関数の引数は、

_

で代用できるので、

l.map(_*2)

 

d. メソッド呼び出し . の省略

それから、メソッドの呼び出しである . も省略できる。

l map (_*2)

シンプルに書けたけれど、ここまでの道程が長い。。(+_+)

 

e. 変更可能なリストを利用する場合

ところで、上記のリストは変更不能な (imutable) リストを利用した。 Scala ではこの使用が推奨されている。

これに対して、変更可能なリストを使いたい場合は、

• scala.collection.mutalble

を使う。

scala.collection.mutable.LinkedList の要素を追加するメソッド は

def :+ (elem: A) : LinkedList[A]

これを利用すると、

import scala.collection.mutable.LinkedList

var result = LinkedList[Int]()
for (e <- l){
  result = result.:+(e * 2)
}
println(result)

変更可能な変数は var を使って宣言。

result 変数を更新している箇所は、以下のように置き換えることができる。

result = result :+ e * 2

更に省略するなら、

result :+= e * 2

慣れないと、なぜこういう風に書けるのかわからなくなってしまうけれど。 ^^;

 

f. シーケンス内包表記

The Scala Language Specification には、

For Comprehension

と書かれており、A Tour of Scala では Sequence Comprehensions とある「シーケンス内包表記」。

List comprehension - Wikipedia に for と yield を使った説明がされていることより、

「リスト内包表記」

と同じような機能を持つようだ。これを使うなら、

for (e <- l) yield e * 2

Ruby の yield や、Python の yield と同じ予約語名なので頭の中が混乱してきた。。 (+_+)

 

3. filter

次に、filter メソッド。型を見ると、引数に述語 (predicate) を与えれば良いことがわかる。

(cf. scala.collection.immutable.List, Haskell の Prelude 散策 (2) - 述語)

def filter (p: (A) ⇒ Boolean) : List[A]

map メソッドと同じように徐々に省略できるところを省いていくと、

val l = List(1,2,3,4,5)
l.filter((x:Int) => x > 3)
l.filter((x) => x > 3)
l.filter(x => x > 3)
l.filter(_>3)
l filter (_>3)

シーケンス内包表記では、

for (e <- l; if e > 3) yield e

( ) を使わずに { } で書くと ; も省略できる。

for { e <- l
      if e > 3
} yield e

他の言語における for とちょっと違うので、混同しないように注意が必要。

 

4. foldRight

最後に、リストの値を集約する foldRight メソッド。(scala.collection.immutable.List)

def foldRight [B] (z: B)(f: (A, B) ⇒ B) : B

map, filter メソッドと違い引数が 2 つ。しかも、それぞれの引数が独立しているように見える括弧の書き方。

以下のようなシグニチャでないことに注意。

def foldRight [B] (z: B, f: (A, B) ⇒ B) : B

各々の引数を括弧で括る書き方は、Scala におけるカリー化の手段。引数のリストがあると言えばいいのかな？

カリー化とは、Chapter 8. Functional Programming in Scala によると、

… currying transforms a function that takes multiple parameters into a chain of functions, each taking a single parameter.

In Scala, curried functions are defined with multiple parameter lists,

def cat(s1: String)(s2: String) = s1 + s2

Of course, we could define more than two parameters on a curried function, if we like.

(太字は引用者による)

メソッドの引数が複数の括弧 ( )  で囲まれている様は、「複数の仮引数のリストを持っている」と言えば良いみたい。つまり、メソッドの引数の括弧が一つというのは、引数の書き方としては特殊な一例に過ぎないと。括弧ごとにメソッドの呼び出しを行うことができ、残りの引数を順に与えていき、最終的に全体の関数と同じ関数の連鎖が生まれる。

foldRight の場合で言えば、

リスト.foldRight(値)

により、foldRight の第 2 引数を受け取る関数が生成される。

では、foldRight を使って、要素を全て足す計算をしてみる。先ほどと同じく、徐々に省略した書き方をすると、

val l = List(1,2,3,4,5)
l.foldRight(0)((x:Int, y:Int) => x + y)
l.foldRight(0)((x,y) => x + y)
l.foldRight(0)(_+_)
(l foldRight 0)(_+_)

 

a. 別名 :\

foldRight と同じ機能のメソッドとして :\ がある。

def :\ [B] (z: B)(op: (A, B) ⇒ B) : B

なぜこんな形のメソッドがわざわざ定義してあるかと言えば、以下の foldr を説明した図を見れば一目瞭然。

Fold (higher-order function) - Wikipedia, the free encyclopedia via kwout

上記と同じ計算をするなら、

l.:\(0)(_+_)
(l :\ 0)(_+_)

これまた慣れないと読みずらい。

 

b. foldLeft と /:

foldRight はリストを右 (末尾) から左 (先頭) へと計算を進めるのに対して、foldLeft は左 (先頭) から右 (末尾) へと計算を行なう。

(l foldRight 100)(_-_)    // (1-(2-(3-(4-(5-100))))) => -97
(l foldLeft 100)(_-_)     // (((((100-1)-2)-3)-4)-5) => 85

foldLeft の別名は /: 。foldRight の :\ とは対照的。

(l :\ 100)(_-_)
(100 /: l)(_-_)

: で終わるメソッド名は右結合なので、第1引数を左に置く。この例外的なルールにより、左から計算を畳み込んでいく様をコードから連想できるようになっている。

. によるメソッドの呼び出しで書くなら、

l./:(100)(_-_)

こういう例外的なことが存在することが良いことなのか悪いことなのか。うーん…

 

c. reduceRight とreduceLeft

Haskell では foldr の第2引数がなく、リストの要素のみに二項演算子を適用していく関数名は foldr1 。

Prelude> foldr1 (+) [1..5]
15

scala には foldRight1 というメソッドはなく、reduceRight が代わりに存在する。

l reduceRight (_+_)

当然ながら、対照的な reduceLeft もあり。

l reduceLeft (_+_)

 

d. map , filter を foldRight で書き直し

次に、map メソッドで要素を 2 倍した関数を foldRight で書き直したい。

Haskell では以下のように書ける。

Prelude> foldr ((:).(*2)) [] [1..5]
[2,4,6,8,10]

Scala では空リストを Nil で表現する。

scala.collection.immutable.Nil

object Nil extends List[Nothing] with Product

これを利用して、以下のように書けばいいのかと思いきや、エラーとなる。 (+_+)

(l foldRight Nil)(_*2::_)

エラーがでないようにするには、foldRight の第1引数の型を明示する。

(l foldRight List[Int]())(_*2::_)

Programming in Scala

理由は、Programming in Scala (p326) によると、

Generally, when tasked to infer the type parameters of a polymorphic method, the type inferencer consults the types of all value arguments in the first parameter list but no arguments beyond that.

(太字は引用者による)

メソッドの型推論は、仮引数のリストのうち、最初の実引数を調べることによって行われるようだ。

foldRight の型で言えば、

def foldRight [B] (z: B)(f: (A, B) ⇒ B) : B

引数 z を元に型推論が行われる。

Nil の型について ：： メソッドを使って調べてみると、

scala> Nil
res0: scala.collection.immutable.Nil.type = List()

scala> 1::2::3::Nil
res1: List[Int] = List(1, 2, 3)

scala> "hoge"::"piyo"::"fuga"::Nil
res2: List[java.lang.String] = List(hoge, piyo, fuga)

：： メソッドに与える引数の型により、返り値の型が決まる。

ところで、foldRight の第1引数 z の型変数は B と書かれており、リストの要素から型を決めることができない。仮引数 z に Nil を与えても型が決まらない。だから、型を指定しなければならないということかな。

(l foldRight List[Int]())(_*2::_)

この場合の foldRight の型は以下のような感じ。

def foldRight(z: List[Int])(f: (Int, List[Int]) ⇒ List[Int]) : List[Int]

ごちゃごちゃしていて頭混乱するなぁ～。

 

map の定義

map 関数を foldRight メソッドを使って定義するなら、

def mymap[A,B](l: List[A], f:(A) => B) :List[B] = (l :\ List[B]())(f(_)::_)

Haskell では、型を明示しなくても推論してくれるのでシンプルに書ける。

mymap f = foldr ((:).f) []

 

filter の定義

filter メソッドを使った 3 以上要素を抽出する関数を ：\ メソッドで書き直すなら、

(l :\ List[Int]())((x,y) => if (x>3) x::y else y)

filter メソッドを :\ メソッドを使って定義するなら、

def myfilter[A](l: List[A], p: (A) => Boolean) :List[A] = 
  (l :\ List[A]())((x,y) => if (p(x)) x::y else y)

Haskell なら、

myfilter p = foldr (\x y -> if p x then x:y else y) []

 

5. その他

a. Range で数値のリストを生成

ついでなので、範囲を表わす scala.collection.immutable.Range を使い、1 から 10 まで足してみる。

((1 to 10) :\ 0)(_+_)
(1 to 10) reduceRight (_+_)
(1 to 10) sum

 

b. ブロックを使って副作用

純粋関数型でないメリットは、変数の更新や副作用を簡単に書けること。( それがバグの温床にもなるけれど… )

ブロック { } を foldRight で用いると計算途中の値を出力できたりする。ブロックは最後の式の値が返されるので、以下のように書くと、計算途中の変数の値を出力可能。

((1 to 5) :\ 0){ (x,y) =>
  println(y)
  x + y
}

結果は、

0
5
9
12
14
res647: Int = 15

これは Ruby の inject メソッドを書くときに似ている。

puts (1..5).inject(0){ |x,y|
  puts x
  x + y
}

実行すると結果は、

0
1
3
6
10
15

あ～、Ruby の inject メソッドは左から右へと畳み込んでいくんだったか。つまり、Scala で書くと、

(0 /: (1 to 5)){ (x,y) =>
  println(x)
  x + y
}