top page > computer > haskell > web_lecture > for_programmer > calculator.html
更新日:
文責: 重城良国

電卓をエミュレートする

(工事中 50%)

はじめに

メモリ機能つきの電卓を関数でエミュレートしてみよう。

計算の例

以下の計算をメモリ機能つきの電卓で計算する。

(3 * 4 + 2 * 5) * 7

以下のようにボタンを押す。

3 * 4 M+ C 2 * 5 M+ C MR * 7

電卓はメモリ内の記憶を状態として持っている。

仕様

それぞれの操作を

関数として実装する。実際の電卓とは異なるが

M+とMR

M+とMRとを表す関数のそれぞれの型は以下のようになる。

mplus :: Int -> Int -> ((), Int)
mrecall :: () -> Int -> (Int, Int)

関数mplusでは返り値の画面の表示の部分が()となり、関数mrecallでは引数の画面の表示の部分が()となっている。表示がないということを()で表現している。

画面を変化させる

画面を変化させる関数を作る。(Int -> Int)型の関数を変換して作ることにする。この関数はメモリは変化させない。

arrC :: (Int -> Int) -> (Int -> Int -> (Int, Int))

この関数によってたとえば'+ 3'のように押したときの動きを作ることができる。さらに、たとえば画面がクリアされている状態で5を押したときの動きを作るために(() -> Int)型の関数も変換できるようにしたい。

arrC :: (() -> Int) -> (() -> Int -> (Int, Int))

これら2つの型をひとつの型で表すと

arrC :: (a -> Int) -> (a -> Int -> (Int, Int))

となる。Intや()を型変数aとして一般化した。さらに画面のクリアも(Int -> ())型の関数を関数arrCで変換して作りたい。このような使いかたをするときには関数arrCは

