by shigemk2

当面は技術的なことしか書かない

第2期 第14回 H本読書会 in 秋葉原 #readhbon

readhbon.doorkeeper.jp

前回。

www.shigemk2.com

P192-P205

9.5 ToDo リストをもっと楽しむ

  • タスクの閲覧 追加 削除
  • マルチタスクリスト
  • エラー対応(例外処理で、ファイルのとじ忘れを開く)

9.6 ランダム性

  • ランダムジェネレータ
  • シード
  • ランダムは参照透過ではない
  • グローバル乱数ジェネレータを初期化
  • シードが一緒だとジェネレータを何回実行しても結果は一緒

gist.github.com

gist.github.com

gist.github.com

今回。

9.7 bytestring

  • Haskell の遅延評価のおかげで、リストに対するフィルタやマップとして他の言語における for や while ループが書ける
  • [1,2,3,4] のようなリストは 1:2:3:4:[] の構文糖衣(シンタックスシュガー)
  • 未評価の部分をサンク(thunk)といい、遅延された計算のこと。
  • リストはプロミス
  • 大きなファイルを読んだり、操作しようとしたときに、多くの場合このオーバーヘッドが問題→bytestringが用意されている

正格 bytestring と遅延 bytestring

  • 正格bytestringでは遅延性が完全に排除されており、サンクがない
  • 遅延bytestringは遅延評価されるが、リストほどは遅延しない
import qualified Data.ByteString.Lazy as B
import qualified Data.ByteString as S
  • pack :: [Word8] -> ByteString という型シグネチャを持つ pack
  • charをintにしたり、その逆をしたりする。なお、packには正格版と遅延版がある

gist.github.com

Prelude B S> B.pack [98..120]
"bcdefghijklmnopqrstuvwx"
Prelude B S> let by = B.pack [98,111,114,116]
Prelude B S> by
"bort"
  • 正格 bytestring を使ってファイルを読もうとすると、そのファイルの内容すべてがメモリ上に一度に読まれる
  • 遅延 bytestring なら、チャンクごとに読まれる
Prelude B S> B.cons 85 $ S.pack [80,81,82,83]

<interactive>:13:13:
    Couldn't match expected type `B.ByteString'
                with actual type `S.ByteString'
    In the return type of a call of `S.pack'
    In the second argument of `($)', namely `S.pack [80, 81, 82, 83]'
    In the expression: B.cons 85 $ S.pack [80, 81, 82, 83]

bytestring を使ったファイルのコピー

  • copy関数を書く
  • B.readFileを使ってコピー元ファイルの内容を読む
  • bracketOnError を使ってエラーハンドラをセットアップします
  • エラーが起こったときに何をすべきかを書きます。まずいことが起こったなら、ハンドルを閉じ、一時ファイルを削除
  • .hPutStr を使って内容を一時ファイルに書き出します。一時ファイルを閉じて、それをコピー先ファイル名に変更したら、望みの処理が完了

gist.github.com

第10章 関数型問題解決法

10.1 逆ポーランド記法電卓

  • RPNのかきかた
4 3 + 10 *

RPN 記法の式を計算

  • スタックの考え方
  • 最終的に演算で残るスタックの値は1つだけ
  • 10 4 3 + 2 * -

f:id:shigemk2:20150610204223p:plain

RPN関数を書く

  • 文字列を引数に取って、数を結果として返す関数

  • solveRPN :: String -> Double

  • リスト化 ["10","4","3","+","2","*","-"]
  • 畳み込み
  • 最終的にひとつの値が返る

  • アキュムレータは[]

  • ポイントフリースタイルを使う

RPN 関数を書く

gist.github.com

  • スタック積みでいろいろ演算。

Haskell の read 関数で、文字列から代数的データ型へ変換 - 導出インスタンスを使って | すぐに忘れる脳みそのためのメモ

演算子を追加しよう

  • 比較的容易に拡張できるが、耐障害性はかなり低い

gist.github.com

10.2 ヒースロー空港からロンドンへ

  • 最短経路を出力するプログラムをつくる

f:id:shigemk2:20150610210458p:plain

問題を解くコツ

  • Haskellはいったんわすれる
  • Haskellでどう表現するか考える
  • データ構造をつくりHaskell操作することを考える

最短経路を計算する

(シンプルに描かれた道路網の絵)

f:id:shigemk2:20150610210845p:plain

  • 最初のルートの最短経路を計算(比較)
  • 同じ手続きで次のルートを計算(比較)
  • これを繰り返す
  • 繰り返していけば、最短経路が分かる

  • AとBを比較してよりよいものを選び、それを繰り返す

  • 最短経路を手で求める方法は分かりました。もし十分な時間と、紙と鉛筆があれば、どんなに多くのセクションがある道路網でも最短経路を求められる

道路網を Haskell で表現する

幹線道路A 幹線道路B 橋 の順に並べてみる

  • 50, 10, 30
  • 5, 90, 20
  • 40, 2, 25
  • 10, 8, 0

これを、Haskellのデータ型で表現する(Intのトリプルではなく、独自データ型=代数的データ型で、表現する)

トリプルにしないのは、汎用性を高めるため。

data Section = Section
deriving (Show) {
  getA :: Int, getB :: Int, getC :: Int
}
type RoadSystem = [Section]

最短経路関数を求めよ!

gist.github.com

得られる出力結果が、同じになることが確認できる

[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]
print $ sum.map snd $ optimalPath heathrowToLondon

ってやれば、75って返るので、最短時間は75分だね☆ってはっきりわかんだね。

入力から道路網を受け取る

いろいろ関数を追加する。

gist.github.com