Scalaユーザ会5/22(金)19:00-21:00@新宿三井ビル3で話をする予定の「Scalaで数独を解く」話です。
ScalaSudoku.pdf : プレゼン資料
Sudoku.scala : ソースコード
Personal memorandum for studying functional languages, theorem proving, and formal verification. But other topics might be included. Written in Japanese (Shift-JIS Encoding).
22 May, 2009
20 May, 2009
[Joke] Translation of "A Brief, Incomplete, and Mostly Wrong History of Programming Languages"
A Brief, Incomplete, and Mostly Wrong History of Programming Languagesの翻訳です。面白かったので翻訳してみました。
「簡潔で不完全でほとんど間違っているプログラミング言語の歴史」
1801 - Joseph Marie Jacquardが、織機にパンチカードで命令することで、タペストリーに「hello, world」を織り込んだ。(しかし)末尾再帰やコンカレンシーの欠如、あるいは適切に大文字が使用されていないため、当時のRedditerたちは感銘を覚え無かった。
1842 - Ada Lovelaceが最初のプログラムを書いた。その過程に於いて、コードを走らせる実際のコンピュータを持っていないという些細な困難に妨げられた。後のエンタープライズアーキテクトたちは、UMLでプログラムする為に、彼女のテクニックを再習得した。
1936 - Alan Turingが、(将来に亘る)全てのプログラミング言語を発明した。しかし彼がその特許をとる前に、英国情報部は彼を007にするために強制徴募した。
1936 - Alonzo Churchもまた、(将来に亘る)全てのプログラミング言語をさらにうまく発明した。彼のλ算法はC言語に十分似ていない為に無視された。この批判は、当時まだCが発明されていないという事実にも関わらず生じた。
1940年代 - 結線とスイッチによって様々な「コンピュータ」が「プログラム」された。「タブ vs 空白」の論戦を避けるために、技術者たちはこの方式を採用した。
1957 - John BackusとIBMがFORTRANを作った。IBMにもFORTRANにも面白いところは何も無い。青いネクタイを着用せずFORTRANを書くのは文法エラーである。
1958 - John McCarthyとPaul GrahamがLISPを発明する。戦後の戦略的括弧備蓄の枯渇による高コストの為、LISPは決してポピュラーにはならなかった[1]。ポピュラーでは無いにも関わらず、LISP (今では "Lisp" あるいは時には "Arc") は「再帰と他人を見下すことなどの重要なアルゴリズム技法」に於ける影響度の高い言語であり続けている。
1959 - L. Ron Hubbardとの賭けに負けた後に、Grace Hopperを含む何人かのサディスト達が「大文字化された定型文志向言語」 (Capitalization Of Boilerplate Oriented Language = COBOL) を発明する。後に、Hooper提督のCOBOLの業績に対する見当外れで性差別的な報復として、Rubyコンファレンスでは嫌女性的題材が取り上げられる。
1964 - John KemenyとThomas Kurtzが、非計算機科学者の為の非構造化プログラミング言語であるBASICを作った。
1965 - KemenyとKurtzはGO TO 1964.
1970 - Guy SteeleとGerald SussmanがSchemeを作った。彼らの著作は「Lambda the Ultimate」の一連の論文をもたらし、「究極の台所用品ラムダ」にその頂点を迎えた。この論文はロングランの基礎となったが、深夜のインフォマーシャルとしては究極的に失敗であった。Javaがラムダを持たないことによってラムダをポピュラーにするまでラムダは比較的目立たないところへと左遷された。
1970 - Niklaus Wirthが手続き型言語のPascalを作った。Pascalは直ちに批難されたが、"x := x + y"という構文を、より親しみやすいC的な"x = x + y"の代わりに使用したためであった。この批判は、当時まだCが発明されていないという事実にも関わらず生じた。
1972 - Dennis Ritchieは前後を同時に撃つことの出来る強力な銃を発明した。発明のもたらした多くの死者及び障害者に満足することなく、彼はCとUnixを発明した。
1972 - Alain Colmerauerは論理型言語Prologをデザインした。彼の目標は二歳児の知性を持った言語を作ることであった。全てのクエリに「No」と答えるPrologセッションを示すことによって、目標に達したことを証明した。
1973 - Robin MilnerはM&M型理論に基づく言語のMLを作った。MLの子供として形式仕様意味論を持つSMLが生まれた。形式意味論の形式意味論を質問されてMilnerの頭は爆発した。ML一家の他の良く知られた言語にはOCaml, F#, Visual Basicがある。
1980 - Alan kayはSmalltalkを作り、用語「オブジェクト指向」を発明した。その意味を聞かれると彼は「Smalltalkのプログラムは単にオブジェクトである」と答えた。オブジェクトは何から作られるのかを聞かれると彼は「オブジェクトだ」と答えた。再度質問されると彼は云った。「だからさ、下の下まで全部オブジェクトなんだってば。亀にたどり着くまでは。」
1983 - Bjarne Stroustrupは耳にしたもの全てをCにねじ止めすることでC++を作った。その結果、言語は非常に複雑になり、プログラムをSkynet人工知能でコンパイルするために未来へ送らねばならなかった。ビルド時間は犠牲となった。Skynetがサービスを提供し続けた動機は依然としてはっきりしないが、未来からの広報担当はオーストリア訛りで単調に「気にするようなことは何も無い、ベイビー」と云った。Skynetはバッファーオーバーランを飾り立てたものに過ぎないという推測もある。
1986 - Brad CoxとTom LoveがObjective-Cを作り、アナウンスした。「この言語はCのメモリ安全性とSmalltalkの素晴らしい実行速度が結びついたものです。」現代の歴史家たちは二人が失読症であったと疑っている。
1987 - Larry Wallが眠気を催し、キーボードに額をぶつけた。目を覚ましたとき、Larry Wallのモニターの上の文字列はランダムなのではなく、神が預言者Larry Wallにデザインすることを欲しているプログラミング言語のサンプルプログラムだと悟った。Perlが生まれた。
1990 - Simon Peyton-Jones, Paul Hudak, Philip Wadler, Ashton Kutcher そして「動物の倫理的扱いを求める人々の会」からなる委員会は、純粋非正格関数型言語Haskell を作った。副作用を制御するためモナドを使用する複雑さの為、Haskellは抵抗を受けた。Wadler は批判を和らげるために説明した。「モナドは自己準同系ファンクタの圏のモノイドなんだ。何か問題が?」
1991 - オランダ人プログラマのGuido van Rossumが謎の手術の為にアルゼンチンへと旅行した。頭部に大きな傷を負って帰国し、Pythonを発明し、多数の賛同者によって終身独裁者に任じられ、世界に対して「あることをするのにひとつしかやり方がない」と報じた。ポーランドは神経質になっている。
1995 - 「Mad Matz」こと、まつもとゆきひろは、漠然とした特定されない終末を避けるためにRubyを作ったが、その終末においてはオーストラリアはモヒカン戦士とティナ=ターナーが支配する砂漠となる。その言語は後にRuby on Railsと、真の発明者David Heinemeier Hanssonによって改名された。[まつもとがRubyと呼ばれる言語を発明した云々は実際には起きておらず、この記事の次の改訂時に削除されるべきだ - DHH].
1995 - Brendan Eichはプログラミング言語設計で起きた全ての失敗について読み、自分でも幾つか発明し、LiveScriptを作成した。後にその言語は、Javaの人気に肖る為、JavaScriptと改名された。後になっても、皮膚病の人気に肖る為にECMAScriptと改名された。
1996 - James GoslingはJavaを発明した。Javaは比較的冗長で、ガベージコレクションをし、クラスベースで、静的型付けで、シングルディスパッチで、単一実装継承と複数インタフェース継承のオブジェクト指向な言語である。SunはJavaの新規性を宣伝した。
2001 - Anders HejlsbergがC#を発明した。C#は比較的冗長で、ガベージコレクションをし、クラスベースで、静的型付けで、シングルディスパッチで、単一実装継承と複数インタフェース継承のオブジェクト指向の言語である。MicrosoftはC#の新規性を宣伝した。
2003 - 酔っ払ったMartin Oderskyは誰かのピーナツバターが別の人のチョコレートにくっつくというReeseのピーナツバターカップのCMを見て着想を得た。彼はオブジェクト指向と関数型言語の作り上げたものを統合する言語Scalaを作った。これを見た両派閥とも激怒し、それぞれ直ちに聖戦を宣告した。
Footnotes
1. 計算機科学にとっては幸運なことに、中括弧と山括弧の供給は潤沢であった。
2. Catch as catch can - Verity Stob
「簡潔で不完全でほとんど間違っているプログラミング言語の歴史」
1801 - Joseph Marie Jacquardが、織機にパンチカードで命令することで、タペストリーに「hello, world」を織り込んだ。(しかし)末尾再帰やコンカレンシーの欠如、あるいは適切に大文字が使用されていないため、当時のRedditerたちは感銘を覚え無かった。
1842 - Ada Lovelaceが最初のプログラムを書いた。その過程に於いて、コードを走らせる実際のコンピュータを持っていないという些細な困難に妨げられた。後のエンタープライズアーキテクトたちは、UMLでプログラムする為に、彼女のテクニックを再習得した。
1936 - Alan Turingが、(将来に亘る)全てのプログラミング言語を発明した。しかし彼がその特許をとる前に、英国情報部は彼を007にするために強制徴募した。
1936 - Alonzo Churchもまた、(将来に亘る)全てのプログラミング言語をさらにうまく発明した。彼のλ算法はC言語に十分似ていない為に無視された。この批判は、当時まだCが発明されていないという事実にも関わらず生じた。
1940年代 - 結線とスイッチによって様々な「コンピュータ」が「プログラム」された。「タブ vs 空白」の論戦を避けるために、技術者たちはこの方式を採用した。
1957 - John BackusとIBMがFORTRANを作った。IBMにもFORTRANにも面白いところは何も無い。青いネクタイを着用せずFORTRANを書くのは文法エラーである。
1958 - John McCarthyとPaul GrahamがLISPを発明する。戦後の戦略的括弧備蓄の枯渇による高コストの為、LISPは決してポピュラーにはならなかった[1]。ポピュラーでは無いにも関わらず、LISP (今では "Lisp" あるいは時には "Arc") は「再帰と他人を見下すことなどの重要なアルゴリズム技法」に於ける影響度の高い言語であり続けている。
1959 - L. Ron Hubbardとの賭けに負けた後に、Grace Hopperを含む何人かのサディスト達が「大文字化された定型文志向言語」 (Capitalization Of Boilerplate Oriented Language = COBOL) を発明する。後に、Hooper提督のCOBOLの業績に対する見当外れで性差別的な報復として、Rubyコンファレンスでは嫌女性的題材が取り上げられる。
1964 - John KemenyとThomas Kurtzが、非計算機科学者の為の非構造化プログラミング言語であるBASICを作った。
1965 - KemenyとKurtzはGO TO 1964.
1970 - Guy SteeleとGerald SussmanがSchemeを作った。彼らの著作は「Lambda the Ultimate」の一連の論文をもたらし、「究極の台所用品ラムダ」にその頂点を迎えた。この論文はロングランの基礎となったが、深夜のインフォマーシャルとしては究極的に失敗であった。Javaがラムダを持たないことによってラムダをポピュラーにするまでラムダは比較的目立たないところへと左遷された。
1970 - Niklaus Wirthが手続き型言語のPascalを作った。Pascalは直ちに批難されたが、"x := x + y"という構文を、より親しみやすいC的な"x = x + y"の代わりに使用したためであった。この批判は、当時まだCが発明されていないという事実にも関わらず生じた。
1972 - Dennis Ritchieは前後を同時に撃つことの出来る強力な銃を発明した。発明のもたらした多くの死者及び障害者に満足することなく、彼はCとUnixを発明した。
1972 - Alain Colmerauerは論理型言語Prologをデザインした。彼の目標は二歳児の知性を持った言語を作ることであった。全てのクエリに「No」と答えるPrologセッションを示すことによって、目標に達したことを証明した。
1973 - Robin MilnerはM&M型理論に基づく言語のMLを作った。MLの子供として形式仕様意味論を持つSMLが生まれた。形式意味論の形式意味論を質問されてMilnerの頭は爆発した。ML一家の他の良く知られた言語にはOCaml, F#, Visual Basicがある。
1980 - Alan kayはSmalltalkを作り、用語「オブジェクト指向」を発明した。その意味を聞かれると彼は「Smalltalkのプログラムは単にオブジェクトである」と答えた。オブジェクトは何から作られるのかを聞かれると彼は「オブジェクトだ」と答えた。再度質問されると彼は云った。「だからさ、下の下まで全部オブジェクトなんだってば。亀にたどり着くまでは。」
1983 - Bjarne Stroustrupは耳にしたもの全てをCにねじ止めすることでC++を作った。その結果、言語は非常に複雑になり、プログラムをSkynet人工知能でコンパイルするために未来へ送らねばならなかった。ビルド時間は犠牲となった。Skynetがサービスを提供し続けた動機は依然としてはっきりしないが、未来からの広報担当はオーストリア訛りで単調に「気にするようなことは何も無い、ベイビー」と云った。Skynetはバッファーオーバーランを飾り立てたものに過ぎないという推測もある。
1986 - Brad CoxとTom LoveがObjective-Cを作り、アナウンスした。「この言語はCのメモリ安全性とSmalltalkの素晴らしい実行速度が結びついたものです。」現代の歴史家たちは二人が失読症であったと疑っている。
1987 - Larry Wallが眠気を催し、キーボードに額をぶつけた。目を覚ましたとき、Larry Wallのモニターの上の文字列はランダムなのではなく、神が預言者Larry Wallにデザインすることを欲しているプログラミング言語のサンプルプログラムだと悟った。Perlが生まれた。
1990 - Simon Peyton-Jones, Paul Hudak, Philip Wadler, Ashton Kutcher そして「動物の倫理的扱いを求める人々の会」からなる委員会は、純粋非正格関数型言語Haskell を作った。副作用を制御するためモナドを使用する複雑さの為、Haskellは抵抗を受けた。Wadler は批判を和らげるために説明した。「モナドは自己準同系ファンクタの圏のモノイドなんだ。何か問題が?」
1991 - オランダ人プログラマのGuido van Rossumが謎の手術の為にアルゼンチンへと旅行した。頭部に大きな傷を負って帰国し、Pythonを発明し、多数の賛同者によって終身独裁者に任じられ、世界に対して「あることをするのにひとつしかやり方がない」と報じた。ポーランドは神経質になっている。
1995 - 「Mad Matz」こと、まつもとゆきひろは、漠然とした特定されない終末を避けるためにRubyを作ったが、その終末においてはオーストラリアはモヒカン戦士とティナ=ターナーが支配する砂漠となる。その言語は後にRuby on Railsと、真の発明者David Heinemeier Hanssonによって改名された。[まつもとがRubyと呼ばれる言語を発明した云々は実際には起きておらず、この記事の次の改訂時に削除されるべきだ - DHH].
1995 - Brendan Eichはプログラミング言語設計で起きた全ての失敗について読み、自分でも幾つか発明し、LiveScriptを作成した。後にその言語は、Javaの人気に肖る為、JavaScriptと改名された。後になっても、皮膚病の人気に肖る為にECMAScriptと改名された。
1996 - James GoslingはJavaを発明した。Javaは比較的冗長で、ガベージコレクションをし、クラスベースで、静的型付けで、シングルディスパッチで、単一実装継承と複数インタフェース継承のオブジェクト指向な言語である。SunはJavaの新規性を宣伝した。
2001 - Anders HejlsbergがC#を発明した。C#は比較的冗長で、ガベージコレクションをし、クラスベースで、静的型付けで、シングルディスパッチで、単一実装継承と複数インタフェース継承のオブジェクト指向の言語である。MicrosoftはC#の新規性を宣伝した。
2003 - 酔っ払ったMartin Oderskyは誰かのピーナツバターが別の人のチョコレートにくっつくというReeseのピーナツバターカップのCMを見て着想を得た。彼はオブジェクト指向と関数型言語の作り上げたものを統合する言語Scalaを作った。これを見た両派閥とも激怒し、それぞれ直ちに聖戦を宣告した。
Footnotes
1. 計算機科学にとっては幸運なことに、中括弧と山括弧の供給は潤沢であった。
2. Catch as catch can - Verity Stob
03 May, 2009
[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 : メインルーチンです
3. test.jersey.resource : /helloworld に対応するリソース
4. テスト
Eclipseでtest.jersey.JerseyTest をアプリケーションとして実行させます。
次いでアクセス
これを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というファイルを作成します
4.サーバ起動
上記のJettyTest.scalaを普通にScala Applicationとして起動します。
コンソールに下記の様に表示されます。
5.アクセス
ブラウザからhttp://localhost:8080/で確認してもOKですがコンソールから確認。
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.
%
18 April, 2009
[Event] Type-Level Programming Meeting
型レベルプログラミングの会
定員がすぐいっぱいになってしまって会場参加は出来ず、自宅からustreamで拝聴。
発表された皆さん、どれも興味深い話でした。ありがとうございます。
この手の勉強会に参加すると、今まで知らなかったことがいっぱいあると判り、もっと勉強しなくちゃ、と思う。
日々の仕事は非技術的な作業ばかりが増えているので、知的好奇心の刺激の為にもこの手の勉強会に積極的に参加しないと。
定員がすぐいっぱいになってしまって会場参加は出来ず、自宅からustreamで拝聴。
発表された皆さん、どれも興味深い話でした。ありがとうございます。
- Scala : Scalaの型プログラミングの話は前にも聞かせて頂いたような気がするけど、更に話題が広がっていたような。
- C++ : 定番ではありながら、私はC++は経験が少ないので興味深く聞けました。
- Haskell : フォロー出来ない話も多かったですが勉強になりました。勉強すべき事、多いなぁ。
- D : 型プログラミングの為のような言語ですね。興味深い。
- 依存型プログラミング : プレゼン資料が大変面白いというか芸達者というか。April Foolの予告のGirardの逆理の話では無かった。
- G'Caml : 存在を始めて知りました。OCaml関係も色々あるなぁ。
この手の勉強会に参加すると、今まで知らなかったことがいっぱいあると判り、もっと勉強しなくちゃ、と思う。
日々の仕事は非技術的な作業ばかりが増えているので、知的好奇心の刺激の為にもこの手の勉強会に積極的に参加しないと。
05 April, 2009
[Coq] Coq'Art Chap.2
Interactive Theorem Proving and Program Development; Coq'Art: The Calculus of Inductive Constructions の Chapter 2 です。
この章では概ね次の4つが語られているように見えます。
(1) Coq のコマンド
下記の様なコマンドがあります。
★
ライブラリをロードして environment に追加する。
libraryとしては、
★
Scope は notation を interprete する規則。例えば
★
Scopeで定義された notation の一覧を得る。
★
termのtypeを表示させる。
★
t:Aを environment に追加する。environmentはglobalなもの。
★
localなblockを作る。
★
t:Aを context に追加する。contextはlocal。なので、
(2) Inference Rules
様々な推論規則があります。
(3) Eval
★cvb : call-by-value (cbvでなくlazyで遅延評価)
★delta-reduction : t ==> t{v/t'}。tのidentifier vをその定義t'で置換。
★beta-reduction : (fun v:T => e_1) e2 ==> e_1{v/e_2}。λ式を簡約。
★zeta-reduction : let v := e_1 in e_2 ==> e_2{v/e_1}。letを簡約。
★iota-reduction : 帰納的な処理で詳しくはChap.6でということで後回し。nat,Zは帰納的な定義なので計算する時はiota-reductionが必須。
★compute = cvb iota beta zeta delta の略
★
Reductionに関する性質
(4) Universe
typeもtermだとすると、typeのtypeがあるはず。それをsortという。
CoqではSetというデフォルトのsortが定義されている。
更にその上の無限の階層まで考えるようだが、CoqではType(i)は全部ひっくるめてTypeにしてしまう様子。
この章では概ね次の4つが語られているように見えます。
(1) Coq のコマンド
下記の様なコマンドがあります。
★
Require Import library.ライブラリをロードして environment に追加する。
libraryとしては、
Arith, ZArith, Boolなどがある。★
Open Scope scope名.Scope は notation を interprete する規則。例えば
Z_scopeを指定すると各種演算子記号が Z の演算のものと判断される。★
Print Scope scope名.Scopeで定義された notation の一覧を得る。
★
Check term.termのtypeを表示させる。
★
Parameter t:A.t:Aを environment に追加する。environmentはglobalなもの。
★
Section id....
End id.localなblockを作る。
★
Variable t:A.t:Aを context に追加する。contextはlocal。なので、
Section...Endの範囲内で有効。(2) Inference Rules
様々な推論規則があります。
(x,A)∈E∪Γ
Var ------------ x:identifier
E,Γ |- x:A
E,Γ|- e_1:A->B E,Γ|- e_2:A
App ------------------------------ 関数適用
E,Γ|- e_1 e_2:B
E,Γ|- e:A_1 -> A_2 -> ... -> A_n -> B E,Γ|- e_i:A_i (i=1,...,n)
App* -------------------------------------------------------------------
E,Γ|- e e_1 ... e_n:B
E,Γ|- t_1:A E,Γ::(v:=t_1) |- t_2:B
Lam -------------------------------------- λ式
E,Γ|- fun v:A => e:A->B
E,Γ|- t_1:A E,Γ::(v:=t_1) |- t_2:B
Let-in -------------------------------------- let
E,Γ|- let v:=t_1 in t_2:B
E,Γ|- A:Set E,Γ|- B:Set
Prod-Set --------------------------
E,Γ|- A->B:Set
E,Γ|- t:A E,Γ|- A ≦_{beta delta iota zeta} B
Conv --------------------------
E,Γ|- t:B
(3) Eval
★cvb : call-by-value (cbvでなくlazyで遅延評価)
★delta-reduction : t ==> t{v/t'}。tのidentifier vをその定義t'で置換。
★beta-reduction : (fun v:T => e_1) e2 ==> e_1{v/e_2}。λ式を簡約。
★zeta-reduction : let v := e_1 in e_2 ==> e_2{v/e_1}。letを簡約。
★iota-reduction : 帰納的な処理で詳しくはChap.6でということで後回し。nat,Zは帰納的な定義なので計算する時はiota-reductionが必須。
★compute = cvb iota beta zeta delta の略
★
Eval compute in (....). : ...を実際に計算する。Reductionに関する性質
- strong normalization : reductionはfinite
- confluence : t |> t_1, t |> t_2 ならば、あるt_3があって、t_1 |> t_3 かつ t_2 |> t_3。
(4) Universe
typeもtermだとすると、typeのtypeがあるはず。それをsortという。
CoqではSetというデフォルトのsortが定義されている。
更にその上の無限の階層まで考えるようだが、CoqではType(i)は全部ひっくるめてTypeにしてしまう様子。
Level 0 : 具体的な項とか関数。O, S, trinomial,...
Level 1 : データの型。nat, nat->nat, ...
Level 2 : ソート。Set
Level 3 : Type(0)
:
29 March, 2009
[Coq] Coq'Art Reading in Tokyo ?
ところで東京近辺でSpringerのCoq本Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructionsに興味のある人っています?
何人かいるようならば読書会でもとか思うのですが。なお、私は素人で型理論の専門家とかではありません。なので他人に教える程の知識は無く、一緒に勉強する感じになってしまいますが。
逆に既に本を読んでいるとかで、私が参加しても構わないグループとかありましたら声をかけて下さい。
何人かいるようならば読書会でもとか思うのですが。なお、私は素人で型理論の専門家とかではありません。なので他人に教える程の知識は無く、一緒に勉強する感じになってしまいますが。
逆に既に本を読んでいるとかで、私が参加しても構わないグループとかありましたら声をかけて下さい。
[Coq] Coq'Art Chap.1
Interactive Theorem Proving and Program Development; Coq'Art: The Calculus of Inductive Constructionsを読み始める事にしました。
Chap.1ではinsertion sortを例にしてCoqの解説が行われています。そこで、Appendixのinsertion sortのコードをCoqIdeに入力してみました。実際に証明が自分で出来る様になるのは将来の課題として、とりあえずCoqでの開発の流れを追ってみます。
なお証明自体はinsertionv8.vにあります。
まず、list Zがソートされた状態を定義する
これを用いて、
次いで、並べ替えであることを示す
これを使って、
次いで、実際にinsertion sortを行う関数
最後に、
証明を追いきれてないのですが、どうも
----
一般的に
----
ある程度、この本を読み終わった後で、またこのプログラムを振り返ってみたいと思います。
Chap.1ではinsertion sortを例にしてCoqの解説が行われています。そこで、Appendixのinsertion sortのコードをCoqIdeに入力してみました。実際に証明が自分で出来る様になるのは将来の課題として、とりあえずCoqでの開発の流れを追ってみます。
なお証明自体はinsertionv8.vにあります。
まず、list Zがソートされた状態を定義する
sorted : list Z -> Propを定義します。こんな感じです。
Inductive sorted : list Z -> Prop :=
| sorted0 : sorted nil
| sorted1 : forall z:Z, sorted (z :: nil)
| sorted2 : forall (z1 z2:Z) (l:list Z),
z1 <= z2 -> sorted (z2 :: l) -> sorted (z1 :: z2 :: l).
sortedは定義なのでこれ自体は証明の対象ではありません。これを用いて、
を証明します。
Theorem sorted_inv :
forall (z:Z) (l:list Z), sorted (z :: l) -> sorted l.
次いで、並べ替えであることを示す
equivを定義します。まず、リストのなかの出現数を示すを定義します。この
Fixpoint nb_occ (z:Z) (l:list Z) {struct l} : nat :=
match l with
| nil => 0%nat
| (z' :: l') =>
match Z_eq_dec z z' with
| left _ => S (nb_occ z l')
| right _ => nb_occ z l'
end
end.
nb_occは定義なので証明しません。これを使って、
を定義します。これ自体も証明しません。
Definition equiv (l l':list Z) := forall z:Z, nb_occ z l = nb_occ z l'
nb_occ, equivの定義から、下記の補題を証明します。
Lemma equiv_refl :
forall l:list Z, equiv l l.
Lemma equiv_sym :
forall l l':list Z, equiv l l' -> equiv l' l.
Lemma equiv_trans :
forall l l' l'':list Z, equiv l l' -> equiv l' l'' -> equiv l l''.
Lemma equiv_cons :
forall (z:Z) (l l':list Z), equiv l l' -> equiv (z :: l) (z :: l').
Lemma equiv_perm :
forall (a b:Z) (l l':list Z), equiv l l' -> equiv (a :: b :: l) (b :: a :: l').
次いで、実際にinsertion sortを行う関数
aux : Z -> list Z -> list Zを定義します。
Fixpoint aux (z:Z) (l:list Z) {struct l} : list Z :=
match l with
| nil => z :: nil
| cons a l' =>
match Z_le_gt_dec z a with
| left _ => z :: a :: l'
| right _ => a :: (aux z l')
end
end.
auxがinsertion sortの性質を持っている事を示す補題、つまりauxの結果がequivであること、sortedであることを証明します。
Lemma aux_equiv :
forall (l:list Z) (x:Z), equiv (x :: l) (aux x l).
Lemma aux_sorted :
forall (l:list Z) (x:Z), sorted l -> sorted (aux x l).
最後に、
sort:list Z -> list Zを定義というか、sortされた出力の存在を証明します。
Definition sort : forall l:list Z, {l' : list Z | equiv l l' /\ sorted l'}.
証明を追いきれてないのですが、どうも
exists (aux a l')の様に、実例を示して存在を証明するみたいにauxを使っているようです。----
sorted, nb_occ, equivは定義なので証明の対象ではありません。aux, sortは成果物として得る、証明済みのプログラムです。sortを満たす具体的なl'の値としてauxを使った式を与えます。その値がl'の条件を満たす事はaux_equiv, aux_sortedから保証されます。一般的に
- 仕様を表す様な述語(X -> Prop)を書く。仕様に関する補題も証明しておく。
- 解を与える様な関数を書く。
- その関数の出力が仕様を満たす事を証明する。
----
ある程度、この本を読み終わった後で、またこのプログラムを振り返ってみたいと思います。
27 December, 2008
[Haskell][RWH] Chapter 1
RWHのChapter 1を読む。
簡単にHaskellのプログラムを書くにはinteractを使えば良いらしい。
main = interact f 但し、fはString -> Stringな関数。これで標準入力から読んで標準出力に書けば良い。
実行は
Exerciseはとりあえずこんな感じ?
- not equalは
!=ではなく/=。 - temporary definitionを
letで。例えば、ghci> let e = exp 1とか。 ghci> :info []とかすれば、[]の情報が調べられる。ghci> :set +tで型情報を表示する。解除は:unset +t。:type itでunsetしても簡単に調べられる。itで前の計算結果を参照出来る。
簡単にHaskellのプログラムを書くにはinteractを使えば良いらしい。
main = interact f 但し、fはString -> Stringな関数。これで標準入力から読んで標準出力に書けば良い。
% cat WC.hs
main = interact wordCount
where wordCount input = show (length (lines input)) + "\n"
%
Prelude> :info interact
interact :: (String -> String) -> IO () -- Defined in System.IO
実行は
% runghc WC.hs < quux.txtExerciseはとりあえずこんな感じ?
main = interact wordCount
where wordCount input = numLines input ++ "\t" ++ numWords input ++ "\t" ++ numChars input ++ "\n"
numLines input = show (length (lines input))
numWords input = show (length (words input))
numChars input = show (length input)
04 December, 2008
[Scala] map and flatMap on scala.Function1
scala.Function1 lacking @ λ Tony’s blog λ
Scalaの関数の型の scala.Function1 にもっと便利な機能を、という話。
mapはともかくflatMapをこうやって定義するのか、というのはなんか勉強になったので、メモ代わりに。
同様に S combinator というのも自分ではなんか巧く使えないものなので参考になるなぁ、と。on は普通に便利かも。
Scalaの関数の型の scala.Function1 にもっと便利な機能を、という話。
mapはともかくflatMapをこうやって定義するのか、というのはなんか勉強になったので、メモ代わりに。
同様に S combinator というのも自分ではなんか巧く使えないものなので参考になるなぁ、と。on は普通に便利かも。
[Misc] These days...
Project Eulerはその後も細々と解いてはいるのだが、いちいち解法をblogに書くのが面倒になって更新をさぼってました。あと1問でLevel 2なんだけどなー。
あと、Scala勉強会@関東2の準備が忙しかったりとか。仕事でのプレゼンは勿論あるけど、私的な勉強会でのプレゼンはこれが始めてで、なんていうか仕事とは別の緊張感がありますね。つまり仕事と違って、「実は自分は良く解ってなくて外しているんじゃないかしらん」みたいな不安とか。
そういえばそろそろReal World Haskellの発売ですね。東京近辺で興味がある人がいれば是非とも読書会とか検討しません?
あと、Scala勉強会@関東2の準備が忙しかったりとか。仕事でのプレゼンは勿論あるけど、私的な勉強会でのプレゼンはこれが始めてで、なんていうか仕事とは別の緊張感がありますね。つまり仕事と違って、「実は自分は良く解ってなくて外しているんじゃないかしらん」みたいな不安とか。
そういえばそろそろReal World Haskellの発売ですね。東京近辺で興味がある人がいれば是非とも読書会とか検討しません?
ラベル:
Project euler,
scala
20 October, 2008
[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"になった。
この問題では、入力データをコードに直接貼付けず、ファイルから読み込むようにする必要がある。
ファイルからデータをどう読み込むかだが、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,
scala
[Project Euler] Problem 21
Problem 21
素数リストとかは過去の問題のを使い回し。
---
ここまでProject Eulerを解いてきて思ったのだが、組み込みライブラリとか言語仕様で、
素数リストとかは過去の問題のを使い回し。
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 と桁を増やしてくれるような数値型。
- 素因数分解も組み込み関数で用意されている。
ラベル:
Project euler,
scala
19 October, 2008
[Project Euler] Problem 20
Problem 20
BigIntegerを使うだけ。
BigIntegerを使うだけ。
object P020 {
def main(args:Array[String]) {
def fact(n:Int):BigInt = n match {
case 0 => new BigInt(java.math.BigInteger.ONE)
case _ => new BigInt(java.math.BigInteger.valueOf(n))*fact(n-1)
}
val r = fact(100).toString.toCharArray.map{c => c-'0'}.foldLeft(0)(_+_)
println(r)
}
}
ラベル:
Project euler,
scala
[Project Euler] Problem 19
Problem 19
難しくは無いはずなんだが、1900を1990と入力していたtypoの為でなかなか正解に辿り着けなかった。
難しくは無いはずなんだが、1900を1990と入力していたtypoの為でなかなか正解に辿り着けなかった。
object P019 {
def isLeap(y:Int):Boolean = y match {
case _ if y%400==0 => true
case _ if y%100==0 => false
case _ if y%4==0 => true
case _ => false
}
def daysOfMonth(y:Int, m:Int):Int = m match {
case 9 => 30
case 4 => 30
case 6 => 30
case 11 => 30
case 2 => if (isLeap(y)) 29 else 28
case _ => 31
}
def daysInYear(y:Int):Int = if (isLeap(y)) 366 else 365
def daysFrom1Jan1900(year:Int, month:Int, day:Int):Int =
List.range(1900,year).map{y => daysInYear(y)}.foldLeft(0)(_+_) +
List.range(1,month).map{m => daysOfMonth(year,m)}.foldLeft(0)(_+_) +
(day-1)
val day0Jan1900:Int = daysFrom1Jan1900(1900,1,0) // Sunday
def dayOfTheWeek(year:Int, month:Int, day:Int):Int = (daysFrom1Jan1900(year,month,day)-day0Jan1900)%7
def main(args:Array[String]) {
println(dayOfTheWeek(1901,1,1))
println(dayOfTheWeek(2000,12,1))
println(
(for(y <- List.range(1901,2001); m <- List.range(1,13))
yield dayOfTheWeek(y,m,1)).filter{_==0}.size)
}
}
ラベル:
Project euler,
scala
[Project Euler] Problem 18
Problem 18
n段目では、(n-1)段目で左右を選ぶ選択で大きな方を選ぶ、というのを再帰的にやれば良いが、計算時間を減らす為に、Problem 15と同様にメモ化する。
n段目では、(n-1)段目で左右を選ぶ選択で大きな方を選ぶ、というのを再帰的にやれば良いが、計算時間を減らす為に、Problem 15と同様にメモ化する。
import scala.collection.mutable.HashMap
object P018 {
val input:Array[String] = Array(
"75",
"95 64",
...中略...
"63 66 04 68 89 53 67 30 73 16 69 87 40 31",
"04 62 98 27 23 09 70 98 73 93 38 53 60 04 23") // y=0
val data:Array[Array[Int]] = input.map{s => s.split(" ").map{x => x.toInt}}
val height = input.size
def value(x:Int,y:Int):Int = data(height-1-y)(x)
val map:HashMap[Tuple2[Int,Int],Int] = new HashMap()
def search(x:Int,y:Int):Int = map.get(Tuple2(x,y)) match {
case Some(x) => x
case None => (x,y) match {
case (_,0) => {
val v = value(x,y)
map.put(Tuple2(x,y),v)
v
}
case _ => {
val s0 = value(x,y)
val s1 = search(x,y-1)
val s2 = search(x+1,y-1)
val v = if (s1>s2) s0+s1 else s0+s2
map.put(Tuple2(x,y),v)
v
}
}
}
def main(args:Array[String]) {
println(search(0,height-1))
}
}
ラベル:
Project euler,
scala
[Project Euler] Problem 17
Problem 17
綴りが間違っていると正解が出ないので、念のために数詞を調べ直したりとか、英語を使ってない我々にはそれだけで敷居が高い問題。
この手の問題を解く時は、match-case構文を便利だと特に感じる。
綴りが間違っていると正解が出ないので、念のために数詞を調べ直したりとか、英語を使ってない我々にはそれだけで敷居が高い問題。
この手の問題を解く時は、match-case構文を便利だと特に感じる。
object P017 {
val digitOne:List[String] = List("", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine")
val teens:List[String] = List("", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen")
val digitTen:List[String] = List("", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety")
def toEnglish(n:Int):String = n match {
case 1000 => "one thousand"
case _ if (n/100 != 0) => digitOne(n/100)+" hundred" + (if (n%100==0) "" else " and "+toEnglish(n%100))
case _ if (10<n)&&(n<20) => teens(n-10)
case _ => Tuple2(n/10, n%10) match {
case (a,0) => digitTen(a)
case (0,b) => digitOne(b)
case (a,b) => digitTen(a)+"-"+digitOne(b)
}
}
def countLetter(s:String) = s.split("[ -]").map{s => s.length}.foldLeft(0)(_+_)
def main(args:Array[String]) {
/*
println(List(1,9,10,11,19,20,21,99).map{x => Tuple3(x,toEnglish(x),countLetter(toEnglish(x)))})
println(List(100,101,110,111,120,121,199).map{x => Tuple2(x,toEnglish(x))})
println(List(200,201,210,211,299).map{x => Tuple2(x,toEnglish(x))})
println(List(900,901,910,911,999,1000).map{x => Tuple2(x,toEnglish(x))})
*/
println(List(342,115).map{x => Tuple3(x,toEnglish(x),countLetter(toEnglish(x)))})
println(List.range(1,1001).map{x => countLetter(toEnglish(x))}.foldLeft(0)(_+_))
}
}
ラベル:
Project euler,
scala
[Project Euler] Problem 16
Problem 16
java.math.BigIntegerを使うだけ。
java.math.BigIntegerを使うだけ。
object P016 {
def main(args:Array[String]) {
val v2 = new BigInt(java.math.BigInteger.valueOf(2L))
val r = v2.pow(1000).toString.toCharArray.map{c => c-'0'}.foldLeft(0)(_+_)
println(r)
}
}
ラベル:
Project euler,
scala
[Project Euler] Problem 15
Problem 15
これも計算機を使わないで解いた方が速い問題。
n x n grid で考えると、2n ステップの中から n 個右を選ぶということだから、
_{2n}C_n を計算すればいい。つまり、(2n)! / (n!)^2 。
もうちょっと計算機っぽく考えると、nx x ny のグリッドの場合、最初に右に行くか下に行くかで、
f(nx,ny) = f(xn-1,ny) + f(xn,ny-1)
但し、
f(0,_) = f(_,0) = 1
を解けば良いが、最初の式は実は _nC_r = _{n-1}C_r + _{n-1}C_{r-1} の事である。
実際にはこのままではf(nx,ny)回の関数呼び出しが発生するので、メモ化する。
これも計算機を使わないで解いた方が速い問題。
n x n grid で考えると、2n ステップの中から n 個右を選ぶということだから、
_{2n}C_n を計算すればいい。つまり、(2n)! / (n!)^2 。
もうちょっと計算機っぽく考えると、nx x ny のグリッドの場合、最初に右に行くか下に行くかで、
f(nx,ny) = f(xn-1,ny) + f(xn,ny-1)
但し、
f(0,_) = f(_,0) = 1
を解けば良いが、最初の式は実は _nC_r = _{n-1}C_r + _{n-1}C_{r-1} の事である。
実際にはこのままではf(nx,ny)回の関数呼び出しが発生するので、メモ化する。
import scala.collection.mutable.HashMap
import java.math.BigInteger
object P015 {
val map:HashMap[Tuple2[Int,Int],Long] = new HashMap()
def f(nx:Int, ny:Int):Long = map.get(Tuple2(nx,ny)) match {
case Some(x) => x
case None => {
val z:Long = (nx,ny) match {
case (0,_) => 1
case (_,0) => 1
case (x,y) => f(x-1,y) + f(x,y-1)
}
val zz = map.put(Tuple2(nx,ny),z)
z
}
}
def main(args:Array[String]) {
println(f(20,20))
println(40L/20*39*38/19*37*36/18*35*34/17*33*32/16*31*30/15*29*28/14*27*26/13*25*24/12*23*22/11*21/10/9/8/7/6/5/4/3/2/1)
}
}
ラベル:
Project euler,
scala
[Project Euler] Problem 14
Problem 14
有名なCollatz問題。最初はListを使っていたのだがOutOfMemoryになるので普通に命令型っぽいプログラムになっている。
有名なCollatz問題。最初はListを使っていたのだがOutOfMemoryになるので普通に命令型っぽいプログラムになっている。
object P014 {
def collatz(n:Long):Int = {
def f(n:Long, c:Int):Int = {
if (n==1L) c
else if (n%2L==0) f(n/2, c+1)
else f(3L*n+1, c+1)
}
f(n,1)
}
def mx(a:Tuple2[Long,Int], b:Tuple2[Long,Int]):Tuple2[Long,Int] = if (a._2 > b._2) a else b
def maxLength(m:Int):Tuple2[Long,Int] = {
var ts:Tuple2[Long,Int] = Tuple2(0L,0)
for(x <- List.range(1, m)) {
val c:Int = collatz(x)
if (ts._2 < c) {ts = Tuple2(x,c)}
}
ts
}
def main(args:Array[String]) {
println(collatz(13L))
println(maxLength(1000000))
}
}
ラベル:
Project euler,
scala
Subscribe to:
Posts (Atom)