一部の値を変更したレコード

Database.Persist.MySQLの設定を調べていて、こんな記述を発見。

defaultConnectInfo :: ConnectInfo
Default information for setting up a connection.
(中略)
Use as in the following example:

connect defaultConnectInfo { connectHost = "db.example.com" }
Database.Persist.MySQL

レコードってこんな使い方できたっけ?
ということで、試しにいろいろやってみた。

  • Hoge.hs
data Hoge = Hoge { hoge :: Int, piyo :: String } 
 deriving Show

で、

> :l Hoge.hs
[1 of 1] Compiling Main             ( Hoge.hs, interpreted )
Ok, modules loaded: Main.

> let aa = Hoge { hoge = 9, piyo = "aaa" }
> aa
Hoge {hoge = 9, piyo = "aaa"}

> aa { hoge = 22 }
Hoge {hoge = 22, piyo = "aaa"}

> aa { piyo = "xx" }
Hoge {hoge = 9, piyo = "xx"}

> aa
Hoge {hoge = 9, piyo = "aaa"}

> aa { piyo = "xx" } { hoge = 0 }
Hoge {hoge = 0, piyo = "xx"}

> aa { piyo = "xx" } { hoge = 0 } { piyo = "uuu" }
Hoge {hoge = 0, piyo = "uuu"}

> hoge aa
9

> hoge aa { piyo = "xx" } { hoge = 0 } { piyo = "uuu" }
0

へ〜。

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 "(パッケージ名)" ~) を書ける。

他言語系

CPP

Cプリプロセッサの構文が使える。

#define とか #if とか #include とか。

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 になってくれた。

Git 導入

家のデスクトップに入れてた Git を新しくしようと思って、ついでに入れ方を残しておこうと思って、書いてみる。
OS は Windows 7。多分 XP でも大丈夫。
cygwin とかは入ってない想定。7z は入ってる想定。

  • 入ってた Git を削除

前入れたときはインストーラから入れていたので、普通にあんいんすこ。

  • Git DL

msysgit から、最新の PortableGit をDLする。
2/17 現在、一番新しそうな PortableGit-1.7.9-preview20120201.7z を落とした。

  • 適当なところに解凍する

パスにスペースや日本語は入ってないほうがいいと思う。
自分は、F:\Programs の下に解凍。会社では、C:\libs の下にしている。

  • 日本語対応
    • less 書き換え

Downloading less から落とす。
・・・のだが、バイナリがない・・・
http://www.greenwoodsoftware.com/less/less436w.zip
から直接落とすことはできるので、そこから落とした。
解凍して出てくる、less.exe を、bin/ の中へ。(上書き)

nkf Network Kanji Filter for Win33 (自家用) から、nkf-2.0.8b.bin.tar.gz をDL。
解凍して出てくる、nkf.exe を、bin/ の中へ。

    • 設定書き換え

etc/inputrc の

# disable/enable 8bit input
set meta-flag on
set input-meta on
set output-meta off
set convert-meta on

この辺を、

# disable/enable 8bit input
set meta-flag on
set input-meta on
#set output-meta off
set output-meta on
#set convert-meta on
set convert-meta off

こうする。


etc/profile に

alias ls='ls --color=auto --show-control-chars'
export GIT_PAGER="nkf -s | less"

を追記。

  • ckw 導入

ckw-mod より、ckw-mod-0.9.0-d2.zip をDL。
解凍して出てくる、ckw.exe と ckw.cfg を、bin/ の中へ。
単体でも便利なので、どこかにコピーして使ってもいい。


コピーした ckw.cfg を書き換える。
必須箇所は、

Ckw*exec:  cmd.exe
Ckw*chdir: c:\

ここを、

Ckw*exec:  sh.exe --login -i
!Ckw*chdir: c:\

こう。
自分が書き換えたのはこんな感じ。

Ckw*title: ckw[git sh]
Ckw*exec:  sh.exe --login -i
!Ckw*chdir: c:\

Ckw*scrollHide:  no
Ckw*scrollRight: yes
Ckw*internalBorder: 1
Ckw*lineSpace: 0
Ckw*topmost: no
Ckw*transp: 200
!Ckw*transpColor: #000000

Ckw*font: MS Gothic
Ckw*fontSize: 12

Ckw*geometry: 160x50
Ckw*saveLines: 500
  • git 設定

ホームディレクトリに .gitconfig ファイルを作る。
Windows だと エクスプローラからは . から始まるファイルを作れないので、
さっきコピーした ckw.exe を開いて、

touch ~/.gitconfig

