[Coq] Scala PartialFunction is Monoid

「Scala の PartialFunction が orElse の演算に関して monoid になっているのでは？」という stackoverflow の議論 Scala PartialFunction can be Monoid? について twitter 上で目にしたので証明してみた。
Scala の PartialFunction[A,B] は失敗する関数と考えれば A -> option B と考えて良い。
Coq は外延性の公理を入れないと、(fun x => f x) = f が言えないので、ライブラリ Logic.FunctionalExtensionality を Import してるとか extensionality というタクティックを使ってるとかが目新しいぐらいで、他は単に型クラス定義してインスタンスが公理を満たすのを証明するだけ。

Section PartialFunctionMonoid.
(* See http://stackoverflow.com/questions/9067904/scala-partialfunction-can-be-monoid *)
 
Require Import Logic.FunctionalExtensionality.
 
Class Monoid(T:Type) := {
  op : T -> T -> T;
  e : T;
  left_id : forall t, op e t = t;
  right_id : forall t, op t e = t;
  assoc : forall t u v, op (op t u) v = op t (op u v)
}.
 
Variable A B:Type.
Definition pf := A -> option B.
Definition orElse(f g:pf):pf :=
fun a => match (f a) with
  | None => g a
  | Some b => Some b
  end.       
 
Instance pf_monoid : Monoid pf := {
  op := orElse;
  e := (fun a => None)
}.
Proof.
  intros. unfold orElse. simpl.
  extensionality a. auto.
 intros. unfold orElse.
 extensionality a. destruct (t a); auto.
intros. unfold orElse. extensionality a.
destruct (t a); auto.
Defined.
 
End PartialFunctionMonoid.

[Scala] Fibonacci series including 7110

　今更ながら http://recruit.drecom.co.jp/event2010 の「7110を含むフィボナッチ数列で、初期値の組み合わせが一番小さいものをあげろ。※自然数に限る」をScalaで解いてみた。
　もうイベントは終わったから解答公開してもいいよね。

　fib が 7110以下の範囲のフォボナッチ数列を計算する関数。zipとか使って格好良く書けるかもとも思うが、判りやすさ優先で。ysのところにxs'と書けないScalaは残念な感じだ。

scala> def fib(n0:Int,n1:Int) = {                   
     |   def f(xs:List[Int]):List[Int] = xs match { 
     |     case a::b::ys if a < 7110 => f((a+b)::xs)
     |     case _ => xs                             
     |   }                                          
     |   f(n1::n0::Nil)                                    
     | }
fib: (Int,Int)List[Int]

scala> def solve = for( n1 <- (1 to 100).toList;                       
     |   n0 <- (1 to n1).toList if fib(n0,n1).head==7110               
     | ) yield {(n0,n1)}
solve: List[(Int, Int)]

scala> solve
res7: List[(Int, Int)] = List((16,70), (70,86))
scala> 

[Scala] Scala 2.8 Continuation (1)

root/compiler-plugins/continuations/trunk/doc/examples/continuationsに載っているサンプルコードをREPLで写経してみます。

Test0.scala

scala> import scala.util.continuations._            
import scala.util.continuations._

scala> reset {                                      
     |   2 * {                                      
     |     println("up")                            
     |     val x = shift((k:Int=>Int) => k(k(k(8))))
     |     println("down")                          
     |     x                                        
     |   }                                          
     | }
up
down
down
down
res1: Int = 64

これはdef k(i:Int):Int = {println("down"); 2*i}と考えればOK。

Test1.scala

scala> object Test1 {                                 
     |   def testThisMethod() = {                     
     |     1 + (shift((k:Int=>Int) => k(k(k(17)))))   
     |   }
     |   def testThisCallingMethod() = {              
     |     testThisMethod() * 2                       
     |   }
     |   def m() {
     |     val result = reset(testThisCallingMethod())
     |     println(result)
     |   }
     | }
defined module Test1

// ((((((17 + 1) * 2) + 1) * 2) + 1) * 2) = 150

scala> Test1.m()                                      
150

k = (_+1)*2 と考えればこれも予想通りの結果。
resetの中にshiftを書くのはOKだが、resetなしでshiftだけの関数を定義しようとすると下記の様にエラーになります。仕方が無いのでobject Test1 {...} に包みます。

scala> def testThisMethod() = {
     |   1 + (shift((k:Int=>Int) => k(k(k(17)))))
     | }
:2: error: type mismatch;
 found   : Int @scala.util.continuations.cpsSynth @scala.util.continuations.cpsParam[Int,Int]
 required: Int
object RequestResult$line4$object {
                                  ^

Test2.scala

scala> object Test2 {                             
     |   def methA() = {                          
     |     def fun(k:Int=>String) = {             
     |       for(i <- List(1,2,3,4)) println(k(i))
     |       Some("returnvalue")                  
     |     }                                      
     |     2 * shift(fun)                         
     |   }
     |   def methB() = {                          
     |     "+++ "+methA().toString()              
     |   }
     |   def m() = reset(methB())                 
     | }
defined module Test2

scala> Test2.m()
+++ 2
+++ 4
+++ 6
+++ 8
res0: Some[java.lang.String] = Some(returnvalue)

k = "+++" + (2 * _).toString() ですか。

[Scala] Scala 2.8 RC4 and continuation plugin

　Scala 2.8 RC4 が出ました --- が、なんかバグがあるらしく来週には RC5 が出るそうです。なんか品質安定しませんね＞Scala 2.8。

　RC4からは限定継続のコンパイラプラグインが付属される様になりました。
　使い方はこんな感じ。Scala 2.8 RC4を導入したディレクトリに居るとします。pluginにパスを通し、continuationをenableにする必要があります。

% cd ~/scala28rc4
% ./bin/scala -Xpluginsdir ./misc/scala-devel/plugins/ ¥
-Xplugin:continuations -P:continuations:enable
Welcome to Scala version 2.8.0.RC4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_20).
Type in expressions to have them evaluated.
Type :help for more information.

scala> import scala.util.continuations._         
import scala.util.continuations._

scala> reset {
     |   shift { (k:Int=>Int) =>
     |     k(k(k(7)))
     |   } + 1
     | }
res0: Int = 10

scala> 

限定継続をおいおい勉強しようと思います。

[Scala] Articles about Scala 2.8 on ITpro

　Scala 2.8に関する紹介記事をITproに書きました。ほぼ年末年始休暇を費やして書き、2010年の1,2月に分けて掲載。

第15回 Scala 2.8の新機能 (1)
第16回 Scala 2.8の新機能 (2) --- コレクションライブラリの再実装

　記事を書く機会を与えてくださった羽生田さんに感謝を。

[Scala] Hindley-Milner Type Inference

Hindley-Milnerの型推論を理解したいと思い、とりあえずScala by Exampleに載っているコードにデバッグプリントを大量に挿入して動かしてみました。
動かした結果を、将来の自分の為にメモしたものがHM.pdf、
動かしたソースはHM.scalaにあります。

アルゴリズム自体はHindley Milner Type Inference Algorithm (PS file)とか簡潔に書かれている。が、こうやってデバッグプリントを挟んで動かしてみないとなかなか判らない...。

[Scala] Talk on scala-be's "Step by Step Scala" on 12/22

　東京のScala勉強会であるscale-beの、12/22開催のStep by Step Scala [vol.06]@scala-be (ATNDへのリンク)で講師をすることになりました。
　今回は主として14章の「表明と単体テスト」のScalaCheckの使い方を中心に話をしようと思っています。ScalaCheckは「満たすべき性質を記述する」ことでテストケースを自動生成してくれる面白い単体テストツールですが、従来のxUnit系テストツールとはちょっと使い方が違うというのもあって、使い方を学ぶには良いのではないかと思います。
　参加者希望者は上記のATNDのリンクから申し込みをしていただければと思います。
　今回は日程が12/22と多くの忘年会と重なる日で、割と参加者は少なそうでちょっと残念。

[Scala] Scala Style Guide

Scala Style Guide (PDF)

Scalaのコーディングスタイルガイド。

[scala] Proposed Style Guideで議論されていて、Oderskyもコメントしてる。これが叩き台になって正式版が出たら訳すといいかなぁ。

[Scala][Book] Pro Scala: Monadic Design Patterns for the Web

APressからPro Scala: Monadic Design Patterns for the Webという本が出る様です。
今までの職業的プログラマの視野に入っていなかったが、実は実用的にも重要である概念の、
- Monadic design patterns
- Zippers and data type differentiation
- Delimited continuations
を考察するとのこと。

「モナド＝デザインパターン」というのはあちこちで書かれていることだし、モナドに限らず圏論的視点で計算を考えようという話は檜山さんのブログで繰り返し出て来るテーマ（11/28開催のセミナーのコパスタを食べる余会はまだ空席があるようですよ）。
Delimited continuationということはScala 2.8対応だし、限定継続を一般向けに紹介した本は今までにあるのかなぁ？なんかそれだけでも価値があるよね。

なんか非常に楽しみな本ですね。

[Event] Recent Days

今週は、Step by Step Scala [vol.04]@scala-beで話をしたり、Haskellナイトを見に行ったり、Scala Hack-a-thon #1に参加したり、でした。

Step-by-Step Scalaは、（少なくとも何人かの方には）Swarmについて興味を持ってもらえた様なので満足。この先の仕事の状況がまだ確定しないのだけど、また機会があればScalaの講師を出来ればなぁ、とか。

Haskellナイトは、本の話がちょっと多過ぎたかなぁとは思うのだけど、出版合わせのイベントだから仕方がないのかなぁ。もうちょっとHaskellの話を聞きたかったかも。

Scala Hackathonは存在を知った時には既に満員になっていて参加を諦めてたんですが、当日朝見たらキャンセルが大量に出たみたいで慌てて家を出た次第。yuroyoroさんの作成したテキストが良く出来ていて、みんな黙々とそれを読んでいたのかな？かつ、質問はtwitterで主として行われていたみたい。懇親会も楽しく参加させて頂きました。

[Scala] Talk on scala-be's "Step by Step Scala" in November

東京のScala勉強会にscale-beというのがありまして、隔週の水曜or木曜の夜に新宿の豆蔵で開催しています。
内容はOderskyの「Scalaスケーラブルプログラミング」の章立てに沿って講師がScalaを解説するというもので、読書会の様にテキストに厳格に沿う訳ではありません。
参加者は、

• 出来れば該当の本を持参して下さい。本の内容を逐一全部話す訳ではないですし。
  
• 出来れば最近のScala実行系（Scala 2.7系）がインストールされたノートPCを持参して下さい。簡単な課題とか、実際に自分でインタプリタ上で動作確認したり、などがあるので。同様に、Scala APIドキュメント（JavaDoc）などをインストールしておくと良いです。（なお、会場はコンセントは利用可能ですが、インターネット接続は提供されません。）
  

あと、勉強会の後に懇親会も行っています。

で、11/4(Wed), 11/19(Thr)の２回は私が講師を担当する事になりました。それぞれ6,7章と8,9章の範囲について話す予定です。11/19の回にはテキストの内容からちょっと離れて最近のScalaの話題という事でSwarmの話をちょっとだけ紹介しようと思ってます。

なお、参加申し込みはATND上で行われ、ATNDへのリンクを含む開催案内は定期的にscala-be上で告知されます。
では、11月に勉強会会場でお会いしましょう。

---
追記：11/21

２回の発表で使用した資料はPDF形式でscala-be Google groupのファイル置き場で公開してます。

[Scala] sbt : simple-build-tool (1)

sbt (simple-build-tool) は Scala で書かれたビルドツールです。
これもscalaで書かれたDSL的なツールであり、プロジェクトのビルドの設定などをscalaで記述する事が出来たりします。

試しに使ってみて、使い方が判ったら追記していこうと思います。

★インストール

Setupのページに従い作業します。
私は MacOS ユーザなので Unix の指示に従い作業。

まずsbt-launcher-0.5.1.jar をダウンロードして指示通り~/binに置き、~/bin/sbt ファイルを作り chmod したりします。

% ls ~/bin
sbt   sbt-launcher-0.5.1.jar
% cat ~/bin/sbt
java -Xmx256M -jar `dirname $0`/sbt-launcher-0.5.1.jar "$@"
%

★動作確認
空の (*.scala の無い) 作業ディレクトリに hw.scala を作ります。(main メソッドを探して自動で判断する都合上、無関係なソースがあると巧く動作しません。最初それで失敗しました。)

% ls
hw.scala
% cat hw.scala
object Hi { def main(args: Array[String]) { println("Hi!") } }
% 

とりあえず下記の様に動きました。

[apple-3:~/work/scala/hw] miyamoto% ~/bin/sbt 
Project does not exist, create new project? (y/N/s) : s
:: loading settings :: url = jar:file:/Users/miyamoto/bin/sbt-launcher-0.5.1.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: retrieving :: sbt#boot
 confs: [default]
 2 artifacts copied, 0 already retrieved (9831kB/149ms)
:: retrieving :: sbt#boot
 confs: [default]
 3 artifacts copied, 0 already retrieved (3171kB/26ms)
[info] Building project scratch 1.0 using sbt.DefaultProject
[info]    with sbt 0.5.1 and Scala 2.7.5
[info] No actions specified, interactive session started. Execute 'help' for more information.
> run
[info] 
[info] == compile ==
[info]   Source analysis: 1 new/modified, 0 indirectly invalidated, 0 removed.
[info] Compiling main sources...
[info] Compilation successful.
[info]   Post-analysis: 2 classes.
[info] == compile ==
[info] 
[info] == run ==
[info] Running Hi ...
Hi!
[info] == run ==
[success] Successful.
[info] 
[info] Total time: 2 s
> quit
[info] 
[info] Total session time: 14 s
% 

この結果として下記の様にプロジェクトが生成されます。このあたりは Maven とかと同様な感じ。各プロジェクト毎にscala-compiler.jarを持ったりするのは、なんか富豪的だなぁ。

% ls -RCF
hw.scala project/ target/

./project:
boot/   build.properties

./project/boot:
scala-2.7.5/

./project/boot/scala-2.7.5:
lib/  sbt-0.5.1/ update.log

./project/boot/scala-2.7.5/lib:
scala-compiler.jar scala-library.jar

./project/boot/scala-2.7.5/sbt-0.5.1:
ivy-2.0.0.jar  jsch-0.1.31.jar  sbt_2.7.5-0.5.1.jar

./target:
analysis/ classes/

./target/analysis:
applications  external  hashes
dependencies  generated_files  tests

./target/classes:
Hi$.class Hi.class
% 

[Scala] S-99: Ninety-Nine Scala Problems (P01-28)

S-99: Ninety-Nine Scala ProblemsのList編(P01-P28)の抄訳です。

• アスタリスクの数は難易度です。


• 効率も大事ですが、エレガントな回答を求めます。可能ならばより簡潔で、計算量が少なく、末尾再帰になっている回答を作りましょう。


• Scalaの組み込み関数を使ってもOKです。が、使わないほうが勉強になります。


• 答えが知りたければ、元の英語文書の各問題のリンクをクリックして下さい。

P01 (*) リストの最後の要素を求めよ。

scala> last(List(1, 1, 2, 3, 5, 8))
res0: Int = 8


P02 (*) リストの最後から二番目の要素を求めよ。

scala> penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5


P03 (*) リストのn番目の要素を求めよ。但しリストの最初の要素は0番目とする。

scala> nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2


P04 (*) リストの要素の数を求めよ。

scala> length(List(1, 1, 2, 3, 5, 8))
res0: Int = 6


P05 (*) リストを逆順にせよ。

scala> reverse(List(1, 1, 2, 3, 5, 8))
res0: List[Int] = List(8, 5, 3, 2, 1, 1)


P06 (*) リストが回文になっているか調べよ。

scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true


P07 (**) ネストされたリスト構造を平坦化せよ。

scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)