arrC :: (Int -> ()) -> (Int -> Int -> ((), Int)

のようであればいい。よって画面のクリアにも使えるように関数arrCをさらに一般化すると

arrC :: (a -> b) -> (a -> Int -> (b, Int))

となる。この型を見ると関数arrCはa型の値をとりb型の値を返す関数を、a型の値と整数値をとりb型の値と整数値を返す関数に変換すていることがわかる。

必要な関数

ここまでで見てきた関数は以下の3つとなる。

mplus :: Int -> Int -> ((), Int)
mrecall :: () -> Int -> (Int, Int)
arrC :: (a -> b) -> a -> Int -> (b, Int)

関数mplus

calculator.hs

関数mplusは

mplus :: Int -> Int -> ((), Int)
mplus x m = ((), x + m)

となる。第1引数が画面の表示であり第2引数はメモリのなかみだ。返り値であるタプルの第1要素が画面の表示であり第2要素がメモリのなかみだ。

関数mrecall

関数mrecallは

mrecall :: () -> Int -> (Int, Int)
mrecall _ m = (m, m)

となる。第1引数は画面の表示である。mrecallを呼び出すときには必ず画面はクリアされている必要がある。第2引数はメモリのなかみだ。結果のタプルの第1要素は画面の表示であり第2要素はメモリのなかみだ。メモリの中身はそのままであり、画面の表示はクリア状態からメモリのなかみの値へと変化する。

試してみる

ここまでの関数を試してみよう。

% ghci calculator.hs
*Main> mplus 3 0
((), 3)
*Main> mplus 4 8
((), 12)
*Main> mrecall () 12
(12, 12)

画面表示が3でメモリが0のときにM+すると画面表示はクリアされメモリは3になる。画面表示が4でメモリが8のときにM+すると画面表示はクリアされメモリは12になる。画面表示がクリアされメモリが12のときにMRすると画面表示は12となりメモリも12のままとなる。

関数arrC

関数arrCの定義は

arrC :: (a -> b) -> a -> Int -> (b, Int)
arrC f x m = (f x, m)

となる。画面表示xは与えられた関数fで変換する。メモリのなかみmはそのまま返す。

試してみる

画面表示がクリアされているときに数字キーを打ったところをエミュレートする。

*Main> :reload
*Main> arrC (const 8) () 4
(8,4)
*Main> arrC (const 11) () 32
(11,32)

画面表示はクリアされメモリは4のときに8を打つと画面表示は8となりメモリは4のままとなる。画面表示はクリアされメモリは32のときに11を打つと画面表示は11となりメモリは32のままとなる。

画面に数字が表示されている状態で演算キーと数字キーを打つ。

*Main> arrC (* 3) 2 5
(6,5)
*Main> arrC (+ 8) 7 23
(15,23)

ひとつめの例では画面表示が2でメモリが5のときに'* 3'を入力した。ふたつめの例では画面表示が7でメモリが23のときに'+ 8'を入力した。メモリのなかみを変えずに画面をそれぞれの関数で変化させているのがわかる。

画面の表示は多相的

画面をクリアしてみよう。

*Main> arrC (const ()) 37 8
((),8)

画面がクリアされた状態を()で表現した。整数が表示されている状態はInt型で表現される。そのために画面の表示を表す部分は多相的にした。普通の電卓以上のことができる。たとえば偶数かどうかをチェックすることができる。

*Main> arrC even 4 7
(True,7)

画面の表示はTrueとなる。

型Calc

今まで扱ってきた関数は共通の構造を持っている。共通する部分をとりだすと

a -> Int -> (b, Int)

となる。a, bはそれぞれ直前と直後の画面の値である。ひとつめのIntは直前のメモリの値であり、ふたつめのIntは直後のメモリの値だ。この関数の型に別名をつけておく。

type Calc a b = a -> Int -> (b, Int)

それぞれの関数の型は

mplus :: Calc Int ()
mrecall :: Calc () Int
arrC :: (a -> b) -> Calc a b

となる。

組み合わせる

計算の部品はそろった。これらを組みあわせていこう。組みあわせる関数pipeCの型は

pipeC :: Calc a b -> Calc b c -> Calc a c

となる。画面の値をaからbにする計算と画面の値をbからcにする計算とをつないで、画面の値をaからcにする計算をつくる。定義は

(f `pipeC` g) x m = let (x', m') = f x m in g x' m'

となる。画面の値xとメモリの値mとを関数fで変化させる。その結果である画面の値x'とメモリの値m'を関数gに与える。

*Main> :reload
*Main> (arrC (const 3) `pipeC` arrC (* 2)) () 23
(6,23)
*Main> (arrC (const 4) `pipeC` mplus) () 3
((),7)

画面がクリアされていてメモリが23のときに'3 * 2'をした例と画面がクリアされていてメモリが3のときに'4 M+'をした例だ。

複雑な計算

最初の例は

(3 * 4 + 2 * 5) * 7

だった。キーの押しかたは

3 * 4 M+ 2 * 5 M+ MR * 7

である。これをエミュレートしてみよう。

example :: Calc () Int
example =
arrC (const 3) `pipeC`
arrC (* 4) `pipeC`
mplus `pipeC`
arrC (const 2) `pipeC`
arrC (* 5) `pipeC`
mplus `pipeC`
mrecall `pipeC`
arrC (* 7)

*Main> :reload
*Main> example () 0
(254,22)

初期状態は画面はクリアされていてメモリは0である。

型State

型Calcは

type Calc a b = a -> Int -> (b, Int)

のように定義されている。型Stateを

type State b = Int -> (b, Int)

のように定義する。

Calc a b == a -> State b

のような関係となる。型(a -> b)と型(a -> State b)を比較すると

であり、画面の値の変化にメモリの値の変化が追加されていることがわかる。

pipeCの型を型Stateを使って書いてみる。

pipeC :: (a -> State b) -> (b -> State c) -> (a -> State c)

画面とメモリを変化させる関数をつないでいる。メモリの変化についてはState型のなかにかくされている。第1引数の'a ->'と返り値の'a ->'とは消せる。

bindC :: State b -> (b -> State c) -> State c

となるような関数bindCと関数pipeCとは情報としては同じものとなる。

関数bindC

関数bindCの定義は

bindC :: State a -> (a -> State b) -> State b
(f `bindC` g) m = let (x, m') = f m in g x m'

となる。関数fに状態mを与え結果の値xと状態m'をgに与える。

関数retC

同様のことがarrCにもできる。

arrC :: (a -> b) -> (a -> State b)

retC :: b -> State b

とできる。関数retCの定義は

retC x m = (x, m)

となる。状態は変化させずに表示を値xとする。

計算例を書きなおす

pipeCとarrCではなくbindCとretCで計算例を書きなおしてみよう。

example :: State Int
example =
retC 3 `bindC`
(retC . (* 4)) `bindC`
mplus `bindC`
const (retC 2) `bindC`
(retC . (* 5)) `bindC`
mplus `bindC`
mrecall `bindC`
(retC . (* 7))

*Main> :reload
*Main> example 0
(154,22)

整形

同じことを以下のように整形して書いてみる。(本当は同じじゃない。そこらへんをどう説明するか。あるいはどうごまかすか) (ここの説明でモナド則をこっそり説明してしまうのもひとつの方法だ)

example :: State Int
example =
retC 3 `bindC` \x ->
retC (x * 4) `bindC` \y ->
mplus y `bindC` \_ ->
retC 2 `bindC` \z ->
retC (z * 5) `bindC` \w ->
mplus w `bindC` \_ ->
mrecall () `bindC` \v ->
retC (v * 7)

*Main> :reload
*Main> example 0
(154,22)

まとめ

メモリつき電卓の例を見た。画面の値とメモリの値のペアを次々と変換していく。画面の値にだけ注目しメモリの値を隠すことができる。以下の2つの関数で変換を部品としてつないでいける。

pipeC :: (a -> State b) -> (b -> State c) -> (a -> State c)
arrC :: (a -> b) -> (a -> State b)

これらの関数はより単純な関数のペアに置きかえられる。

bindC :: State a -> (a -> State b) -> State b
retC :: a -> State a

「失敗する関数をつなぐ」へもどる 「共通する枠組み: モナド」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics