Rokiのチラ裏

学生による学習のログ

scala始めました

scala警察が怖いという話題で少し盛り上がっていたので、始めてみた。sbtとscalabrewから導入した。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)

foryieldだったり、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)

toStringprintlnで出力するためにオーバーライドして定義する。それと、メソッドのシグネチャに複数の引数リストを作る構文がある事に驚きだ。これはつまりカリー化という概念を文法としてサポートする事を意味する。

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 Bbarの初期化に使われる。同時点で、末初期化の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では、関数と言ったら、それは大抵標準搭載されたFunction0Function22のトレイトの無名サブクラスのインスタンスの事を示すのだとのこと。

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は指定した二つの型のどちらを入れる事ができる。型の指定には、LeftRightメソッドを使う。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 この問題は、takedropメソッドを使うと簡単だ。takedropはそれぞれ指定されたインデックス値までの値を取得、指定されたインデックス値まで捨てるメソッドである。

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))

総括

後、書いている感じとしてはリスト操作では正にC++でのパラメータパックを利用した色々な事とやっている事はほぼ同じだな〜と。後はコップ本とかを買ってしっかり深く学習したい感じ。