P08 (**) リスト要素の連続した重複物を除去せよ。もしリストの要素で繰り返し要素が含まれていたならば要素一つに置き換えよ。要素の順序は変えてはならない。

scala> compress(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> pack(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 (*) リストをランレングス・エンコードせよ。P09の結果を用いていわゆるランレングス・エンコーディングによるデータ圧縮法を実装せよ。連続した重複要素はタプル(N,E)にエンコードされる。但しNは要素Eの重複数。

scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))


P11 (*) 修正ランレングス・エンコーディング。P10の結果を修正し、もし要素に重複が無ければ単に要素を結果にコピーせよ。重複している要素だけを(N,E)の形に変換せよ。

scala> encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))


P12 (**) ランレングス・エンコードされたリストをデコードせよ。P10の仕様で生成されたランレングス・エンコードされたリストを元の圧縮されていないものに戻せ。

scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)


P13 (**) リストのランレングス・エンコーディング（直接解法）。いわゆるランレングス・エンコーディングを直接実装せよ。すなわち（P09のpackの様な）自分で書いた他のメソッドを使ってはならない。直接書く事。

scala> encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))


P14 (*) リスト要素を重複させよ。

scala> duplicate(List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)


P15 (**) 指定した個数、リスト要素を重複させよ。

scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)


P16 (**) 毎N番目の要素を除去せよ。

scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)


P17 (*) リストを二つに分割せよ。前半の長さは与えられるものとする。結果はタプルで返す。

scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))


P18 (**) リストのスライスを抽出せよ。二つの添字 i と j が与えられたとき、スライスとは元のリストの i 番目の要素を含むが j 番目の要素を含まないリストである。要素は0番目から始まるとする。

scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g)


P19 (**) リストの要素をn個左ローテートせよ。

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 (*) リストのk番目の要素を除去せよ。除去されたリストと除去した要素をタプルで返せ。要素は0番目から始まるとする。

scala> removeAt(1, List('a, 'b, 'c, 'd))
res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)


P21 (*) リストの指定された場所に要素を追加せよ。

scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)


P22 (*) 与えられた範囲の整数のリストを作れ。

scala> range(4, 9)
res0: List[Int] = List(4, 5, 6, 7, 8, 9)


P23 (**) リストから指定された数だけ値をランダムに選択せよ。（ヒント：P20を使え）

scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res0: List[Symbol] = List('e, 'd, 'a)


P24 (*) ロト：1〜Mからn個の異なるランダムな値を選べ。

scala> lotto(6, 49)
res0: List[Int] = List(23, 1, 17, 33, 21, 37)


P25 (*) 要素のランダムな順列を作成せよ。（ヒント：P23を使え）

scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)


