scala 始めました
scala警察が怖いという話題で少し盛り上がっていたので、始めてみた。sbtとscalaはbrewから導入した。sbt consoleを使ってbuild.sbtの内容を読み込み、チマチマplay groundを遊ぶ。build.sbtにはscalaのバージョンと、-deprecation,-feature,-unchecked,-XlintをscalacOptionsに指定している。本項では、scalaを始めていく中で個人的に興味深く感じる部分などをつらつらと学習メモがてらにまとめている。決して入門を促す記事ではないし、個人的見解が多分に含まれる事、留意して頂きたい。
そんなわけで、取り敢えずクイックソートを書いてみた。
scala> import scala.util.Random import scala.util.Random scala> def qsort(lst:List[Int]): List[Int]= | lst match{ | case p::ys=> | qsort(for(y<-ys if y<p)yield y) ::: List(p) ::: qsort(for(y<-ys if y>=p)yield y) | case _ => Nil | } qsort: (lst: List[Int])List[Int] scala> qsort(List.fill(20)(Random.nextInt(20))) res1: List[Int] = List(0, 1, 2, 4, 4, 5, 5, 6, 7, 10, 10, 10, 12, 12, 13, 14, 14, 16, 18, 18)
for
のyield
だったり、Listを平面化しながらのappendが:::
で済むというのが、やはり良い。あと型に対するパターンマッチはやはり素晴らしい。C++でやろうとすればif constexprとtype traitsやSFINAE、テンプレートの特殊化を使うことになるだろうが、直感的に書けるパターンマッチという機能は便利だ。filter
を使えばこのコードは更に単純化できる。
import scala.util.Random object obj{ def qsort(lst:List[Int]):List[Int] = lst match{ case pivot::tail => qsort(tail filter{_ < pivot}) ::: List(pivot) ::: qsort(tail filter{_ >= pivot}) case _ => Nil } def main(Args:Array[String]):Unit = { val lst = List.fill(20)(Random.nextInt(20)) println(lst) println( qsort(lst) ) } }
C++で全く同じ事を書こうとすればこうなるだろうか。
#include<iostream> #include<numeric> #include<random> #include<boost/range/algorithm/copy.hpp> #include<vector> #include<array> #include<experimental/iterator> template<class T> T& qsort(T& v) { if(v.empty())return v; std::vector<typename T::value_type> left,right; std::partition_copy( std::next(std::begin(v),1),std::end(v), std::back_inserter(left),std::back_inserter(right), [pivot=*std::begin(v)](auto&& x){return x < pivot;} ); std::vector<typename T::value_type> l = qsort(left),r = qsort(right); typename T::value_type pivot = *std::begin(v); boost::copy(left,std::begin(v)); v[left.size()]=std::move(pivot); boost::copy(right,std::next(std::begin(v),left.size()+1)); return v; } template<class T> std::ostream& operator<<(std::ostream& os,T&& ar) { boost::copy(std::forward<T>(ar),std::experimental::make_ostream_joiner(os,",")); return os; } int main() { std::array<int,42> ar; std::iota(std::begin(ar),std::end(ar),0); std::shuffle(std::begin(ar),std::end(ar),std::mt19937()); qsort(ar); std::cout << ar << std::endl; }
やはり連結の機能が乏しく感じる...。入力をイテレータから受け付けるのであれば下記のように無駄なコピーとかは省けるが
template<class Iter> void qsort(Iter first,Iter last) { if(first==last)return; Iter l=first,r=std::next(last,-1); while(l<r){ for(; *r>*first; --r); for(; *l<=*first and l<r; ++l); std::iter_swap(l,r); } std::iter_swap(first,l); qsort(first,l); qsort(std::next(l,1),last); }
Scalaに比べて冗長的だ。
ただ、Scalaで一つ不便に思ったのは、コレクションの内部型(という言い方がscala的には正しいのか定かではないが)によって分岐するパターンマッチは書けないというところ。
scala> val lst:List[Int] = List.fill(5)(0) lst: List[Int] = List(0, 0, 0, 0, 0) scala> lst match{ | case _:List[String] => println("is String") | case _:List[Int] => println("is Int") | } <console>:14: warning: fruitless type test: a value of type List[Int] cannot also be a List[String] (the underlying of List[String]) (but still might match its erasure) case _:List[String] => println("is String") ^ <console>:15: warning: unreachable code case _:List[Int] => println("is Int") ^ is String
これはscalaコンパイラによるerasureという動作によってコレクションの内部型情報が削除されてしまうために上記の場合List[String]
とList[Int]
の判別ができない。もしこれを判別したければ、以下のようにしてワイルドカードを用いて内部でさらにパターンマッチを行うしかないのだろうか。何か良い方法がありそうだが。
scala> import java.util.Locale import java.util.Locale scala> val lst:List[AnyRef]=List.fill(5)("hoge") lst: List[AnyRef] = List(hoge, hoge, hoge, hoge, hoge) scala> lst match{ | case x:List[_] => | x.head match { | case _:java.lang.Integer => println("is integer") | case _:String => println("is String") | case _ => println("other") | } | case _ => println("other") | } is String
scala> class Point(val x:Int,val y:Int){ | def +(other:Point): Point = new Point(other.x+x,other.y+y) | override def toString():String = "(" + x + "," + y + ")" | } defined class Point scala> val p = new Point(42,42) p: Point = (42,42) scala> println(p + p) (84,84)
toString
はprintln
で出力するためにオーバーライドして定義する。それと、メソッドのシグネチャに複数の引数リストを作る構文がある事に驚きだ。これはつまりカリー化という概念を文法としてサポートする事を意味する。
scala> def plus(x: Int)(y: Int):Int = x+y plus: (x: Int)(y: Int)Int scala> val plus10 = plus(10)_ plus10: Int => Int = $$Lambda$1202/791874361@70061cf6 scala> plus10(20) res3: Int = 30
C++では、主にラムダをネストしていく事でカリー化を実現するが、これもscalaでは簡潔に書ける。さて、クラスの継承は以下のように書く。
scala> class X(){ | def print():Unit = println("X") | } defined class X scala> class Y() extends X{ | override def print():Unit = println("Y") | } defined class Y scala> new X().print() X scala> new Y().print() Y
scalaでは親クラスと同名のメソッドをoverrideキーワードなしで定義しようとするとエラーとなる。オーバーライドしたつもりになる可能性を考えれば、まぁ確かに禁止にするのも良い方針か。
scala> class Y() extends X{ def print():Unit = println("Y")} <console>:12: error: overriding method print in class X of type ()Unit; method print needs `override' modifier class Y() extends X{ def print():Unit = println("Y")} ^
また、scalaのobjectにおいて、apply
という名前のメソッドが、scala処理系では特別に扱われる。
scala> class X() defined class X scala> object X{ | def apply():X = new X() | } defined object X warning: previously defined class X is not a companion to object X. Companions must be defined together; you may wish to use :paste mode for this. scala> X() res0: X = X@2ad7126
この場合、X()
という記述によってX.apply()が呼ばれる事となる。また、クラス名と同じ名前のシングルトンオブジェクトはコンパニオンオブジェクトと呼ばれ、対応するクラスのprivate[this]
以外のprivateフィールドに対して特権的な権限を持っており、その性質を無視してアクセスを可能とする。
クラスとコンパニオンオブジェクトの関係性を正しくコンパイラに示すためには、両者の記述を同一ファイル中に示す必要がある。REPLでは上記のように、一つ一つの入力でコンパニオンオブジェクトを定義した場合、その関係性を正しく認識できないとの事で、警告文が出力されている。よってREPLでは、:paste
コマンドによってペーストモードへ移行し、そのモード中にクラスとそれに対するコンパニオンオブジェクトを一度に入力する必要がある。
scala> :paste // Entering paste mode (ctrl-D to finish) class X(private val x:Int) object X{ def print():Unit = { val a:X = new X(42) println(a.x) } } // Exiting paste mode, now interpreting. defined class X defined object X scala> X.print() 42
scalaでは、トレイトの実体化は行えないが、new trait{}
というようにするとそのトレイトを継承した空のクラスが暗黙生成され実体化されるとのことで、トレイトそのものの実体化ではないことに留意。
scala> trait traitT{def f():Unit = println("f")} defined trait traitT scala> new traitT{}.f() f
また、scalaでは、菱形の継承関係にある実態に対する曖昧さ解決に主に二つの方法が取られる。1つは、他の言語でも馴染みのある、型を明示的に指定する方法。
scala> trait A{def f():Unit} defined trait A scala> trait B extends A{def f():Unit = println("B::f")} defined trait B scala> trait C extends A{def f():Unit = println("C::f")} defined trait C scala> class X extends B with C{ | override def f():Unit = println("X::f") | } defined class X scala> class Y extends B with C{ | override def f():Unit = super[B].f() | } defined class Y scala> class Z extends B with C{ | override def f():Unit = super[C].f() | } defined class Z scala> (new X).f() X::f scala> (new Y).f() B::f scala> (new Z).f() C::f scala> class ZZ extends B with C{ | def f():Unit = println("non override") | } <console>:14: error: overriding method f in trait C of type ()Unit; method f needs `override' modifier def f():Unit = println("non override") ^
菱形の継承関係にあるクラスで該当するメソッドのオーバーライドを行わない事は許されず上記の通りエラーとなる。
もう一つはlinearizationという方法。この方法は、菱形関係になりうるトレイトの定義内の関数において、overrideキーワードを付与する事でその効果が発揮される事を示す。linearizationを行うと、トレイトのミックスインの順序に依存して、つまり最後にミックスインされたトレイトの同メソッドを呼び出すようになる。
scala> trait A{def f():Unit} defined trait A scala> trait B extends A{override def f():Unit = println("B::f")} defined trait B scala> trait C extends A{override def f():Unit = println("C::f")} defined trait C scala> class X extends B with C defined class X scala> (new X).f() C::f scala> class X extends C with B defined class X scala> (new X).f() B::f
このような線形化によるトレイトの積み重ねの処理をStackable Traitと呼ぶ。また、scalaにはself type annotationsまたはself typeと呼ばれる機能がある。self type annotationは、自身の型にアノテーションを追加記述できるように設定する事で、機能を後に注入する事ができる機能である。
scala> trait T{ def f():Unit } defined trait T scala> trait X{ | self: T => | def invoke():Unit = f() | override final def toString = "X" | } defined trait X
上記のコードだと、メソッドfに対して機能を後に定義する事ができる。
scala> trait printHello extends T{ | def f():Unit = println("Hello") | } defined trait printHello scala> val t = new X with printHello t: X with printHello = X scala> t.f() Hello
このように、後から利用するモジュールの実装を与えることを依存性の注入(Dependency Injection)と呼ぶ。
トレイトには、初期化を遅延する方法がある。例えば、以下のような場合
scala> trait A{ val s:String } defined trait A scala> trait B extends A { val bar:String = s + "World" } defined trait B scala> class C extends B{ | val s:String = "Hello" | def print():Unit = println(bar) | } defined class C scala> (new C).print() nullWorld
scalaのトレイトは、上から順番に初期化されていくため、trait A
内のs
が末初期化の状態でtrait B
のbar
の初期化に使われる。同時点で、末初期化のs
、つまりnullと"World"というStringオブジェクトが連結されて初期化されるため上記のような結果となる。このような事を未然に防ぐためには、初期化順序をよく把握している事が最も重要であるが、初期化の遅延を行うlazyキーワードを用いる事でも可能である。
scala> trait A{ val s:String } defined trait A scala> trait B extends A { lazy val bar:String = s + "World" } defined trait B scala> class C extends B{ | val s:String = "Hello" | def print():Unit = println(bar) | } defined class C scala> (new C).print() HelloWorld
lazyキーワードが付与されたオブジェクトは実際に使われる部分で初期化が行われる。しかしその分若干オーバーヘッドが発生してしまい、マルチスレッド下では最悪デッドロックが発生してしまう可能性がある。トレイトの初期化順序を遅延させるもう1つの方法として、事前定義(Early Definitions)を使う方法もある。
scala> trait A{ val s:String } defined trait A scala> trait B extends A{ val bar = s + "World" } defined trait B scala> class C extends { val s = "Hello" } with B { def f():Unit = println(bar) } defined class C scala> (new C).f() HelloWorld
Early Definitionsはクラス定義の時点での回避方法、つまり利用者側の回避方法となるため、利用者側で止むを得ない場合に当機能を利用するかもしれないが、問題の起因はトレイトB側にあるためトレイトBの定義を改変できない特別な理由がない限りは当機能を使うことはないだろう。
クラス、メソッドには型パラメータという機能を用いることができるとのこと。C++のテンプレートといったところか。
scala> class X[T](var l:T,val r:T){ | final override def toString():String = "(" + l + "," + r + ")" | } defined class X scala> new X(42,42) res0: X[Int] = (42,42)
しかし、Variadic templates的な機能はないようで、例えばタプルはTuple1からTuple22までがコピペコードによって標準搭載されているとのこと。Variadic templatesは欲しかったなぁ。
scala> new Tuple3(42,"hoge",42.4) res2: (Int, String, Double) = (42,hoge,42.4) scala> (42,"hoge",42.4) res3: (Int, String, Double) = (42,hoge,42.4) scala> (42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42) <console>:1: error: too many elements for tuple: 23, allowed: 22 (42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42)
上記の通り、オブジェクトを()
で囲むと、タプルが暗黙生成されるようだ。23以上になると、当然タプルの生成ができないのでエラーとなる。
また、Scalaでは、何も指定しなかった型パラメータは通常はinvariantとなる。
scala> class X[T](x:T){ override def toString():String = x.toString } defined class X scala> var a = new X(42) a: X[Int] = 42 scala> val b = new X(53) b: X[Int] = 53 scala> a = b a: X[Int] = 53 scala> class A{ override def toString():String = "This is A" } defined class A scala> class B extends A{ final override def toString():String = "This is B" } defined class B scala> var a = new X(new A()) a: X[A] = This is A scala> val b = new X(new B()) b: X[B] = This is B scala> a = b <console>:13: error: type mismatch; found : X[B] required: X[A] Note: B <: A, but class X is invariant in type T. You may wish to define T as +T instead. (SLS 4.5) a = b ^
covariantの動作を行うためには、型パラメータに+
を付与する。
scala> class X[+T](x:T){ override def toString():String = x.toString } defined class X scala> class A{ override def toString():String = "This is A" } defined class A scala> class B extends A{ final override def toString():String = "This is B" } defined class B scala> var a = new X(new A()) a: X[A] = This is A scala> val b = new X(new B()) b: X[B] = This is B scala> a = b a: X[A] = This is B
covariantでは継承元に継承先を代入することができる機能であるがそれに対してcontravariantという機能もある。これは、継承先に継承元の代入を許す。記述としては、型パラメータに対して-
を付与する。
scala> class X[-T](x:T){ override def toString():String = x.toString } defined class X scala> class A{ override def toString():String = "This is A" } defined class A scala> class B extends A{ final override def toString():String = "This is B" } defined class B scala> val a = new X(new A()) a: X[A] = This is A scala> var b = new X(new B()) b: X[B] = This is B scala> b = a b: X[B] = This is A
また、型制約を設けることもできる。これはとても良い。渡されたオブジェクトが、E >: T
の継承関係にある場合に呼び出すようにしてみると以下のようになる。
scala> class X[T]{ def f[E >: T](t:T): Unit = println("ok") } defined class X scala> class Y defined class Y scala> (new X[Int]).f(new Y) <console>:14: error: type mismatch; found : Y required: Int (new X[Int]).f(new Y) ^ scala> class Z extends Y{ final override def toString():String = "This is Z" } defined class Z scala> (new X[Y]).f(new Z) ok
また、scalaでは、関数と言ったら、それは大抵標準搭載されたFunction0
〜Function22
のトレイトの無名サブクラスのインスタンスの事を示すのだとのこと。
scala> val plus = new Function2[Int,Int,Int]{ | def apply(x:Int,y:Int):Int = x + y | } plus: (Int, Int) => Int = <function2> scala> plus(10,20) res0: Int = 30
Functionnの三つの引数は左からそれぞれのパラメータ型、最後が返却型となっている。これは以下のようなsyntax sugerが搭載されている。
scala> val plus = (x:Int,y:Int) => x + y plus: (Int, Int) => Int = $$Lambda$1328/628570906@4c524cb9 scala> plus(10,20) res1: Int = 30 scala> val plus = (_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int) <console>:1: error: too many elements for tuple: 23, allowed: 22 val plus = (_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int)
これも、23以上のFunctionは標準搭載されていないので、暗黙生成させることはできない。 また、関数の型は、以下のように省略する事ができる。
scala> val plus:Function2[Int,Int,Int] = (x:Int,y:Int) => x + y plus: (Int, Int) => Int = $$Lambda$1349/1622814373@55417169 scala> val plus:(Int,Int)=>Int = (x:Int,y:Int) => x + y plus: (Int, Int) => Int = $$Lambda$1350/566120649@771e97aa scala> val plus:Function1[Int,Function1[Int,Int]] = (x:Int) => ((y:Int) => x + y) plus: Int => (Int => Int) = $$Lambda$1362/1779572183@64635707 scala> val plus:Function1[Int,(Int)=>Int] = (x:Int) => ((y:Int) => x + y) plus: Int => (Int => Int) = $$Lambda$1363/969408428@24bc022 scala> val plus:(Int) => (Int) => Int = (x:Int) => ((y:Int) => x + y) plus: Int => (Int => Int) = $$Lambda$1364/1710966481@35c89f3b
下三つは全て同じ意味となる。カリー化に関して言えば、複数の引数リストを用いる事でも同様の事が実現できる。しかしこれは関数ではなくメソッドであることに留意されたし。
scala> def plus(l:Int)(r:Int):Int = l + r plus: (l: Int)(r: Int)Int scala> val plus10 = plus(10)_ plus10: Int => Int = $$Lambda$1375/155403162@28c4ecfb scala> plus10(100) res6: Int = 110 scala> val func_plus = plus _ func_plus: Int => (Int => Int) = $$Lambda$1376/1282098776@98b2097 scala> func_plus(10)(100) res7: Int = 110 scala> val func_plus:Function1[Int,Function1[Int,Int]] = plus _ func_plus: Int => (Int => Int) = $$Lambda$1378/816291015@60b0b8ea
冒頭ではplusメソッドを定義しているが、引数リストの一部にワイルドカードを使用すると関数が得られる。この時得られるのはメソッドではなく関数であるため、Functionnトレイトの無名サブクラス型のオブジェクトが返される。これはつまり、値が得られるという事を意味する。scalaでは、このようにメソッドと関数が厳密に区別される。両者の違いは、値が得られるかそうでないかが最も大きな差異となる。主にdef
キーワードを用いて定義されたものはメソッドであり、メソッドそのものをオブジェクトとする事はできない。
scala> def predicater(l:Int,r:Int,f:(Int,Int) => Boolean):Boolean = f(l,r) predicater: (l: Int, r: Int, f: (Int, Int) => Boolean)Boolean scala> val less= (x:Int,y:Int) => x < y less: (Int, Int) => Boolean = $$Lambda$1379/134733223@1db6fc87 scala> def predicater(l:Int,r:Int,f:(Int,Int) => Boolean):Boolean = f(l,r) predicater: (l: Int, r: Int, f: (Int, Int) => Boolean)Boolean scala> val less = (x:Int,y:Int) => x < y less: (Int, Int) => Boolean = $$Lambda$1380/1245768732@7244e3f7 scala> val greater = (x:Int,y:Int) => !less(x,y) greater: (Int, Int) => Boolean = $$Lambda$1382/1363010125@546ad6ad scala> predicater(10,20,less) res8: Boolean = true scala> predicater(10,20,greater) res9: Boolean = false
これを高階関数という。これは関数ではなくメソッドであるのだが、便宜上高階関数と言うのだとか。
あと例外も使えるようだ。
scala> def f(g:()=>Unit,h:()=>Unit):Unit = { | try{g()}finally{h()} | } f: (g: () => Unit, h: () => Unit)Unit scala> f( () => println("Maybe no throw"), () => println("Call") ) Maybe no throw Call scala> f( () => throw new Exception("throw exception"), () => println("But call") ) But call java.lang.Exception: throw exception at .$anonfun$res3$1(<console>:13) at scala.Function0.apply$mcV$sp(Function0.scala:34) at .f(<console>:12) ... 39 elided
foldは、左右ともにサポートされている。
scala> (1 to 10).foldLeft(0)((x,y) => x + y) res5: Int = 55 scala> def reverse[T](lst:List[T]):List[T] = lst.foldLeft(Nil:List[T])((a,b) => b::a) reverse: [T](lst: List[T])List[T] scala> reverse((1 to 10).toList) res6: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
ケースクラスといわれる機能もある。C++でのスコープ付きenumっぽい感じだ。
scala> sealed abstract class Student defined class Student scala> case object Bob extends Student defined object Bob scala> case object Tom extends Student defined object Tom scala> case object Jejus extends Student defined object Jejus scala> case object Maria extends Student defined object Maria scala> val x:Student = Maria x: Student = Maria
sealed
というキーワードはスーパークラス/トレイトに付与すると、その基の直接的なサブクラス/トレイトが同じファイル内でしか定義できないようにする修飾子である。ケースクラスの機能を使う場合に多様されるらしく、sealed
キーワードを付与することで、パターンマッチングの際のパターンとして網羅できていない場合に、コンパイラが警告文を発してくれるようになるとのこと。
scala> x match { | case Bob => () | case Tom => () | case Maria => () | } <console>:16: warning: match may not be exhaustive. It would fail on the following input: Jejus x match { ^
C++のスコープ付きenumなどと異なる点は、Scalaではあくまでクラスであるため、各々のデータが独立してパラメータを持てる点だ。
scala> sealed abstract class Expression defined class Expression scala> case class Add(lhs:Expression,rhs:Expression) extends Expression defined class Add ^ scala> case class Sub(lhs:Expression,rhs:Expression) extends Expression defined class Sub scala> case class Mul(lhs:Expression,rhs:Expression) extends Expression defined class Mul scala> case class Div(lhs:Expression,rhs:Expression) extends Expression defined class Div scala> case class int(value:Int) extends Expression defined class int scala> val exp = Add(int(42),Div(int(10),int(10))) exp: Add = Add(int(42),Div(int(10),int(10))) scala> def eval(exp:Expression):Int = exp match { | case Add(l,r) => eval(l)+ eval(r) | case Sub(l,r) => eval(l)- eval(r) | case Mul(l,r) => eval(l)* eval(r) | case Div(l,r) => eval(l)/ eval(r) | case int(v) => v | } eval: (exp: Expression)Int scala> eval(exp) res3: Int = 43
無効な値を意味するoptionも勿論準備されている。
scala> val op:Option[Int] = Option(42) op: Option[Int] = Some(42) scala> op.get res0: Int = 42 scala> op.isEmpty res1: Boolean = false scala> op.isDefined res2: Boolean = true scala> val op:Option[Int] = None op: Option[Int] = None scala> op.isEmpty res3: Boolean = true scala> op.isDefined res4: Boolean = false scala> op.get java.util.NoSuchElementException: None.get at scala.None$.get(Option.scala:349) at scala.None$.get(Option.scala:347) ... 39 elided scala> op.getOrElse(42) res7: Int = 42 scala> op.getOrElse(throw new RuntimeException("except")) java.lang.RuntimeException: except at .$anonfun$res8$1(<console>:13) at scala.Option.getOrElse(Option.scala:121) ... 39 elided scala> op match { | case Some(x) => x | case None => 42 | } res9: Int = 42 scala> val x = Option(42) x: Option[Int] = Some(42) scala> x.filter(_ < 43) res34: Option[Int] = Some(42) scala> x.filter(_ > 43) res35: Option[Int] = None scala> x ++ Option(84) res36: Iterable[Int] = List(42, 84) scala> x ++ None res37: Iterable[Int] = List(42)
上記の通り、例えNoneであったとしてもget
メソッド以外の操作では例外を発する事はなく、単にNoneが返ってきたり値から除外されたりなど、統一的な記述ができるようになっている。連結もなんのそのである。尚、NoneなOptionに対してmap操作などを行うと、必ずNoneが返ってくる。
scala> val x:Option[Int] = Some(6) x: Option[Int] = Some(6) scala> x.map(_ * 7) res23: Option[Int] = Some(42) scala> val x:Option[Int] = None x: Option[Int] = None scala> x.map(_ * 7 ) res24: Option[Int] = None scala> x.filter(_ >= 20) res25: Option[Int] = None
getOrElse
と同じようなものとしてfold
メソッドなどがある。
scala> Option[Int](7).fold(throw new RuntimeException){_ * 6} res5: Int = 42 scala> val none:Option[Int] = None none: Option[Int] = None scala> none.fold(throw new RuntimeException){_ * 6} java.lang.RuntimeException at .$anonfun$res6$1(<console>:13) at scala.Option.fold(Option.scala:158) ... 39 elided
あまり動きは以下と変わらない気がする。
scala> val f = (op:Option[Int]) => op.getOrElse(throw new RuntimeException) * 6 f: Option[Int] => Int = $$Lambda$1904/1963014637@729c62e9 scala> f(Some(7)) res2: Int = 42 scala> val none:Option[Int] = None none: Option[Int] = None scala> f(none) java.lang.RuntimeException at .$anonfun$f$2(<console>:11) at scala.Option.getOrElse(Option.scala:121) at .$anonfun$f$1(<console>:11) at .$anonfun$f$1$adapted(<console>:11) ... 39 elided
contains
メソッドを使うと、Optionの中身の値と比較することができる。この時中身がNoneであっても例外は投げられない。
scala> val x:Option[Int] = None x: Option[Int] = None scala> x.contains(42) res16: Boolean = false
flatten系も健在である。
scala> (x map { v1 => y map { v2 => v1 + v2 }}).flatten res2: Option[Int] = Some(13) scala> x flatMap { v1 => y map { v2 => v1 + v2 }} res4: Option[Int] = Some(13)
これらは、for式でリファクタリングできる。
scala> val a = Option(2) a: Option[Int] = Some(2) scala> val b = Option(3) b: Option[Int] = Some(3) scala> val c = Option(7) c: Option[Int] = Some(7) scala> for(i <- a; j <- b; k <-c )yield i * j * k res2: Option[Int] = Some(42)
話は変わって、暗黙の型変換を定義することができるようだ。
scala> implicit def IntToString(arg:Int):String = arg.toString <console>:11: warning: implicit conversion method IntToString should be enabled by making the implicit value scala.language.implicitConversions visible. This can be achieved by adding the import clause 'import scala.language.implicitConversions' or by setting the compiler option -language:implicitConversions. See the Scaladoc for value scala.language.implicitConversions for a discussion why the feature should be explicitly enabled. implicit def IntToString(arg:Int):String = arg.toString ^ IntToString: (arg: Int)String
暗黙の型変換を定義する際には、scala.language.implicitConversionsをimportすることが推奨されるようだ。まぁこれは、暗黙の型変換を定義していることを意図するためのimportだろう。それと、言語機能をimportさせることで言語そのもののをmodule likeにしたいという意味合いが込められているようだ。
scala> import scala.language.implicitConversions <console>:11: warning: Unused import import scala.language.implicitConversions ^ import scala.language.implicitConversions scala> implicit def IntToString(arg:Int):String = arg.toString IntToString: (arg: Int)String scala> val x:String = 42 <console>:9: warning: Unused import import scala.language.implicitConversions ^ x: String = 42
暗黙の型変換が広く有用的に使われるのは、pimp my libraryと呼ばれる利用方法で、これは既存のクラスへメソッドを追加しているように見せかける。C++の型変換演算子をグローバルに定義したような感じだ。
scala> class ListSorted(x:List[Int]){ | def concatSorted(y:List[Int]):List[Int] = (x:::y).sorted | } defined class ListSorted scala> implicit def toListSorted(arg:List[Int]):ListSorted = new ListSorted(arg) toListSorted: (arg: List[Int])ListSorted scala> List(4,1,9).concatSorted(List(6,3,2)) res0: List[Int] = List(1, 2, 3, 4, 6, 9)
暗黙の変換は単にクラスの引数に値を渡してnewしているだけなのでやや冗長だ。これは以下のように書ける。
scala> implicit class ListSorted(x:List[Int]){ | def concatSorted(y:List[Int]):List[Int] = (x:::y).sorted | } defined class ListSorted scala> List(4,1,9).concatSorted(List(6,3,2)) res2: List[Int] = List(1, 2, 3, 4, 6, 9)
Implicit parameterという機能もある。これは、カリー化されたメソッドの最後の引数にimplicitキーワードを付与する事で、その関数の呼び出しの最も直近なimplicitが付与された変数をメソッド呼び出しの際の束縛とし、呼び出しの際に明示的な変数の差し込みをなくす事ができる機能だ。
scala> class X(val i:Int){ | final override def toString():String = i.toString | } defined class X scala> def f()(implicit x:X):X = x f: ()(implicit x: X)X scala> implicit val x = new X(42) x: X = 42 scala> f() res0: X = 42 scala> f()(new X(53)) res2: X = 53
勿論上記の通り、明示的にもオブジェクトを渡す事ができる。
一通り文法は把握したはずなので、最後に、S-99: Ninety-Nine Scala Problemsが練習として良さそうだったので順に解いてみる。取り敢えず本エントリでは基本的なリスト操作までを書いてみるとする。
P01
scala> def last[T](lst:List[T]):T = { | lst match{ | case tail::Nil => tail | case _::tail => last(tail) | case _ => throw new NoSuchElementException | } | } last: [T](lst: List[T])T scala> last((1 to 42).toList) res0: Int = 42
P02
scala> def last_two[T](lst:List[T]):T = { | lst match{ | case target::_::Nil => target | case _::tail => last_two(tail) | case _ => throw new NoSuchElementException | } | } last_two: [T](lst: List[T])T scala> last_two((1 to 42).toList) res3: Int = 41
P03
scala> def nth[T](n:Int,lst:List[T]):T = (n,lst) match { | case (0,h::_) => h | case (n,_::tail) => nth(n-1,tail) | case _ => throw new IndexOutOfBoundsException | } nth: [T](n: Int, lst: List[T])T scala> val smplst = (1 to 42).toList smplst: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42) scala> nth(smplst.length - 1,smplst) res1: Int = 42 scala> nth(smplst.length,smplst) java.lang.IndexOutOfBoundsException at .nth(<console>:15) ... 29 elided
P04
scala> def size[T](lst:List[T]):Int = lst.foldLeft(0){(c,_) => c + 1 } size: [T](lst: List[T])Int scala> size((1 to 42).toList) res0: Int = 42
P05
scala> def reverse[T](lst:List[T]):List[T] = lst.foldLeft(Nil:List[T])((a,b)=>b::a) reverse: [T](lst: List[T])List[T] scala> reverse((1 to 42).toList) res0: List[Int] = List(42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
P06
scala> def is_palindrome[T](lst:List[T]):Boolean = lst == reverse(lst) is_palindrome: [T](lst: List[T])Boolean scala> is_palindrome( (1 to 42).toList ::: reverse((1 to 42).toList) ) res4: Boolean = true scala> is_palindrome( (1 to 42).toList ) res5: Boolean = false
P07
この問題はflatMap
を使う。flatMap
は、map
されたものをflatten
する機能である。
scala> List((1 to 5).toList,(1 to 5).toList) map { x => 42 +: x } res6: List[List[Int]] = List(List(42, 1, 2, 3, 4, 5), List(42, 1, 2, 3, 4, 5)) scala> List((1 to 5).toList,(1 to 5).toList) flatMap { x => 42 +: x} res7: List[Int] = List(42, 1, 2, 3, 4, 5, 42, 1, 2, 3, 4, 5)
これを使うと、この問題はとても楽に書けるだろう。
scala> def flat(lst:List[Any]):List[Any] = lst flatMap{ | case x:List[_] => flat(x) | case x => List(x) | } flat: (lst: List[Any])List[Any] scala> val lst = List((1 to 5).toList,(1 to 3).toList,(1 to 4).toList) lst: List[List[Int]] = List(List(1, 2, 3, 4, 5), List(1, 2, 3), List(1, 2, 3, 4)) scala> flat(lst) res0: List[Any] = List(1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3, 4)
P08
この問題にはdropWhile
サブコレクションを使う。dropWhile
サブコレクションは、引数に記述される条件に合致するオブジェクトを排除する。尚、条件に合致しない要素が見つかった場合、そこから先はdropされない。
scala> val a = (1 to 10).filter(_ % 2 == 0).toList a: List[Int] = List(2, 4, 6, 8, 10) scala> val b = (1 to 10).filter(_ % 2 != 0).toList b: List[Int] = List(1, 3, 5, 7, 9) scala> (a ::: b ::: a).dropWhile(_ % 2 == 0) res52: List[Int] = List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)
dropWhile
の対となるサブコレクションとしてtakeWhile
というサブコレクションもある。これは、引数に記述される条件に合致するオブジェクトのみに絞る。これも条件に合致しない要素に当たった瞬間に処理が止まる。
scala> (a ::: b ::: a).takeWhile(_ % 2 == 0) res53: List[Int] = List(2, 4, 6, 8, 10)
これらに加えて、span
というサブコレクションも備えている。span
は条件に合致する集合とそうでない集合をそれぞれ一つの集合として分けて返す。span
も、条件に合致しないオブジェクトに当たった場合にその時点で処理が止まる。
scala> (a ::: b ::: a).span(_ % 2 == 0) res56: (List[Int], List[Int]) = (List(2, 4, 6, 8, 10),List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10))
これらを使えば、問題は以下のように解ける。
scala> def no_eleminate_duplicate(lst:List[Symbol]):List[Symbol] = lst match { | case Nil => Nil | case head::tail => head::no_eleminate_duplicate(tail.dropWhile(_ == head)) | } no_eleminate_duplicate: (lst: List[Symbol])List[Symbol] scala> no_eleminate_duplicate( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) ) res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)
P09
まず書いてみたのは以下のような感じ。
scala> def pack_duplicate[T](lst:List[T]):List[Any] = { lst match { | case Nil => Nil | case head::tail => { | if(head == tail.head) | (List(head) ::: tail.takeWhile(_ == head)) :: pack_duplicate(tail.dropWhile(_ == head)) | else | List(head) :: pack_duplicate(tail.dropWhile(_ == head)) | } | case _ => throw new NoSuchElementException | } | } pack_duplicate: [T](lst: List[T])List[Any] scala> pack_duplicate( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) ) res0: List[Any] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))
この実装でも問題そのものは解決しているのだが、型がList[Any]
な部分があまり宜しくないので、書き直した。
scala> def pack_duplicate[T](lst:List[T]):List[List[T]] = lst match { | case Nil => Nil | case x => { | val (packed,next) = x span{_ == lst.head} | if(next == Nil)List(packed) | else packed :: pack_duplicate(next) | } | } pack_duplicate: [T](lst: List[T])List[List[T]] scala> pack_duplicate( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) ) res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))
P10
scala> def run_length[T](lst:List[T]):List[(T,Int)] = pack_duplicate(lst) map { x => (x.head,x.length) } run_length: [T](lst: List[T])List[(T, Int)] scala> run_length( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) ) res1: List[(Symbol, Int)] = List(('a,4), ('b,1), ('c,2), ('a,2), ('d,1), ('e,4))
P11
この問題では、Either
という型を使う。Either
は指定した二つの型のどちらを入れる事ができる。型の指定には、Left
、Right
メソッドを使う。C++ではstd::variant
あたりに該当するだろうか。
scala> val e:Either[Int,List[Int]] = Left(42) e: Either[Int,List[Int]] = Left(42) scala> val e:Either[Int,List[Int]] = Right(List(42)) e: Either[Int,List[Int]] = Right(List(42))
これを使えば、問題は以下のように解ける。
scala> def run_length_mod[T](lst:List[T]):List[Either[T,(T,Int)]] = run_length(lst) map { | x => if(x._2 == 1)Left(x._1) else Right(x) | } run_length_mod: [T](lst: List[T])List[Either[T,(T, Int)]] scala> run_length_mod( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) ) res0: List[Either[Symbol,(Symbol, Int)]] = List(Right(('a,4)), Left('b), Right(('c,2)), Right(('a,2)), Left('d), Right(('e,4)))
P12
scala> def run_length_decode[T](lst:List[(Int,T)]):List[T] = lst flatMap{ x => List.fill(x._1)(x._2) } run_length_decode: [T](lst: List[(Int, T)])List[T] scala> run_length_decode( List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)) ) res4: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
P13
scala> def run_length[T](lst:List[T]):List[(T,Int)] = lst match { | case Nil => Nil | case x => val (packed,next) = x span { _ == lst.head } | (packed.head,packed.length) :: run_length(next) | } run_length: [T](lst: List[T])List[(T, Int)] scala> run_length( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) ) res5: List[(Symbol, Int)] = List(('a,4), ('b,1), ('c,2), ('a,2), ('d,1), ('e,4))
P14
scala> def make_duplicate[T](lst:List[T]):List[T] = lst match { | case Nil => Nil | case head::tail => (List.fill(2)(head)) ::: make_duplicate(tail) | } make_duplicate: [T](lst: List[T])List[T] scala> make_duplicate( List('a, 'b, 'c, 'c, 'd) ) res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)
P15
scala> def make_duplicate[T](i:Int,lst:List[T]):List[T] = lst match { | case Nil => Nil | case head::tail => (List.fill(i)(head)) ::: make_duplicate(i,tail) | } make_duplicate: [T](i: Int, lst: List[T])List[T] scala> make_duplicate( 3, List('a, 'b, 'c, 'c, 'd) ) res8: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)
P16
scala> def drop[T](target:Int,lst:List[T]):List[T] = (target,lst) match{ | case (_,Nil) => Nil | case (1,_::tail) => tail | case (x,head::tail) => List(head) ::: drop(x-1,tail) | } drop: [T](target: Int, lst: List[T])List[T] scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) ) res0: List[Symbol] = List('a, 'b, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)
zipWithIndex
を使えば更に短く書ける。zipWithIndex
はインデックス値とペアにした集合を返す。
scala> (1 to 10).zipWithIndex res1: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,6), (8,7), (9,8), (10,9))
これを使って、指定されたインデックス値で除算しその結果が割り切れていないもののみを残す。
scala> def drop[T](target:Int,lst:List[T]):List[T] = lst.zipWithIndex filter { | x => ((x._2 + 1) % target) != 0 | } map { _._1 } drop: [T](target: Int, lst: List[T])List[T] scala> drop( 3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) ) res2: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)
P17
この問題は、take
、drop
メソッドを使うと簡単だ。take
、drop
はそれぞれ指定されたインデックス値までの値を取得、指定されたインデックス値まで捨てるメソッドである。
scala> val lst = (1 to 42).toList lst: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42) scala> lst.take(lst.length/2) res6: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21) scala> lst.drop(lst.length/2) res7: List[Int] = List(22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
これらを使うと以下のように解ける。
scala> def split[T](target:Int,lst:List[T]):Either[List[T],(List[T],List[T])] = lst match { | case Nil => Left(Nil) | case x => Right((x.take(target),x.drop(target))) | } split: [T](target: Int, lst: List[T])Either[List[T],(List[T], List[T])] scala> split( 3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k ) ) res0: Either[List[Symbol],(List[Symbol], List[Symbol])] = Right((List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k)))
P18
scala> def slice[T](h:Int,t:Int,lst:List[T]):List[T] = lst match{ | case Nil => Nil | case x => x.drop(h).take(t-h) | } slice: [T](h: Int, t: Int, lst: List[T])List[T] scala> slice( 3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) ) res1: List[Symbol] = List('d, 'e, 'f, 'g)
P19
scala> def rotate[T](target:Int,lst:List[T]):List[T] = (target,lst) match { | case (_,Nil) => Nil | case (t,x) if t > 0 => x.drop(t) ::: x.take(t) | case (t,x) if t < 0 => x.drop(x.length+t) ::: x.take(x.length+t) | } rotate: [T](target: Int, lst: List[T])List[T] scala> rotate( 3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) ) res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c) scala> rotate( -2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) ) res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)
P20
この問題はsplitAt
を使うと容易に実装できる。splitAt
は指定されたインデックス値で分割する。
scala> List(1,2,3).splitAt(2) res2: (List[Int], List[Int]) = (List(1, 2),List(3))
これを使うと以下のように書ける。
scala> def removeAt[T](target:Int,lst:List[T]):(List[T],T) = lst.splitAt(target) match { | case (Nil,_) => throw new NoSuchElementException | case (_,Nil) => throw new NoSuchElementException | case (left,target::right) => (left ::: right,target) | } removeAt: [T](target: Int, lst: List[T])(List[T], T) scala> removeAt(1, List('a, 'b, 'c, 'd)) res11: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)
P21
scala> def insertAt[T](value:T,target:Int,lst:List[T]):List[T] = lst.splitAt(target) match { | case (Nil,_) => throw new NoSuchElementException | case (_,Nil) => throw new NoSuchElementException | case (left,target::right) => (left ::: List(value,target) ::: right) | } insertAt: [T](value: T, target: Int, lst: List[T])List[T] scala> insertAt('new, 1, List('a, 'b, 'c, 'd)) res14: List[Symbol] = List('a, 'new, 'b, 'c, 'd)
P22
scala> def range(head:Int,tail:Int):List[Int] = (head to tail).toList range: (head: Int, tail: Int)List[Int] scala> range(4,9) res15: List[Int] = List(4, 5, 6, 7, 8, 9)
P23
乱数にはutil.Randomを使う。
scala> val rnd = new util.Random rnd: scala.util.Random = scala.util.Random@10bb5dc9 scala> for(x <- 1 to 10)yield rnd.nextInt(10) res28: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 9, 8, 7, 9, 1, 5, 0, 3, 5)
scala> def randomSelect[T](len:Int,lst:List[T]):List[T] = (len,lst,new util.Random) match { | case (x,l,_) if x >= l.length || l == Nil => Nil | case (x,l,rnd) => (for(i <- 0 until x)yield l.drop(rnd.nextInt(l.length-len)).take(1).head).toList | } randomSelect: [T](len: Int, lst: List[T])List[T] scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h)) res3: List[Symbol] = List('c, 'b, 'd) scala> randomSelect(4, List('a, 'b, 'c, 'd, 'f, 'g, 'h)) res4: List[Symbol] = List('b, 'c, 'c, 'a) scala> randomSelect(5, List('a, 'b, 'c, 'd, 'f, 'g, 'h)) res5: List[Symbol] = List('a, 'b, 'a, 'b, 'a)
P24
scala> val lotto = (count:Int,max:Int) => randomSelect(count,List.range(1,max+1)) lotto: (Int, Int) => List[Int] = $$Lambda$1472/1152751947@774406ba scala> lotto(6, 49) res8: List[Int] = List(4, 36, 29, 11, 40, 9)
P25
scala> def removeAt[T](n:Int,lst:List[T]):(List[T],T) = lst.splitAt(n) match { | case (Nil,_) if n < 0 => throw new NoSuchElementException | case (_,Nil) => throw new NoSuchElementException | case (left,head::tail) => (left ::: tail,head) | } removeAt: [T](n: Int, lst: List[T])(List[T], T) scala> def randomSelect[T](n:Int,lst:List[T]):List[T] = (n,lst) match { | case (0,_) => List[T]() | case (_,Nil) => Nil | case (nm,l) => { | val index = (Math.random * l.length).toInt | val (short,item) = removeAt(index,l) | item :: randomSelect(nm-1,short) | } | } randomSelect: [T](n: Int, lst: List[T])List[T] scala> def randomPermute[T](lst:List[T]) = randomSelect(lst.length,lst) randomPermute: [T](lst: List[T])List[T] scala> randomPermute( List('a, 'b, 'c, 'd, 'e, 'f) | ) res0: List[Symbol] = List('f, 'b, 'a, 'd, 'e, 'c)
P26
scala> def combination[T](n:Int,lst:List[T]):List[List[T]] = (n,lst) match { | case (_,Nil) => Nil | case (0,_) => Nil | case (1,x) => lst.map(List(_)) | case (nm,head::tail) => combination(nm-1,tail).map(head::_) ::: combination(nm,tail) | } combination: [T](n: Int, lst: List[T])List[List[T]] scala> combination( 3, List('a, 'b, 'c, 'd, 'e, 'f) ) res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), List('a, 'b, 'f), List('a, 'c, 'd), List('a, 'c, 'e), List('a, 'c, 'f), List('a, 'd, 'e), List('a, 'd, 'f), List('a, 'e, 'f), List('b, 'c, 'd), List('b, 'c, 'e), List('b, 'c, 'f), List('b, 'd, 'e), List('b, 'd, 'f), List('b, 'e, 'f), List('c, 'd, 'e), List('c, 'd, 'f), List('c, 'e, 'f), List('d, 'e, 'f))
P27
scala> def group[T](left:List[Int],right:List[T]):List[List[List[T]]] = left match { | case Nil => Nil | case head :: tail => { | combination(head,right).foldLeft(List[List[List[T]]]()){ | (lists,comb) => group(tail,(right diff comb)) match { | case Nil => lists ::: List(List(comb)) | case other => lists ::: other.map(comb :: _ ) | } | } | } | } group: [T](left: List[Int], right: List[T])List[List[List[T]]] scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")) res9: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Evi), List(David, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Flip), List(David, Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Gary), List(David, Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Hugo), List(David, Evi, Flip, Gary, Ida)), List(List(Aldo, Beat), List(Carla, Ida), List(David, Evi, Flip, Gary, Hugo)), List(List(Aldo, Beat), List(David, Evi), List(Carla, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(David, Flip), List(Carla, Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(David, Gary), List(Carla, Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List(Dav...
この問題にはdiff
を使っている。diff
は排他的論理和的な処理で、双方の内一方だけが持つ要素を集合として返す。
scala> List.range(1,10) diff List.range(1,10).filter(_ % 2 == 0) res12: List[Int] = List(1, 3, 5, 7, 9)
否定でフィルターをするfilterNot
でも同じことができる。
scala> List.range(1,10) filterNot List.range(1,10).filter(_ % 2 == 0).contains res24: List[Int] = List(1, 3, 5, 7, 9)
filterNot
は条件としてpredicate functionを受け取るため、contains
メソッドを使って指定された値を内包しているかどうかを返す関数を生成しそれを適用している。
scala> val has_value = List.range(1,10).filter(_ % 2 == 0).contains _ has_value: Any => Boolean = $$Lambda$1690/121969977@29463fba scala> has_value(1) res28: Boolean = false scala> has_value(2) res29: Boolean = true
P28
scala> def qsort[T](lst:List[T],pred:(T,T) => Boolean):List[T] = lst match { | case x if x.length <= 1 => x | case x => { | removeAt((Math.random * x.length).toInt,x) match { | case (other,pivot) => { | val empty = (List[T](),List[T]()) | val (lesser,greater) = other.foldLeft(empty) { | (acc,ot) => acc match { | case (l1,l2) => pred(ot,pivot) match { | case true => (l1 ::: List(ot),l2) | case false => (l1,l2 ::: List(ot)) | } | } | } | qsort(lesser,pred) ::: List(pivot) ::: qsort(greater,pred) | } | } | } | } qsort: [T](lst: List[T], pred: (T, T) => Boolean)List[T] scala> def lsort[T](lst:List[List[T]]) = qsort(lst,(x:List[T],y:List[T]) => x.length < y.length) lsort: [T](lst: List[List[T]])List[List[T]] scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o))) res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('m, 'n), List('d, 'e), List('f, 'g, 'h), List('a, 'b, 'c), List('i, 'j, 'k, 'l))
総括
Scalaは楽しい。
— roκi (@530506) 2017年5月29日
後、書いている感じとしてはリスト操作では正にC++でのパラメータパックを利用した色々な事とやっている事はほぼ同じだな〜と。後はコップ本とかを買ってしっかり深く学習したい感じ。