スタートHaskell 2

関数型問題解決法

@dekokun

## 自己紹介 * @dekokun * Web企業でPHPとかPerlとかNodeとか * 最近Jenkinsが好き * 静的な型付け言語は手慰みにCやJavaをやったこともあるがHaskellがほぼ初めて！ * 静的型付け言語、楽しいですね！！！ * Haskell製のブログエンジン、Hakyleを使って作ったブログとかあるし見てね！

## 逆ポーランド記法電卓

### 逆ポーランド記法(RPN)とは * こんな感じ * "1 2 +" -> 1 + 2 * "1 2 + 10 *" -> (1 + 2) * 10 * ()が不要ですね。素敵ですね。

### 計算方法 * 左から右に読む * 数だったらスタックに積む * 演算子だったらスタックから数を取り出し演算し、結果をスタックに積む * 最後にスタックに残った数が答え

## 実際に自分の頭で計算してみる * "10 4 3 + 2 * -"

### まずはスタックに10を積む * "10 4 3 + 2 * -" * スタック:10

### 次のアイテムは4なのでこれも
スタックに積む * "4 3 + 2 * -" * スタック:4 10

### 次も3なのでスタックに * "3 + 2 * -" * スタック:3 4 10

### 次は2項演算子なのでスタックから2個取り出して計算し結果をスタックに積む * "+ 2 * -" * 4 + 3 = 7 * スタック:7 10

### 2をスタックに * "2 * -" * スタック:2 7 10

### 掛け算 * "* -" * 7 * 2 = 14 * スタック:14 10

### 引きましょう * "-" * 10 - 14 = -4 * スタック:4

### なくなった * "" * スタック:4 お疲れ様です。答えは4です

### RPN関数を作成 * まずは型 * 文字列をとって数を返す * 倍精度浮動少数で


            solveRPN :: String -> Double

### 自分の頭ではどうやったっけ 1. スペース区切りの文字列をリストに分割 -> words 1. リストを走査しスタックを更新 -> 畳込み * 今回はリストを左から走査するので左畳込み 1. スタックはどう表現するか * リストの先頭をスタックの先頭に * リストはリストの先頭の操作が得意ですので、出入りの激しいスタックの先頭をリストの先頭に対応づけましょう

### 関数の一部


          solveRPN :: String -> Double
          solveRPN expression = head (foldl foldingFunction [] (words expression))
            where foldingFunction stack item = ....

* ポイントフリースタイルに向けて書きなおす


          solveRPN expression = head $ foldl foldingFunction [] $ words expression
            where foldingFunction stack item = ....

* 更に↓


          solveRPN expression = head . foldl foldingFunction [] $ words expression
            where foldingFunction stack item = ....

* 更に↓


          solveRPN = head . foldl foldingFunction [] . words
            where foldingFunction stack item = ....

### 作ってみよう * 作ったり使ったりしてみよう * 続きはVimで

### 失敗する場合も考えたいですね * 現在は不正な文字列が渡されるとプログラムが落ちる * 14章でMaybeモナドを学ぶと、失敗した際にNothingを返すなど綺麗に失敗させることができるようになりますので早く学びましょう

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

* とにかく早くヒースロー空港からロンドンに行きたい * ただしレンタカーで

(MacのPreview.appで作りました)

上記の図が下記文字列に対応 * 50 10 30 5 90 20 40 2 25 10 8 0 * 本当は、改行で区切られてます

## こんな感じで解く 1. 手で解く 2. 手で解いた時に使ったデータ構造をHaskellで表現する 3. そのデータ構造をどのようにHaskellで操作するか考えるまぁ、このやり方が常にうまくいくわけではないでしょうが、
常に何がしかの手がかりは得られる方法ですよね

## これからは教科書の
図を見ましょう * Preview.app、疲れた

## 求めましょう * A1に行く最短経路とかかる時間 * B Cで40分 * B1に行く最短経路とかかる時間 * Bで10分

## A1,B1への時間を元に、以下を求めましょう * A2に行く最短経路とかかる時間 * A1まで40分 + Aで45分 * B2に行く最短経路とかかる時間 * A1まで40分 + A Cで65分

## 以下繰り返し (明らかに再帰ですね) 最後に、A4とB4の所要時間を比べればめでたしめでたし

## 手で解く方法は分かった * 続きはVimでやりましょう * ghciも交えながら * [toLondon.hs](https://github.com/dekokun/StartHaskell2-Chapter10/blob/master/toLondon.hs)参照

## 自分で道路を生成しよう * [badMakeRondomPath.hs](https://github.com/dekokun/StartHaskell2-Chapter10/blob/master/badMakeRondomPath.hs) * [makeRandomPath.hs](https://github.com/dekokun/StartHaskell2-Chapter10/blob/master/makeRandomPath.hs) #### スタックオーバーフローも起こしてみよう

## 正格評価に * foldlをfolol'に * sumをfolol' (+) 0に * [notLazyToLondon.hs](https://github.com/dekokun/StartHaskell2-Chapter10/blob/master/notLazyToLondon.hs)

## 最適化オプションをつけてコンパイル $ ghc --make -O