P26 (**) n要素数のリストからk個の異なるオブジェクトを取り出す組み合わせを生成せよ。12人から3人の委員会を作る方法は何通りだろうか？答えは C(12,3)=220通り（C(n,k）はよく知られた二項係数）である。数学者にとってはこれで十分であるが、我々は本当に全ての解を生成したい。

scala> combinations(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), ...


P27 (**) 集合の要素を、互いに素な部分集合に纏めよ。
a) 9人の人をそれぞれ2,3,4人の３グループに纏める方法は何通りか？全ての組み合わせを生成する関数を書け。

scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ...

b) 上の問題を一般化してグループの大きさのリストを与えるとグループのリストを与える様にせよ。グループメンバーの順列は求めていない、すなわち((Aldo,Beat),...)は((Beat,Aldo),...)と同じ解である。しかし、((Aldo,Beat),(Carla,David),...)は((Carla,David),(Aldo,Beat),...)と異なる解である。

scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), ...

この組み合わせ問題に関して知りたければ離散数学の良い本で「多項係数」について調べよ。
P28 (**) リストのリストを長さでソートせよ。
a) 要素がリストであるリストを考える。そのリストの要素を長さでソートする、すなわち短いリストを前に、長いリストを後にする。

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('d, 'e), List('m, 'n), List('a, 'b, 'c), List('f, 'g, 'h), List('i, 'j, 'k, 'l))

