Haskellの言語拡張たち
前回、なんか拡張を沢山使っていたが、おまじないのままなのもそろそろまずい感じなので、とりあえず調べてみた。
今回調べた拡張
- 型系
- GADTs
- ScopedTypeVariables
- EmptyDataDecls
- TypeFamilies
- 型クラス系
- MultiParamTypeClasses
- TypeSynonymInstances
- FlexibleInstances
- FlexibleContexts
- パターン系
- BangPatterns
- PatternGuards
- ViewPatterns
- 文字列系
- OverloadedStrings
- TemplateHaskell系
- TemplateHaskell
- QuasiQuotes
- import系
- ImplicitPrelude
- PackageImports
- 他言語系
- CPP
- ForeignFunctionInterface
設定方法
hsファイルの上の方に、
{-# LANGUAGE 〜 #-}
な感じで書くか、実行時に
$ ghc -X〜 ... $ ghci -X〜 ... $ runhaskell -X〜 ...
な感じで指定する。
無効にする場合は、No〜 を指定する。
調べてるときに使った GHC は 7.0.4 。
型系
GADTs
代数的データ型のもつ型変数に対して、型を限定した型構築子が書ける。
{-# LANGUAGE GADTs #-} -- GADTs 拡張が必要 data List a where INil :: List Int CNil :: List Char Cons :: a -> List a -> List a
ScopedTypeVariables
スコープを持つ明示的な型変数 (forall) を書ける。
-- x と y の型が違うのでエラーになる myId :: a -> a myId x = y where y :: a y = x
↓
{-# LANGUAGE ScopedTypeVariables #-} -- ScopedTypeVariables 拡張が必要 myId :: forall a. a -> a myId x = y where y :: a y = x
EmptyDataDecls
構築子のないデータ型の宣言を書ける。
{-# LANGUAGE EmptyDataDecls #-} -- EmptyDataDecls 拡張が必要 data EmpData data EmpDataF a
何も指定しなくても通ったので、デフォルトで有効のよう。
試しに NoEmptyDataDecls を指定したら、コンパイラに EmptyDataDecls を指定しろといわれた。
TypeFamilies
型族やデータ族が書ける。
{-# LANGUAGE TypeFamilies #-} -- 型族 -- TypeFamilies 拡張が必要 type family TypeConv a :: * type instance TypeConv EmpData = Int type instance TypeConv (EmpDataF a) = a -- データ族 -- TypeFamilies 拡張が必要 data family MyDF a data instance MyDF Int = MyDF1 Int | MyDF2 Int Int newtype instance MyDF EmpData = MyDF3 Bool newtype instance MyDF (EmpDataF a) = MyDF4 a
型クラス系
MultiParamTypeClasses
型パラメータを複数持つ型クラスが書ける。
{-# LANGUAGE MultiParamTypeClasses #-} -- MultiParamTypeClasses 拡張が必要 class Set s a where empty :: s a insert :: a -> s a -> s a member :: a -> s a -> Bool
TypeSynonymInstances
型シノニム (typeで宣言した型) に対して、インスタンス宣言が書ける。
{-# LANGUAGE TypeSynonymInstances #-} class CHoge a where hoge :: a -> a type SHoge = String -- TypeSynonymInstances 拡張が必要 instance CHoge SHoge where hoge = id
FlexibleInstances
型引数を持つ型に、特定の型を与えたものに対して、インスタンス宣言が書ける。
{-# LANGUAGE FlexibleInstances #-} class CHoge a where hoge :: a -> a -- FlexibleInstances 拡張が必要 instance CHoge (Maybe Int) where hoge _ = Nothing
FlexibleContexts
型パラメータを複数持つ型クラス制約が書ける。
{-# LANGUAGE MultiParamTypeClasses, FlexibleContexts #-} -- MultiParamTypeClasses 拡張が必要 class CCHoge a b where choge :: a -> b -- FlexibleContexts 拡張が必要 ihoge :: (CCHoge a Int) => a -> Int ihoge _ = 0
パターン系
BangPatterns
!(パターン) で、束縛時にそのパターンを正格評価する。
{-# LANGUAGE BangPatterns #-} -- BangPatterns 拡張が必要 myseq :: a -> b -> b myseq !x y = y
PatternGuards
パターンを含むガードが書ける。
{-# LANGUAGE PatternGuards #-} -- PatternGuards 拡張が必要 justOddOrElse :: Maybe Int -> Int -> Int justOddOrElse x y | Just a <- x, odd a = a | otherwise = y
これもデフォルトで有効のよう。
ViewPatterns
パターンの中で関数を呼んで、その結果に対してマッチするパターンマッチ (関数 -> パターン) が書ける。
{-# LANGUAGE ViewPatterns #-} import Control.Monad (mfilter) -- ViewPatternt 拡張が必要 justOddOrElse :: Maybe Int -> Int -> Int justOddOrElse (mfilter odd -> Just a) _ = a justOddOrElse _ b = b
文字列系
OverloadedStrings
文字列リテラルの型を、Stringではなく、(IsString a) => a にする。
{-# LANGUAGE OverloadedStrings #-} import Data.ByteString (ByteString) import Data.ByteString.Char8 () -- for IsString ByteString -- OverloadedStrings 拡張が必要 hogebstr :: ByteString hogebstr = "hoge"
TemplateHaskell系
TemplateHaskell
TemplateHaskell の構文が使える。
コンパイル時メタプログラミングとかできるようになる。
QuasiQuotes
準クォート ([〜| 〜 |]) が使える。
Yesod の [persist| 〜 |] とか [hamlet| 〜 |] とか。
import系
ImplicitPrelude
Prelude を暗黙的にインポートする。
デフォルトで有効。
NoImplicitPrelude を指定することで、暗黙的に Prelude が import されないようにできる。
PackageImports
パッケージ名で修飾したimport宣言 (import "(パッケージ名)" ~) を書ける。
他言語系
ForeignFunctionInterface
他言語関数インタフェース (FFI) を有効にする。
デフォルトで有効らしい。
Haskell で DB操作
最近 Yesod を弄っているが、Yesod で使ってるやつ (Database.Persistent) を使って、普通に DB 操作したいな、と。
sqlite と mongodb をやってみる。
github にあげた分 → https://github.com/rf0444/haskell-db
とりあえず自分の環境 (Mac) で runhaskell で確認した。
cabal はめんどそうなのでまた今度。
sqlite 編
Yesod の Persistent の通りにやればまあ動く。
構成を Yesod のプロジェクトっぽくしたかったので、yesod init した後の Model.hs を持ってきて、Yesod 関係のものを書き換える。
{-# LANGUAGE TypeFamilies, TemplateHaskell, FlexibleContexts, GADTs #-} module Model where import Data.Text (Text) import Database.Persist.Quasi import Database.Persist.Sqlite import Database.Persist.TH share [mkPersist sqlSettings, mkMigrate "migrateAll"] $(persistFileWith lowerCaseSettings "config/models")
こんな感じ。拡張が豪華だ・・・。
(5/13 いらなかった拡張を消しました)
config/models は、
User email Text password Text Maybe UniqueUser email
こんな感じ。テスト用なのでとても単純に。
本体 (main.hs) は、
{-# LANGUAGE OverloadedStrings #-} import Database.Persist.Sqlite import Model main = withSqliteConn path $ runSqlConn $ do runMigration migrateAll insert $ User { userEmail = "hoge@hoge.jp", userPassword = Just "hoge" } return () where path = "hogesql.sqlite3"
こんな感じ。
runhaskell を 2回たたくと、ちゃんと2 回目は error になってくれる。
$ runhaskell main.hs $ runhaskell main.hs main.hs: user error (SQLite3 returned ErrorConstraint while attempting to perform step.)
mongodb 編
config/models はそのままで、Model.hs と main.hs を書き換える。
Model.hs は、
{-# LANGUAGE TypeFamilies, TemplateHaskell, FlexibleContexts, GADTs #-} module Model where import Data.Text (Text) import Database.Persist.Quasi import Database.Persist.MongoDB import Database.Persist.TH import Language.Haskell.TH.Syntax share [mkPersist MkPersistSettings { mpsBackend = ConT ''Action }, mkMigrate "migrateAll"] $(persistFileWith lowerCaseSettings "config/models")
こんな感じ。
sqlite 版との違いは、Database.Persistent.Sqlite が Database.Persistent.MongoDB になったのと、
mkPersist の引数が変わっているところ。ConT ''Action とかやってるので、Language.Haskell.TH.Syntax を import する。
main.hs は、
{-# LANGUAGE OverloadedStrings #-} import Database.Persist.MongoDB import Model main = withMongoDBConn dbname hostname $ runMongoDBConn master $ do insert $ User { userEmail = "hoge@hoge.jp", userPassword = Just "hoge" } return () where hostname = "localhost" dbname = "test"
こんな感じ。
sqlite 版との違いは、Database.Persistent.Sqlite が Database.Persistent.MongoDB になったのと、
withSqliteConn/runSqlConn が、withMongoDBConn/runMongoDBConn になったのと、
runMigration migrateAll がなくなったこと。
runMongoDBConn の第1引数には、書き込むならとりあえす master でいいっぽい。
詳しくは hackage の Database.Persist.MongoDB とか。
というか、これ 0.6.3 までしかドキュメントがない・・・。
sqlite の時は config/models の変更の際にテーブル構造を変更したりするように runMigration migrateAll をしていたが、
mongodb ではそもそもそういう構造を管理しないので、必要ないそう。
If you were using the MongoDB backend, migration would not be needed.
http://www.yesodweb.com/blog/2012/01/blog-example
で、runhaskell をたたくと動いてくれた。
$ runhaskell main.hs $ mongo MongoDB shell version: 2.0.4 connecting to: test > db.user.find() { "_id" : ObjectId("4f9e59686aface0ae8000000"), "email" : "hoge@hoge.jp", "password" : "hoge" }
が、もう一回たたくと・・・
$ runhaskell main.hs $ mongo MongoDB shell version: 2.0.4 connecting to: test > db.user.find() { "_id" : ObjectId("4f9e59686aface0ae8000000"), "email" : "hoge@hoge.jp", "password" : "hoge" } { "_id" : ObjectId("4f9e598c6aface0aff000000"), "email" : "hoge@hoge.jp", "password" : "hoge" }
・・・あれ? 入ってる・・・。
yesod init で普通にプロジェクト作ってやってみても、やっぱり重複して入れれるっぽい。
この辺 migration とかでやってほしい気も。
手で unique index はってみると、
$ mongo MongoDB shell version: 2.0.4 connecting to: test > db.user.remove() > db.user.ensureIndex({email: 1}, {unique: true}) > exit $ runhaskell main.hs $ runhaskell main.hs main.hs: PersistMongoDBError "WriteFailure 11000 \"E11000 duplicate key error index: test.user.$email_1 dup key: { : \\\"hoge@hoge.jp\\\" }\""
ちゃんと 2回目は error になってくれた。
The End of Start Haskell
1/28 に、第6回 スタートHaskell に行ってきました!
また1週間かかってしまった・・・遅延評価だから仕方がない (キリッ
- 12章 遅延評価 解説
最内簡約
(Leftmost) Innermost evaluation
内側から外側、左から右
関数適用より先に引数が評価 引数の値渡し (call-by-value)
最外簡約
(Leftmost) Outermost evaluation
外側から内側、左から右
引数の評価より先に関数が適用される 引数の名前渡し (call-by-name)
(値渡し、名前渡しより最内、最外のほうが分かりやすい)
(ここで遅刻組到着)
(大量の参加者が遅延評価されている)
(Haskell は) Lambda の中は簡約しない。
Lambda は関数定義
Lambda 計算に基づいているので、Lambda 内は弄らない
コンパイル時に最適化される話と、実行時にどうやって簡約されるかは全く別の話
値渡しでは停止しない式も、名前渡しだと停止することもある。
停止する評価戦略があれば、名前渡しは必ず停止し、その戦略時の評価と同じ結果を返す
簡約回数
元々一つの式なら、1度だけ評価してくれる (式の共有)
同じ式が2つ出てきただけなら、共有してくれない
変数に抽出すると、その変数が評価されるとき、1度だけ評価してくれる
call-by-name + 式の共有 = call-by-need = lazy-evaluation
木の簡約ではなく、グラフ簡約になる
共有部分が出来るので、木構造が崩れる
部品プログラミング
データと制御を切り離す
無限データを定義、どれだけ使うかは制御側で
無限データ自体は、遅延でなくても、再帰的データ構造が使えれば作れる
正格適用
$! (ダラバン) 演算子
$ 演算子の、右側を先に評価する版
空間効率が向上することがある
しないこともある
seq 関数を使って定義される
foldl とかは正格が良さげ
foldr とかは遅延のが良さげ
Weak Head Normal Form (WHNF)
参考: http://itpro.nikkeibp.co.jp/article/COLUMN/20070305/263828/?ST=ittrend&mkjt&P=2
Normal Form : これ以上簡約できない式
Normal Form と見なされるための制約を緩めたものの一つが、WHNF
Haskell は、式を WHNF に簡約する
例を考えるときは、Lambda より List の方が分かりやすい
- 12章 演習問題
-
- 1, 2, 3
@choplin
https://github.com/choplin/start_haskell/blob/master/12.lhs
-
- 4
@shokos
fibs = 0:1:[uncurry (+) (a, b) | (a, b) <- zip fibs (tail fibs)]
uncurry なしで
fibs = 0:1:[a + b | (a, b) <- zip fibs (tail fibs)]
でもできる。
リスト内包表記なしなら、
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
とか、パターンマッチを使って、
fibs@(_:tfibs) = 0 : 1 : zipWith (+) fibs tfibs
とか書ける。
自分は、
fibs = 0 : scanl (+) 1 fibs
が好き。
-
- 5
@dekosuke
fib n = head $ drop n fibs fib1000 = head $ dropWhile (<= 1000) fibs
!! を使って、
fib n = fibs !! n
でもいい。
-
- 6
@beketa
repeatTree x = xTree where xTree = Node xTree x xTree
とか。
- 13章 プログラムの論証 解説
@kawamoto
関数定義を、逆に置換することも出来る
パターンマッチを使った定義は、それより上の定義に一致しないという条件が付くので注意
関数の性質から定義を導く
天下り的に定義を与えるのではなく、性質を満たすことを証明することで、その定義を導く
確立できれば、「証明駆動開発」も夢じゃない!?
既に効率の悪いものがある場合、引数を一つ増やした版を作って、その2つの関係を証明していくことで、引数増やしたの関数定義を導く
引数増やした版の関数を使って元の関数を定義すると、効率の良いものが出来る
証明したい性質・関数をうまく一般化してやると、証明が簡単になり、また導かれる関数の効率がよくなることがよくある
CPS 変換して証明して、元の定義は cont に id 入れるのと似ている
末尾再帰になって効率上がるし。
フィボナッチのときも、「n の時に成り立ち、かつ n + 1 の時に成り立つ」で証明した。
参考文献 30: http://homepages.inf.ed.ac.uk/wadler/papers/vanish/vanish.pdf
($) と (.) の話: http://d.hatena.ne.jp/kazu-yamamoto/20100702/1278036842
- 13章 演習問題
自分が Coq でやった分: https://github.com/rf0444/coq/blob/master/start_haskell/13.v
-
- 1
重複のあるパターンで定義されている関数
-
- 2, 3, 4, 5
ひたすら数学的帰納法が続く。
-
- 7
@master_q
http://www.slideshare.net/master_q/20120128-start-haskell6
背景のイカwww
-
- 8
@sat0_da
Coq 紹介
change で 指定された形に簡約する
-
- 9
@senzans
https://github.com/seizans/exercise/blob/master/start_haskell/ch13/ex9.lhs
-
- 10
@beketa
- LT
QuickCheck の話
性質検証
性質を書いて、ランダムチェックできる
template haskell を使って、prop_ から始まるテストを全て実行できる
生成されたランダム値を出力することもできる
参考: http://itpro.nikkeibp.co.jp/article/COLUMN/20080304/295346/
shpider package
http://hackage.haskell.org/package/shpider-0.2.1.1
クローラ
使って、食べログにばんくらった。
HaskellWiki をクロールしてみた
http://d.hatena.ne.jp/Dekosuke/20120108
OpenGL を使ってみた
https://github.com/shtaag/Haskell/tree/master/opengl
http://taketoncheir.hatenablog.com/entry/2012/01/07/232345
最終的にはゲームを作りたい
モナディウス的な
gloss package が便利らしい
http://hackage.haskell.org/package/gloss-1.0.0.1
逆ポーランド記法の電卓を作った
https://github.com/yunomu/exercises/tree/master/dc_haskell
Real World な Haskell
浮動小数注意
演算で投げられる例外に注意
ArithException か SomeException か
Hoogle をローカルで使う
Hoogle: http://www.haskell.org/hoogle/
入れ方
cabal install hoogle
わりと時間かかる
hoogle data
やり方
hoogle 調べたいやつ
ghci 中で :hoogle
~/.cabal/bin/hoogle server
ポート80で見れる
GHCi debugger
http://d.hatena.ne.jp/khibino0/20111212/1323680441
Haskell とテストと BDD
http://d.hatena.ne.jp/kazu-yamamoto/20120112/1326335764
ぶっちゃけて言うと、BDD は TDD
名前にテストって入ってると設計的な見方が軽視される的な
haddoc: doctest の Haskell 版的な
quickcheck 的なこともしたい
test-framework 使いたい
quickcheck 自体を document の方に書きたい
haddoc 拡張されるかも!
Haskell の勉強会
http://wiki.haskell.jp/Workshop
- 次回
多数決的には Real World Haskell か?
Learn You a Haskell for Great Good (日本語版!?) になるとか。
Purely Functional Data Structures読書会 第4回
1/21 に、Purely Functional Data Structures読書会 第4回 に行ってきました。
まとめ的な: http://wiki.haskell.jp/Workshop/ReadPFDS/4
- 3.4 (c) (d)
@khibino
前回末尾再帰になっていなかったから、CPS変換して末尾再帰にしたらしい。
なんかいきなり継続の話に。
任意の場所で継続がとれる、call/cc スタイルの CPS だけを CPS という人もいるらしい。
- 3.10 (b)
@imsuten
http://blog-ja.intransient.info/2012/01/red-black-tree-balance.html
以下の balanceL も見ておくといい
http://hackage.haskell.org/packages/archive/containers/0.4.2.0/doc/html/src/Data-Map.html#Map
- 4
@master_q
4章をOCamlで書く
やる気のある資料: http://www.slideshare.net/master_q/pfds-4ocaml
$-notation の代わりに lazy キーワードを使う
lazy の後は気持ちよく全部括弧でくるむ!
(括弧が嫌なら begin/end も使える)
Lazy.force で取り出す
カリー形式だと一気にマッチできないので、タプルを使うことが多い (ML系)
fun plus($m, $n) = $m + n
↓
let plus (lazy m) (lazy n) = lazy (m + n)
-
- m + n の計算は遅延される
- m と n は評価されてしまう
fun lazy plus ($m, $n) = $m + n
=
fun plus (m, n) = $case (m, n) of ($m, $n) => force ($m + n)
↓
let plus m n = lazy (match (m, n) with (lazy m, lazy n) -> m + n)
-
- with の先でマッチした変数名を m, n として、そのスコープでもとの変数を隠すこともある
- シャドウイングという
- よく使うかは派閥による
- m, n の中身をほどくのも、その足し算も遅延される
- with の先でマッチした変数名を m, n として、そのスコープでもとの変数を隠すこともある
-
- Stream の型
- susp の代わりに Lazy.t を使う
- Stream の型
トップレベルの let はシャドウイング出来る
OCaml の文法は気違い (by kazu_yamamoto)
- 4.1
@seizans
fun dropA x = $case x of | (0, s) = force s | (n, $Nil) = force $Nil | (n, $Cons(x, s)) = force (dropA(n - 1, s))
fun dropB x = $case x of | (n, s) = force ( let fun dropB' (0, s) = s dropB' (n, $Nil) = $Nil dropB' (n, $Cons(x, s)) = dropB' (n - 1, s) in dropB' (n, s) )
force を中に入れたり外に出したりはできる。
n をばらしたとき、 force ($ ...) がいくつか出来るが、それは簡約可能。
- 4.2
@rf0444
遅延リストに対して insertion sort を作って、その計算量がソート済み先頭k要素を取ってくるなら、O(n*k) になるっていうの。
最初 Coq で計算量の証明をしようとしていたが、・・・挫折。
(跡地: https://github.com/rf0444/coq/tree/master/pfds)
前日に Haskell で作って、挙動を追うと、・・・あれ?挿入ソートというよりは・・・バブルソートの挙動になってる!!
https://github.com/rf0444/haskell/tree/master/study/PFDS/C4
ソート超奥深そう。
遅延リストの挿入ソートの挙動がバブルソートっぽくなるのは、アルゴリズムのなんとか変換とかいう概念があるらしい。
homomorphic sort でぐぐると幸せになれるらしい。
http://d.hatena.ne.jp/kazu-yamamoto/20110913/1315905876
- 5
@senzans
償却計算量、銀行家と物理屋の手法
ならし解析
アルゴリズムイントロダクションを読んで、比較すると面白いらしい。
用語対応: https://twitter.com/#!/seizans/status/158462657807138816
銀行家の方法は、正格/遅延リストで、積み立て/借金の方法で計算量を出す。
- 次回
引き続き 5章解説。
となりで @S1E11 が頑張って資料作っていた。
Purely Functional Data Structures読書会 第3回
12/17 に、Purely Functional Data Structures読書会 第3回 に行ってきました。
- 開始前
Mac (Lion) のデスクトップ増やす:
Mission Control から カーソルを右上の方にやると「+」が出てくる。
押すと増える。
Lion から操作が変わった部分は、わりと前から使っていたユーザを苦しめてるっぽい。
- 練習問題回答
-
- 3.2 LeftistHeap の insert を merge を使わずに実装する
http://blog-ja.intransient.info/2011/11/leftistheap-in-haskell.html
こういうのって、Coq で書いていれば、どんな入力に対しても、
元のやつと新しく作ったやつが同じ動作をするとか証明できていいなと思った。
Heap Tree はバランスしてない方が速いことが多いらしい。
(makeT y b (insert x a) の方が速い?)
quickCheck の代わりに verboseCheck を使うと、実際に入れられた値が分かる。
100個くらいだと、あまり信頼できない。
(リストとかだと、割と空リストが多い)
-
- 2.6 UnbalancedSet を基に FiniteMap を作る
OCaml で。
val とか with type とか。ちょっと微妙らしい。
functor は最近ではあまり使われてなく、first class module が使われてるらしい。
-
- 3.5 BinominalHeap の findMin を removeMinTree を使わずに作る
findMin ts = minimum $ fmap root ts
な感じ。
minimuBy を使うともっといい感じにできるかも。
OCaml:
比較演算は勝手にできるようになるらしい。
(デフォルトで deriving Eq, Ord 的な)
deriving もあって、既存の型に Show 的なものをつけたりすることも出来る。
タプルの括弧が省略できる。(, があればおk)
カリー化された関数は、タプルにしてパターンマッチというのをやることが多いらしい。
テストのお話 by kazu_yamamoto
スマートズーム : 環境設定/ユニバーサルアクセス/視覚/ズーム機能/オプション の一番下「スクロールホイールと修飾キーを使ってズーム」
model check : 動くものが既にあるときに、それと同じものを返すことを確認する
quickCheck を手動でやらず、テストフレームワークを使うと楽。
test-framework (利用例)
https://github.com/kazu-yamamoto/bst/blob/master/test/Test.hs
TestGroupGenerator
http://hackage.haskell.org/package/test-framework-th
-
- 3.6 BinomialHeap の rank を Tree の外に出して作る
https://github.com/seizans/pfds/blob/master/2/BinomialHeap.hs
型の定義をうまくすると、一部の関数を除いて殆ど同じにできるらしい。
-
- 3.9 リストから Red-Black Tree を作る関数 fromOrdList を作る
https://github.com/shtaag/Haskell/blob/master/pfds/RedBlackSet.hs
参考:http://t.co/P3SiwhRE
資料:http://www.slideshare.net/ShigekazuTakei/pfds-ex3-9
Red-Black Tree は、赤いエッジを心眼で見なくすると、2-3-4木 (完全バランス) らしい。
2-3木でも完全バランスするらしく、それだと赤は左だけで出来る。
2-3木を普通に作ってもいいかも。
Red-Black Tree への insert は、最初赤で入れると、
黒の制約そのままで、赤の制約に引っかかる。
黒の制約を満たしつつ、バランスしていくと、root に赤が来て、
それ以外はうまくいっている状態になる。
あとは、root の色を黒にすれば、完成。らしい。
Red-Black Tree の制約は緩く、多くの実装がある。
アルゴリズム・イントロダクションでは、叔父のノードまで見て
8パターンの balance になっている。
B木は 2-3-4木/Red-Black Tree と近い。(同じ?)
2-3-4木:
各ノードが、
1つの要素と2つの子/2つの要素と3つの子/3つの要素と4つの子
のどれかである木。 完全バランスしている。
Red-Black Tree の赤のノードを親にくっつけると、2-3-4木が出来る。
-
- 3.10 balance 関数を右と左に分けて作る
https://github.com/kazu-yamamoto/llrbtree/blob/master/Data/RBTree/Original.hs
-
- 3.4 (b) LeftistHeap を weight-biased にする
makeT だけ書き換えてできる。
-
- 3.4 (c) makeT を使わないようにして、単一パスの merge を作る
top-down にする。末尾再帰みたいにする。
次回へ。
-
- 3.8 サイズ n の深さは 2 * floor(log (n + 1)) 以下になることを証明
https://docs.google.com/document/d/1MfH9-GXHzemYUaM3LagyBcN12GdyPPxeyvJ3VyQAoAo/edit?hl=ja&pli=1
帰納法で証明するといいらしい。
- 4章解説
OCaml の lazy
https://github.com/master-q/readPurelyFunctionalDataStructures/tree/master/LazyEvaluation
遅延リストの中身が取得時に評価されてしまうかも。
Haskell すばらしい。
遅延リストはいいぞ。
fibs = 1:1:zipWith (+) fibs (tail fibs)
とか
fibs = 1:scanl (+) 1 fibs
とか。
fibs = 1:zipWith (+) fibs (tail fibs)
ってやると2つめが以降が返って来ないとか。
- 帰り
@seizans と @S1E11 と中華食べた。
Haskell 触った後 Java 触ると Java の書き方が変わったり Java が残念に感じるよねって話とか、
Java は Eclipse が型推論してくれるんだ(キリッ)とか、
Eclipse の設定やショートカットとか、
お仕事の話とか。
- 次の日
まとめようと思ったけど睡魔に負けた・・・
第5回 スタートHaskell
12/5 に、第5回 スタートHaskell に行ってきました!
会社の先輩 (@seizans) に誘われて、久しぶりの勉強会 & 初スタートHaskell!
- 前日
本の中身をざっくりみた後、演習をやっておこうとした。
環境をみてみると、Haskell Platform 入れてなくて、
Mac Ports の ghc が入っていたので、
そっちはアンインストールして、Haskell Platform を入れようとしたが、
家のネットが調子悪く、とりあえす今回はこのままで行くことに。
割と夜遅くなったので、練習問題と関係ありそうな演習はなんとか終わらせて寝た。
- 当日
品川駅で迷ったり、大森駅で逆方向から出て迷ったりしたけど、なんとか辿り着けた。
togetter - スタートHaskell第5回 まとめ : http://togetter.com/li/222626
- 第10章:クラスとインスタンスの宣言
@ruicc さん
資料 : http://www.slideshare.net/RuiccRail/programming-haskell-chapter10
Haskell といえば・・・
モナド?いいえ、型クラスです。
-
- オブジェクト指向から理解する型クラス
OO: クラス (型)、インスタンス(値)
Haskell: 型クラス(型)、型(型)
型クラスにメソッドがあり、型にフィールドがある、的な。
-
- データ構造比較
OO: 直積構造、状態
Haskell: 直積構造、直和構造、再帰構造
data Hoge a (ここまで型の世界) = (ここから値の世界) MkInt Int | MkA a add :: Int -> Int -> Int (型の世界) add a b = a + b (値の世界)
-
- OOで直和クラス
State Pattern, 状態をフラグ管理 など (大変・・・(特に使う側))
「「状態」と書いて、大いなるバグの母と読む」
OOで再帰構造
Composite, Visitor Pattern (大変・・・)
パターンの粒度が大きく、組み合わせが面倒
意図がばらける
オブジェクトをまたぐ処理が苦手
-
- private がない
(Python にも JS にもない)
Haskell だったら
フィールドのprivate
ロジックを書くのに状態は必要ない (直和で十分)
パフォーマンスの際には、module単位で隠蔽
メソッドのprivate
module, where で隠蔽
-
- 抽象力比較
OO:
型の継承 - メソッドの依存関係の継承 (フィールド非依存)
オーバーライドが複数回あり得る
実装の継承 - フィールド依存
Haskell:
型クラス間で継承 (多重継承可)
型での実装(オーバーライド)は1回
型クラス - OO のインタフェース的な
型 - OO のクラス (-α) 的な
型クラスのクラスは、集合論のクラスに近いらしい。
同じ性質を持った型の集合。
型クラスの継承
class (親 a) => 子 a where ... class (親1 a, 親2 a) => 子 a where ...
型クラスにデフォルト実装も書ける
Scala の trait 的な
既にある型に、後から型クラスをつけることも出来る
型での実装
instance 型クラス 型 where ...
data 型名 = ... deriving(型クラス)
で、インスタンスを書くことなく型クラスを実装できる。
(特殊な場合のみ)
種については省略
(* -> * とからしい。まだよくわからん)
仮想マシンの eval と exec (相互再帰)
左を評価して、右は後で
後でやるのはスタックに積んでおく
型クラスとOOの話でおおいに盛り上がっていた
(1時間超過)
会場のコンセントに、MBAの電源がささらない・・・
(でかい部分が入らない)
- 第11章:切符番号遊び
@dekosuke さん
Twitter の数字遊び (10になったー)
使える演算とかは割と曖昧
切符番号遊び
四則演算のみ、並べ替え可
テキストに沿った解説
choices は、Data.List の中の関数を使えば、
Prelude Data.List> let choices = (>>= permutations) . subsequences Prelude Data.List> choices [1..3] [[],[1],[2],[1,2],[2,1],[3],[1,3],[3,1],[2,3],[3,2],[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
こんな感じで書けた。
@kazu_yamamoto さん
資料 : http://mew.org/~kazu/material/2011-monad.pdf
モナドはトップダウンで理解するのは難しい
(とても抽象的)
まずは具体例から見ていくとよい
統一理論と大統一理論
物理
電磁気力 + 弱い力: 電弱統一理論
強い力 + 電弱統一理論 : 大統一理論
あと重力 (アインシュタイン は 大統一理論とくっつけようとして死んでしまったらしい)
いきなり大統一理論を与えられても分からない
(4つの力があって、それを統一的に扱いたいということが分からない)
モナドも同じ
Haskell
Parser + IO : 状態系
List + Maybe : 失敗系
状態系 + 失敗系 : コンテナ
状態系統一理論
Parser と IO : なんか似ている
共通点 : データ定義、生成する関数、合成する関数
型クラスで共通化
糖衣構文(do)を用意
- > 命令型言語の逐次実行の再発明!
失敗系統一理論
Maybe は失敗と1つの成功 (答えが0個か1個)
List は失敗と複数の成功 (答えが0個以上)
Maybe は合成できた。
List も出来る!
Maybe の合成は0と1のかけ算っぽい (Nothing が 0)
List もかけ算 (組み合わせ) にする
大統一理論
失敗系と状態系の統一 (Philip Wadler)
コンテナ
中身が一つの型、生成関数、合成関数を持つ
文脈として使える
Parser : パーサー、IO : 副作用表現
Maybe : 失敗しうる計算、List : 答えが0個以上の計算 (非決定性を持つ計算)
文脈が混ざらないこと!
力が弱いものから使う
弱いものほど安全
再帰 > 畳み込み > 単純な高階関数
プログラム可能コンテナ (>>=) > 逐次コンテナ (<*>, return) > マップ可能コンテナ (<$>)
(<$>) :: (a -> b) -> (m a -> m b) (fmap)
f :: a -> b とすれば、
(f <$>) :: (m a -> m b)
f という関数を m という文脈に持ち上げる (lift)
2引数関数 f :: a -> b -> c を、<$> で m の文脈に持ち上げると、
(f <$>) :: m a -> m (b -> c)
関数が文脈 m の中に入る
このような、文脈の中の関数も適用できるようにしたい
(<*>) :: m (a -> b) -> m a -> m b (app)
文脈 m の中の関数を適用している
(逐次らしい)
例えば、
(+) <$> [1,2] <*> [3,4]
のように書け、
<$> と <*> を消すと、通常の関数適用のように見える
(>>=) :: m a -> (a -> m b) -> m b (bind)
(分岐らしい)
プログラム可能コンテナ : Monad
逐次コンテナ : Applicativce
マップ可能コンテナ : Functor
モナドは、様々なパラダイム(文脈)を統一された形で扱うためのもの
IO は IO。ただモナドとしてあるだけで、
モナドの代表としてIOがある訳ではない
モナドはただの型クラス (Haskell では)
糖衣構文 do がモナドを特殊にしている
リスト内包表記は do 記法の別表現
(現在はリストのみ)
Maybe は >>= で書くことが多いらしい
リストは内包表記で
パーサーは <$>, <*> で
do 使うのは IO くらいらしい
歴史的経緯により、Monad <|- Applicativce <|- Functor とはなっていない
Q: 「マップ可能コンテナで出来ることは?」
A: 「map map map いえーい」
型構築子も関数なので、例えば
data KV = MkKV String Int
とすると、
MkKV :: String -> Int -> KV
なので、
MkKV <$> ["a", "b"] <*> [1, 2]
とか出来る
- 練習問題
10.3 と TreeMap
問題自体はそんなに難しくなかったが、
Tree の定義を間違えていて、instance の種が合わないとか言われて
しばらく悩んでいた。
やっぱ種周りも知っておきたい。
- 懇親会
ビールがおいしい店!
炭酸的な感じがないビール。
Haskell の話とか OO の話とか、お仕事の話とか会社の話とか。
Jaav っぽいの
なんか bleis 先生が関数型っぽいライブラリを Java で作ってるっぽくて、自分も作ってみようかなーって適当に作ってたらとても残念な感じになったのでのっけてみる。
コードは rf0444's jaav at master - GitHub に。
よくもこんなキチ(ry
まずは Function インタフェース。これがないと始まりませんよねー。
public interface Fun<T, R> { R _(T x); }
メソッド名 _ ってw。Jaav もこうらしいw。
続いて Unit。
public enum Unit { _ }
_ 万能説ww。
Function の便利メソッド達。楽しすぎてやばい。(Fun的な意味でw)
public static <T1, T2, T3> Fun<Fun<T2, T3>, Fun<Fun<T1, T2>, Fun<T1, T3>>> compose() { return new Fun<Fun<T2,T3>, Fun<Fun<T1,T2>,Fun<T1,T3>>>() { @Override public Fun<Fun<T1, T2>, Fun<T1, T3>> _(final Fun<T2, T3> f1) { return new Fun<Fun<T1,T2>, Fun<T1,T3>>() { @Override public Fun<T1, T3> _(final Fun<T1, T2> f2) { return new Fun<T1, T3>() { @Override public T3 _(T1 x) { return f1._(f2._(x)); } }; } }; } }; } public static <T1, T2> Fun<Fun<? super T1, ? extends T2>, Fun<T1, T2>> cast() { return new Fun<Fun<? super T1,? extends T2>, Fun<T1,T2>>() { @Override public Fun<T1, T2> _(final Fun<? super T1, ? extends T2> f) { return new Fun<T1, T2>() { @Override public T2 _(T1 x) { return f._(x); } }; } }; }
Option も作ってみたけど、便利メソッドを関数型ちっくに書こうとして、型推論が出来ないようで全部自分で書くという残念なことに。(まぁこれはこれで面白いww)
public static <T1, T2> Fun<Fun<T1, Option<T2>>, Fun<Option<T1>, Option<T2>>> bind() { return new Fun<Fun<T1,Option<T2>>, Fun<Option<T1>,Option<T2>>>() { @Override public Fun<Option<T1>, Option<T2>> _(final Fun<T1, Option<T2>> f) { return new Fun<Option<T1>, Option<T2>>() { @Override public Option<T2> _(Option<T1> x) { return x.flatMap(f); } }; } }; } public static <T> Fun<Option<Option<T>>, Option<T>> join() { return Option.<Option<T>, T>bind()._(Funs.<Option<T>>id()); } public static <T1, T2> Fun<Fun<T1, T2>, Fun<Option<T1>, Option<T2>>> map() { return new Fun<Fun<T1,T2>, Fun<Option<T1>,Option<T2>>>() { @Override public Fun<Option<T1>, Option<T2>> _(final Fun<T1, T2> f) { return Option.<T1, T2>bind()._(Funs.<T1, T2, Option<T2>>compose()._(Option.<T2>unit())._(f)); } }; } public static <T1, T2> Fun<T2, Fun<Fun<T1, T2>, Fun<Option<T1>, T2>>> maybe() { return new Fun<T2, Fun<Fun<T1,T2>,Fun<Option<T1>,T2>>>() { @Override public Fun<Fun<T1, T2>, Fun<Option<T1>, T2>> _(final T2 x) { return new Fun<Fun<T1,T2>, Fun<Option<T1>,T2>>() { @Override public Fun<Option<T1>, T2> _(final Fun<T1, T2> f) { return Funs.<Option<T1>, Option<T2>, T2>compose()._(Option.<T2>getOrElse()._(x))._(Option.<T1, T2>map()._(f)); } }; } }; } public static <T1, T2 extends T1> Fun<Option<T2>, Option<T1>> cast() { return Option.<T2, T1>map()._(Funs.<T2, T1>cast()._(Funs.<T2>id())); }
あとはリスト系もやろうと思ったけどここまででおなかいっぱいになってやめたww。
reflexivityつおい
Require Import List. Theorem sum_10_eq_55 : fold_left (fun y x => y + x) (seq 1 10) 0 = 55. Proof. reflexivity. Qed.
ぅゎ、reflexivity っぉぃ。
続・Coqりさん Q.E.D.
Coqりさん 証明のかけら の続き (再挑戦)。
Require Import Arith. Fixpoint fib1 n:nat := match n with | 0 => 0 | 1 => 1 | S (S m as p) => fib1 p + fib1 m end. Fixpoint fib2 n a b:nat := match n with | 0 => a | S n => fib2 n b (a + b) end. Lemma plus_1_Sn : forall n:nat, n + 1 = S n. Proof. intro n. rewrite plus_n_O. rewrite plus_Snm_nSm. reflexivity. Qed. Lemma plus_2_SSn : forall n:nat, n + 2 = S (S n). Proof. intro n. rewrite plus_n_O. rewrite plus_Snm_nSm. rewrite plus_Snm_nSm. reflexivity. Qed. Theorem fib1_fib : forall n:nat, fib1 n + fib1 (n + 1) = fib1 (n + 2). Proof. intro n. rewrite plus_1_Sn. rewrite plus_2_SSn. simpl fib1. destruct n. reflexivity. ring. Qed. Theorem fib2_fib : forall n a b:nat, fib2 n a b + fib2 (n + 1) a b = fib2 (n + 2) a b. Proof. induction n. intros a b. reflexivity. intros a b. rewrite plus_Sn_m. rewrite plus_Sn_m. simpl. rewrite (IHn b (a + b)). reflexivity. Qed. Lemma fib1_eq_fib2_aux : forall n:nat, fib1 n = fib2 n 0 1 /\ fib1 (S n) = fib2 (S n) 0 1. Proof. induction n. split. reflexivity. reflexivity. destruct IHn. split. exact H0. rewrite <- plus_2_SSn. rewrite <- fib1_fib. rewrite <- fib2_fib. rewrite plus_1_Sn. rewrite <- H. rewrite <- H0. reflexivity. Qed. Theorem fib1_eq_fib2 : forall n:nat, fib1 n = fib2 n 0 1. Proof. intro n. destruct (fib1_eq_fib2_aux n). exact H. Qed.
で、できたー!
これまでは流れが追えるように . で書いてきたけど、そろそろ ; 使っていってもいいかもしれない。
SKK とか
K I = F と、S K K = I を証明してみる。
Definition I {A:Type} x:A := x. Definition K {A B:Type} (x:A) (y:B) := x. Definition F {A B:Type} (x:A) (y:B) := y. Definition S {A B C:Type} (x:A->B->C) (y:A->B) (z:A) := x z (y z). Theorem ki_f : forall (A B:Type)(x:A)(y:B), K I x y = F x y. Proof. intros A B x y. unfold K. unfold I. unfold F. reflexivity. Qed. Theorem skk_i : forall (A B:Type)(x:A), S K (K:A->B->A) x = I x. Proof. intros A B x. unfold S. unfold K. unfold I. reflexivity. Qed.
まぁ、展開するだけなんですけどね。