とやればファイルが作られる。
ホームディレクトリは、Vista 以降だと、C:\Users\(ユーザ名) 的な。個人用フォルダとかいう所。
XP だと、C:\Documents and Settings\(ユーザ名) 的な。


中身は、最低でもこんな感じ。

[user]
	name = (名前)
	email = (メールアドレス)

自分のやつは、

[user]
	name = rf
	email = (略)
[core]
	editor = vim -c \"set fenc=utf-8\"
[color]
	ui = auto
[alias]
	adda = add -A
	st = status
	di = diff
	co = checkout
	br = branch
	cl = clone
	ci = commit
	cia = commit -a
	cim = commit --amend
	rs = reset
	rh = reset --hard
	rv = remote -v
	ra = remote add
	ru = remote update --prune
	log-all = log --graph --all --color --pretty='%x09%h %cn%x09%s %Cred%d%Creset'
	la = log --graph --all --color --pretty='%x09%h %cn%x09%s %Cred%d%Creset'

こんな感じ。


他、.bashrc や .vimrc など書いておくといいかも。
自分の .vimrc は こんな感じ
.bashrc は

alias vr='vi -R'
alias ll='ls -l'
alias la='ls -a'
alias lla='ls -la'

alias gitk='gitk --all &'

こんな感じ。

  • 右クリックの設定

エクスプローラからフォルダ右クリックして開けたら便利だよね。

レジストリエディタ開く (Windows + R → regedit)
→ HKEY_CLASSES_ROOT\directory\shell の中に適当にキーを作る。(git とか)
→ 作ったキーの (既定) の値を、右クリックしたときに表示したいやつにする。「git で開く (&G)」とか。
→ 作ったキーの中に、command というキーを作成
→ command の (既定) の値を、「"(コピーしたckw.exeのフルパス)" -cd "%V"」にする。
  Vista 以降なら、ckw.exe を Shift 押しながら右クリック → パスとしてコピー とか使えて便利。

エクスプローラから、別にフォルダ選ばなくても、何もないところ右クリックしても開けたら便利だよね。(Vista 以降のみ)

レジストリエディタ開く (Windows + R → regedit)
→ HKEY_CLASSES_ROOT\directory\Background\shell の中に適当にキーを作る。(git とか)
→ 作ったキーの (既定) の値を、右クリックしたときに表示したいやつにする。「git で開く (&G)」とか。
→ 後は同じ。
  • 使ってみる

適当にフォルダ作って、git init 打って、適当にファイル作って、コミットしてみる。
コミットメッセージに日本語入れてコミットしてみて、(utf-8 で コミットメッセージが打てればおk)
git log とか gitk とかやってみて、一連の過程で化けなければ、おk。


パスに日本語が含まれていると、たまに毎回変な文字が表示されることがあるが、特に実害が出てないのでほったらかし。

The End of Start Haskell

1/28 に、第6回 スタートHaskell に行ってきました!

また1週間かかってしまった・・・遅延評価だから仕方がない (キリッ

  • 12章 遅延評価 解説

@imsuten
http://www.intransient.info/materials/Programming_in_Haskell_12/Programming_in_Haskell_12.html5.html#landing-slide


最内簡約
  (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

@nagaet
https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B6eWGr-ow12sOGUxMDVmMzItYzQ3Ny00NTczLTg5MzgtZWViNTFkZGVjNzk5&hl=ja

ひたすら数学的帰納法が続く。

    • 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 の中身をほどくのも、その足し算も遅延される
    • Stream の型
      • susp の代わりに Lazy.t を使う


トップレベルの 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 すばらしい。
遅延リストはいいぞ。


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 が残念に感じるよねって話とか、
JavaEclipse が型推論してくれるんだ(キリッ)とか、
Eclipse の設定やショートカットとか、
お仕事の話とか。

  • 次の日

まとめようと思ったけど睡魔に負けた・・・

第5回 スタートHaskell

12/5 に、第5回 スタートHaskell に行ってきました!

会社の先輩 (@seizans) に誘われて、久しぶりの勉強会 & 初スタートHaskell

  • 前日

本の中身をざっくりみた後、演習をやっておこうとした。
環境をみてみると、Haskell Platform 入れてなくて、
Mac Ports の ghc が入っていたので、
そっちはアンインストールして、Haskell Platform を入れようとしたが、
家のネットが調子悪く、とりあえす今回はこのままで行くことに。


割と夜遅くなったので、練習問題と関係ありそうな演習はなんとか終わらせて寝た。

  • 当日

品川駅で迷ったり、大森駅で逆方向から出て迷ったりしたけど、なんとか辿り着けた。


togetter - スタートHaskell第5回 まとめ : http://togetter.com/li/222626

@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 の話とか、お仕事の話とか会社の話とか。