b) 次に同様にリストを長さでソートするが、今回は長さの頻度でソートする。すなわち稀な長さのものを前に、頻度の高い長さのものを後ろにする。例の場合、長さ４と１のリストはただ１度しか現れない。3番目と4番目は長さ3のリスト２つである。最後に３つの最も頻度の高い長さ２のリストが現れる。

scala> lsortFreq(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)))
res1: List[List[Symbol]] = List(List('i, 'j, 'k, 'l), List('o), List('a, 'b, 'c), List('f, 'g, 'h), List('d, 'e), List('d, 'e), List('m, 'n))


[Scala] Sudoku in Scala

Scalaユーザ会5/22(金)19：00-21：00@新宿三井ビル3で話をする予定の「Scalaで数独を解く」話です。

ScalaSudoku.pdf : プレゼン資料
Sudoku.scala : ソースコード

[Scala] Jersey with Scala + Jetty

Jersey は JAX-RS (Java API for RESTful Web Service)のreference実装です。
これをScalaで動かしてみます。

1. Libraries : Jetty 6.1.17. Jersey 1.0.3 を使用しました。下記をEclipseプロジェクトのreference librariesに登録

Jetty : jetty-XX.jar, jetty-util-XX.jar, servlet-api-XX.jar
Jersey : jsr311-api-XX.jar, jersey-core-XX.jar, jersey-server-XX.jar, asm-XX.jar

2. test.jersey.JerseyTest.scala : メインルーチンです

package test.jersey

import javax.servlet.ServletException
import javax.servlet.http.HttpServlet
import javax.servlet.http.HttpServletRequest
import javax.servlet.http.HttpServletResponse

import org.mortbay.jetty.Server
import org.mortbay.jetty.nio.SelectChannelConnector
import org.mortbay.jetty.servlet.Context
import org.mortbay.jetty.servlet.ServletHolder

import com.sun.jersey.spi.container.servlet.ServletContainer
  
object JerseyTest {
  def main(args: Array[String]) {
    val server = new Server(8080)
    val connector = new SelectChannelConnector()
    server.addConnector(connector)
    
    val holder:ServletHolder = new ServletHolder(classOf[ServletContainer])
    holder.setInitParameter(
      "com.sun.jersey.config.property.resourceConfigClass",
      "com.sun.jersey.api.core.PackagesResourceConfig")
    holder.setInitParameter(
      "com.sun.jersey.config.property.packages",
      "test.jersey.resource")
// URLをクラスにマッピングする為のpackage名

    val context = new Context(server, "/", Context.SESSIONS)
    context.addServlet(holder, "/*")
    
    server.start()
    server.join()
  }
}

3. test.jersey.resource : /helloworld に対応するリソース

package test.jersey.resource

import javax.ws.rs.GET
import javax.ws.rs.Produces
import javax.ws.rs.Path

@Path("/helloworld")
class HelloWorldResource {
  @GET
  @Produces(Array("text/plain"))
  def getMessage:String = "Hello, World"
}

4. テスト
Eclipseでtest.jersey.JerseyTest をアプリケーションとして実行させます。

2009-05-03 22:56:18.064::INFO:  Logging to STDERR via org.mortbay.log.StdErrLog
2009-05-03 22:56:18.123::INFO:  jetty-6.1.17
2009-05-03 22:56:18.205::INFO:  Started SocketConnector@0.0.0.0:8080
2009-05-03 22:56:18.226::INFO:  Started SelectChannelConnector@0.0.0.0:55736

次いでアクセス

% telnet localhost 8080
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
GET /helloworld HTTP/1.0

HTTP/1.1 200 OK
Content-Type: text/plain
Server: Jetty(6.1.17)

Hello, WorldConnection closed by foreign host.
% 

2009/05/03 22:57:08 com.sun.jersey.api.core.PackagesResourceConfig init
情報: Scanning for root resource and provider classes in the packages:
  test.jersey.resource
2009/05/03 22:57:08 com.sun.jersey.api.core.PackagesResourceConfig init
情報: Root resource classes found:
  class test.jersey.resource.HelloWorldResource
2009/05/03 22:57:08 com.sun.jersey.api.core.PackagesResourceConfig init
情報: Provider classes found:

[Scala] Scala Servlet with Jetty6

Jetty + ScalaでServletを書いてみました。

1. Projectの作成
Eclipseで普通にScala Projectを作ります。
ScalaServletという名前のScala Projectを作りました。

2. Jetty6 の入手
JettyのサイトからJetty6を入手します。私がダウンロードしたのはJetty 6.1.17でした。
zipを解凍し、jetty-6.1.17.jar, jetty-util-6.1.17.jar, servlet-api-2.5-20081211.jar をプロジェクトにimportします。

3. ソースを書く
パッケージtest.jettyを作って、下記の様なJettyTest.scalaというファイルを作成します

package test.jetty

import javax.servlet.ServletException
import javax.servlet.http.HttpServlet
import javax.servlet.http.HttpServletRequest
import javax.servlet.http.HttpServletResponse

import org.mortbay.jetty.Server
import org.mortbay.jetty.nio.SelectChannelConnector
import org.mortbay.jetty.servlet.ServletHandler

object JettyTest {

  def main(args: Array[String]) {
    val server = new Server(8080)
    val connector = new SelectChannelConnector()
    server.addConnector(connector)
    
    val handler = new ServletHandler()
    handler.addServletWithMapping(HelloServlet.getClass, "/")
    server.addHandler(handler)
  
    server.start()
    server.join()
  }
}

object HelloServlet extends HttpServlet {
  override def doGet(req:HttpServletRequest, resp:HttpServletResponse) {
    val out = resp.getWriter
    resp.setContentType("text/html")
    out.println("<html><body>Hello, World!</body></html>")
  }
}

4.サーバ起動
上記のJettyTest.scalaを普通にScala Applicationとして起動します。
コンソールに下記の様に表示されます。

2009-05-03 02:20:29.316::INFO:  Logging to STDERR via org.mortbay.log.StdErrLog
2009-05-03 02:20:29.358::INFO:  jetty-6.1.17
2009-05-03 02:20:29.392::INFO:  Started SocketConnector@0.0.0.0:8080
2009-05-03 02:20:29.413::INFO:  Started SelectChannelConnector@0.0.0.0:52134

5.アクセス
ブラウザからhttp://localhost:8080/で確認してもOKですがコンソールから確認。

% telnet localhost 8080
Trying ::1...
telnet: connect to address ::1: Connection refused
Trying fe80::1...
telnet: connect to address fe80::1: Connection refused
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
GET / HTTP/1.0

HTTP/1.1 200 OK
Content-Type: text/html; charset=iso-8859-1
Content-Length: 40
Server: Jetty(6.1.17)

<html><body>Hello, World!</body></html>
Connection closed by foreign host.
% 

[Scala] map and flatMap on scala.Function1

scala.Function1 lacking @ λ Tony’s blog λ

Scalaの関数の型の scala.Function1 にもっと便利な機能を、という話。
mapはともかくflatMapをこうやって定義するのか、というのはなんか勉強になったので、メモ代わりに。
同様に S combinator というのも自分ではなんか巧く使えないものなので参考になるなぁ、と。on は普通に便利かも。

[Misc] These days...

Project Eulerはその後も細々と解いてはいるのだが、いちいち解法をblogに書くのが面倒になって更新をさぼってました。あと１問でLevel 2なんだけどなー。

　あと、Scala勉強会＠関東2の準備が忙しかったりとか。仕事でのプレゼンは勿論あるけど、私的な勉強会でのプレゼンはこれが始めてで、なんていうか仕事とは別の緊張感がありますね。つまり仕事と違って、「実は自分は良く解ってなくて外しているんじゃないかしらん」みたいな不安とか。

そういえばそろそろReal World Haskellの発売ですね。東京近辺で興味がある人がいれば是非とも読書会とか検討しません？

[Project Euler] Problem 22

Problem 22

　この問題では、入力データをコードに直接貼付けず、ファイルから読み込むようにする必要がある。
　ファイルからデータをどう読み込むかだが、scala.io.Source.fromFile("filename").getLines で行単位で読み込めるイテレータを生成するので、それを使うのが楽だと思う。（本当はそういう目的のライブラリでは無い様にも思うのだが...。）
　names.txt がどこに置かれているのかというと、Eclipse上のプロジェクトProjectEuler下の、srcの下の、パッケージP020の下に、names.txtが置かれているので、filenameとしては"src/P020/names.txt"になった。

object P022 {
  def main(args:Array[String]) {
    val line:String = scala.io.Source.fromFile("src/P020/names.txt").getLines.next
    val names1:List[String] = line.split(",").map{s => s.substring(1, s.size-1)}.toList
    val names2:List[(String,Int)] = names1.sort{(a,b) => a.compareTo(b)<0}.zipWithIndex.map{t => (t._1, t._2+1)}
    println(names2.head) // (AARON,1)
    def f(t:Tuple2[String,Int]):Int = t match {
      case (s,i) => i * s.toCharArray.map{c => c-'A'+1}.foldLeft(0)(_+_)
    }
    println(f(names2.head)) // (AARON,1)
    println(names2.map(f).foldLeft(0)(_+_))
  }
}

[Project Euler] Problem 21

Problem 21

素数リストとかは過去の問題のを使い回し。

object P021 {
  val initPrimes:List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
                              31, 37, 41, 43, 47, 53, 59, 61, 67, 
                              71, 73, 79, 83, 89, 97, 101)
  def primes(init:List[Int]):List[Int] = {
    def min(a:Int, b:Int) = if (a<b) a else b
    def sq(a:Int) = a*a
    init ::: List.range(init.last+1, min(100000,sq(init.last))).filter{x => init.forall{x%_!=0}}
  }
  val primeList:List[Int] = primes(primes(initPrimes))
  def factors(n:Int):List[Tuple2[Int,Int]] = {
    def g(n:Int, p:Int, c:Int):Tuple2[Int,Int] = if (n%p==0) g(n/p, p, c+1) else Tuple2(n,c)
    def f(n:Int, ps:List[Int], ts:List[Tuple2[Int,Int]]):List[Tuple2[Int,Int]] = (n,ps) match {
      case (1,_) => ts
      case (_,Nil) => error("n="+n)
      case (_, a::as) if n%a==0 => {
        val z = g(n,a,0)
        f(z._1, as, Tuple2(a,z._2)::ts)
      }
      case (_, a::as) => f(n, as, ts)
    }
    f(n, primeList, Nil)
  }
  def sumDiv(ts:List[Tuple2[Int,Int]]):Int = {
    def pow(a:Int, b:Int):Int = b match {
      case 0 => 1
      case _ => pow(a,b-1)*a
    } 
    def f(t:Tuple2[Int,Int]):Int = {
      List.range(0, t._2 +1).map{pow(t._1, _)}.foldLeft(0)(_+_)
    }
    ts.map(f).foldLeft(1)(_*_)
  }
  def sumDivisors(n:Int):Int = sumDiv(factors(n))-n
  def main(args:Array[String]) {
    println(sumDivisors(220))
    println(sumDivisors(284))
    val l = List.range(2,10000).filter{a => {
      val b=sumDivisors(a)
      val c=sumDivisors(b)
      val r=(a!=b)&&(a==c)
      if (r) println(a+"<->"+b)
      r
    }}
    println(l)
    println(l.foldLeft(0)(_+_))
  }
}

---
　ここまでProject Eulerを解いてきて思ったのだが、組み込みライブラリとか言語仕様で、

• アノテーションを付けるだけで関数の値をメモ化してくれる。
  
• とりあえず1,000,000以下の素数は予め計算されている。
  
• 内部でIntの計算が桁溢れしたら勝手にLong -> BigInt と桁を増やしてくれるような数値型。
  
• 素因数分解も組み込み関数で用意されている。
  

とかだと、かなり楽が出来るのになぁ...。