<   2013年 04月 ( 25 )   > この月の画像一覧

Programming with Arrows 読解 目次

Programming with Arrows 読解 1 --- 1 Introduction
Programming with Arrows 読解 2 --- 1.2 The Arrow class
Programming with Arrows 読解 3 --- 1.3 Arrows as computations
Programming with Arrows 読解 4 --- 2 The Arrow classes
Programming with Arrows 読解 5 --- 2.2 Arrows and conditionals
Programming with Arrows 読解 6 --- 2.3 Arrows and feedback
Programming with Arrows 読解 7 --- 2.3 Arrows and feedback (続き)
Programming with Arrows 読解 8 --- 2.4 Higher order arrows
Programming with Arrows 読解 9 --- 3 Pointed arrow programming
Programming with Arrows 読解 10 --- 3.2 Naming intermediate values
Programming with Arrows 読解 11 --- 3.3 Recursive arrow bindings
Programming with Arrows 読解 12 --- 3.4 Command combinators
[PR]
by tnomura9 | 2013-04-27 21:03 | Haskell 記事リスト | Comments(0)

Programming with Arrows 読解 12

3.4 Command combinators

これまで comand による記述法を導入してきた。そこから自然に command のコンビネータは使えないのだろうかという発想が出てくる。しかし、command は first-class expressions ではないので、command を引数とするコマンド・コンビネータは定義できない。

しかし、do 記法の値は環境 environment から出力への射の Arrow 型であるから、これに対しては Arrow 型のコンビネータを使うことができる。

環境という言葉は耳慣れないかもしれないが、たとえば do 記法でプログラムを作るときは次のような形になる。

foo = proc a -> do
  b <- command_1 -< a
  c <- a && b
  rerutnA -< c

この時 foo の値は Arrow 型になるが、foo の入力は a で出力は c になる。入力の a は do 記法の中でいろいろ加工されて利用されるので、do 記法内の環境(変数)と考えることができる。したがって、foo という Arrow 型の値は入力は環境 a から出力 c への射であるといえる。

ところで、Arrow 型のコンビネータが全てコマンド・コンビネータとして使えるわけではない。というのは、proc キーワード以下のブロックでは、この do 記法による Arrow は全て入力が a という環境になるからだ。つまり、proc 以下のブロックでは、コマンド・コンビネータの引数の Arrow (射) は環境 a を共通の入力にしている。しtがって、コマンド・コンビネータの型は次のように、Arrow の入力が一様に環境 env でなければならない。

arr env a -> arr env b -> ... -> arr env c

例えば (&&&) と (|||) の型を比べてみると、

(&&&) :: Arrow arr => arr a b -> arr a c -> arr a (b,c)

(|||) :: Arrow arr => arr a c -> arr b c -> arr (Either a b) c

となるから、(&&&) は次のようにコマンド・コンビネータとして使うことができるが、(|||) はそうではない。

example = proc x ->
      do returnA -< x
  &&& do delay 0 -< x

Prelude> :s sf.ghci
[1 of 1] Compiling Main ( SF2.hs, interpreted )
Ok, modules loaded: Main.
*Main> let
*Main| example = proc x ->
*Main|       do returnA -< x
*Main|   &&& do delay 0 -< x
*Main|
*Main> runSF example [1..5]
[(1,0),(2,1),(3,2),(4,3),(5,4)]

上の記述法は Haskell のオフサイド・ルールを使ったトリッキーな書き方だ。次のように1行で書くと &&& が returnA -< の一部と解釈されて文法エラーになる。

*Main> let example2 = proc x -> do returnA -< x &&& do delay 0 -< x

この場合も括弧を適切に使用すれば大丈夫だ。

*Main> let example2 = proc x -> (do returnA -< x) &&& (do delay 0 -< x)
*Main|
*Main> runSF example2 [1..5]
[(1,0),(2,1),(3,2),(4,3),(5,4)]

&&& が中置演算子の場合は文法の曖昧さは起きないが、(&&&) のように前置演算子として使うと、(&&&) が一般の関数なのか、コマンド・コンビネータなのか判別がつかない。このような場合は、コマンドをバナナ括弧 (| ... |) で囲うことで (&&&) がコマンド・コンビネータであることを明示できる。

*Main> let example3 = proc x -> (| (&&&) (returnA -< x) (delay 0 -< x) |)
*Main|
*Main> runSF example3 [1..5]
[(1,0),(2,1),(3,2),(4,3),(5,4)]

バナナ括弧記法からの翻訳規則は次のようになる。

proc pat -> (| e c1...cn |) ------> e (proc pat->c1)...(proc pat->cn)

高階関数愛好者の立場からは、コマンド・コンビネータによる値が commnad だけでなく、パラメータつきコマンド parametarised command も戻してほしいと考えるだろう。言い換えると、「command を戻値として返す関数」を戻値にしたいということだ。

パラメータつきコマンドの型は arr (env, a) b のようになる。env は proc ブロックの中で共通の環境の値だ。a がパラメータで、b が出力になる。こういうパラメータつきのコマンド型はラムダ記法で作ることができる。\x -> cmd の形の command は arr (env, a) cmd のように、現在の環境とパラメータのペアを入力とし出力が cmd であるような command になる。

パラメータつきコマンドの翻訳規則は概念的には次のようになる。

proc pat -> \x -> c ------> proc (pat,x) -> c

上の proc pat -> \x -> c とは別に、proc pat -> c e のように、command c が値の引数をとるような場合も考えられる。この場合は環境と値のペア (pat, e) を作りそれを command c に引き渡すというやり方をとる。proc pat -> c e の翻訳規則はつぎのようになる。

proc pat -> c e ------> arr (\pat -> (pat,e)) >>> proc pat -> c

これらの翻訳規則の詳細は GHC の文書を参照してほしい。

さて、パラメータつきコマンドの例として、map に相当する働きをもつコマンド・コンビネータを記述してみる。Arrow 型の map 関数である mapA の型は次のようになる。

mapA :: ArrowChoice arr => arr a b -> arr [a] [b]

しかし、これでは出力の Arrow の入力(環境)が a から [a] に変わってしまうので、command には使えない。そこで、command の map 関数では引数の Arrow と値の Arrow の入力をともに環境と値のペア (env,a) にする。こうすれば、同じ環境 (env) を共有するので問題ない。

mapC :: ArrowChoice arr => arr (env,a) b -> arr (env,[a]) [b]
mapC c = proc (env,xs) ->
  case xs of
    [] -> returnA -< []
    x:xs’ -> do y <- c -< (env,x)
            ys <- mapC c -< (env,xs’)
            returnA -< y:ys

ghci で実験すると次のようになった。まず、mapC を定義する。

*Main> let
*Main| mapC :: ArrowChoice arr => arr (env,a) b -> arr (env, [a]) [b]
*Main| mapC c = proc (env,xs) ->
*Main|   case xs of
*Main|     [] -> returnA -< []
*Main|     x:xs' -> do
*Main|       y <- c -< (env,x)
*Main|       ys <- mapC c -< (env,xs')
*Main|       returnA -< y:ys
*Main|

次に mapC を使って Arrow 型の example2 を定義した。

*Main> let
*Main| example2 = proc (n,xs) ->
*Main|   (| mapC (\x -> do delay 0 -< n
*Main|              &&& do returnA -< x) |) xs
*Main|

マップの引数の command は、(n, xs) を環境入力にとり、n の delay と xs の各要素とのペアからなるリストを作る。

最後に runSF example2 を (n,xs) ペアを要素とするリストに関数適用する。

*Main> runSF example2 [(1,[1,2]),(3,[4]),(5,[6,7])]
[[(0,1),(0,2)],[(1,4)],[(3,6),(1,7)]]

結果は 0 と [1,2] の要素とのペアのリスト [(0,1),(0,2)]、1 と [4] の要素とのペアのリスト [(1,4)]、3 と 6、1 と 7 とのペアのリストを要素とするリスト [[(0,1),(0,2)],[(1,4)],[(3,6),(3,7)]] が戻り値となる。

この用例は複雑で用途が掴みにくいと本文にも書いてあるが、とにかく、モナドでプログラムするときの道具に似たものが Arrow にも導入されている事が分かる。

『 Programming with Arrows 』の4章以降は Arrow のプログラムの応用例について述べられているが、管理人の基礎知識の範囲をはるかに超えているようで全くわからなかった。ここまでの記事で、噂に聞く
Arrow がどういうものかというのが何となくわかったような気になったのでこのシリーズを終了する。

Arrows の何がありがたいのか、今でもさっぱりわからないが、たとえば arr (*2) という Arrow が、次のように関数でも、Kleisli Arrow でも、SF (stream function) でも同じように使えてしまうのが便利に思えた。

*Main> (arr (*2)) 2
4
*Main> runKleisli (arr (*2)) 2
4
*Main> runSF (arr (*2)) [1,2,3,4,5]
[2,4,6,8,10]

抽象的なプログラムは、いろいろな状況にプログラムをほとんど変更せずに利用できる。Haskell を使い始めて楽しいと思えることのひとつだが、Arrow もそのような工夫の一つなのだろう。将来、使いこなせるようになったらまた、Haskell プログラミングのちがった楽しみ方を見つけることができるようになるのかもしれない。

<< 目次
[PR]
by tnomura9 | 2013-04-26 18:39 | Haskell | Comments(0)

Programming with Arrows 読解 11

3.3 Recursive arrow bindings

ghci で SF (stream functions) を使えるようにするには :l SF2.hs、:set -Xarrows、:set +m の操作を前準備でしないといけない。結構めんどうだが、これらのコマンドをファイルに書き込んでおけば :script コマンドで ghci の設定をすることができる。

そこでつぎのコマンドをファイル sf.ghci に記述してスクリプトファイルを作成した。

:load SF2.hs
:set -XArrows
:set +m

そうしておいて ghci を起動した後、:script sf.ghci でスクリプトファイルを読み込めば、簡単に ghci の設定ができる。

Prelude> :s sf.ghci
[1 of 1] Compiling Main ( SF2.hs, interpreted )
Ok, modules loaded: Main.

閑話休題、本文に戻ろう。

point-free style でプログラムを記述するときも、再帰的定義は必須だった。arrow 記法でも再帰的定義をするためのキーワードが用意されている。point-free style で再帰的定義をするときは loop 関数を用いた。arrow 記法の場合は loop 関数の役割を rec キーワードが果たす。

point-free style で記述したフリップフロップ回路のプログラムを再掲する。

flipflop =
  loop (arr (\((reset,set),~(c,d)) -> ((set,d),(reset,c))) >>>
    nor *** nor >>>
    delay (False,True) >>>
    arr id &&& arr id)

point-free style の loop 関数に相当するものは、arrow 記法では rec キーワードだ。rec キーワード以下のブロックは動作が再帰する。上のフリップフロップは arrow 記法では次のようになる。

flipflop :: ArrowCircuit arr => arr (Bool,Bool) (Bool,Bool)
  flipflop = proc (reset,set) -> do
      rec c <- delay False -< nor reset d
          d <- delay True -< nor set c
      returnA -< (c,d)
    where nor a b = not (a || b)

上のプログラムでArrowCircuit クラスの多相関数は delay だけだ。SF2.hs ファイルには自前の delay 関数があるので、SF を ArrowCircuit のインスタンスにしなくても flipflop の定義は可能だ。そこで、ghci で試してみた。

*Main> let
*Main| flipflop = proc (reset,set) -> do
*Main|     rec
*Main|       c <- delay False -< nor reset d
*Main|       d <- delay True -< nor set c
*Main|     returnA -< (c,d)
*Main|   where nor a b = not (a || b)
*Main|
*Main> runSF flipflop [(False,False),(False,True),(False,True),(False,True),(False,False),(False,False),(True,False),(True,False),(True,False),(False,False),(False,False)]
[(False,True),(False,True),(False,False),(True,False),(True,False),(True,False),(True,False),(False,False),(False,True),(False,True),(False,True)]

ちゃんとフリップフロップの動作をしている。再帰的定義の場合でも、arrow 記法のほうが point-free style より分かりやすい。

<< 目次 >>
[PR]
by tnomura9 | 2013-04-24 23:53 | Haskell | Comments(0)

千愛 (Chia)

【千愛】Toluthin Antenna lllトゥルティンアンテナlll 踊ってみた【誕生日&ソロ1周年!】

チャンネル

【千愛】 Chia
[PR]
by tnomura9 | 2013-04-23 23:24 | ボーカロイド | Comments(0)

最近の Danceroid

【DANCEROID】EZ DO DANCE【踊ってみた】
【いくらまなこさつき】Girls踊ってみた【チーム日本アルプス】
【柚姫×まぁむ+まりえ】えもラブ【踊ってみた】
【チームグンマー】キップル・インダストリー【踊ってみた】2013.4.14
【まぁむとまりえ】Sweetie×2踊ってみた【ミジンコ】
【さつまな】ライス定食【踊ってみた】2013.4.17
【まなこ × やっこ】ロマンちっくブレイカー【踊ってみた】2013.2.2
【まなこ x やっこ】ハートビートミュージック【踊ってみた】2013.4.6

ついでに昔のものも

【DANCEROID】ポーカーフェイス【踊ってみた】
【愛川こずえ】トゥインクル×トゥインクル踊ってみた【いとくとら】
【DANCEROID】galaxias!【踊ってみた】2011.12.14
【DANCEROID】Baby Maniacs【踊ってみた】
【DANCEROID】メグメグ☆ファイアーエンドレスナイト【踊ってみた】
【いくらミンカ】メランコリックを踊ってみた【魚民】

どれが上手いかというような比較より、躍る楽しさが表現されていることほうが見るものを楽しくさせる。それが受け継がれているのが大切なのではないか。
[PR]
by tnomura9 | 2013-04-23 22:39 | ボーカロイド | Comments(0)

Programming with Arrows 読解 10

3.2 Naming intermediate values

モナドのプログラムの場合のように、Arrow のプログラムでも計算の途中の値に名前をつけることができれば便利だ。モナドの場合はそれは do 記法で実現されているが、Arrow の場合も同じように do 記法が使える。ただし、モナドの場合の do 記法が式であるのに対し、Arrow の do 記法は command だ。

したがって、do 記法は arrow abstruction の中にだけ現れる。また、モナドの do 記法では x <- e は式 e の値に名前をつけるが、Arrow の場合はコマンドの出力に名前をつける。

単純な例としてファイルの内容を印刷する printFile arrow を次に示す。

Prelude> :set -XArrows
Prelude> :m Control.Arrow
Prelude Control.Arrow> :set +m
Prelude Control.Arrow> let
Prelude Control.Arrow| printFile = proc name ->
Prelude Control.Arrow|   do s <- Kleisli readFile -< name
Prelude Control.Arrow|      Kleisli print -< s
Prelude Control.Arrow|
Prelude Control.Arrow> runKleisli printFile "SF2.hs"
(表示省略)

<- Arrow -< という記法は矢を意識すると使い方のイメージが掴みやすい。データの流れは、矢筈の方から矢先に向かっている。

2番めの例はセクション 2.3 で述べたエッジ検出器の edge のプログラムだ。

edge :: SF Bool Bool
edge = arr id &&& delay False >>> arr detect
  where detect (a,b) = a && not b

これを do 記法で書くと次のようになる。

edge = proc a -> do
  b <- delay False -< a
  returnA -< a && not b

ghci で試してみた。

Prelude Control.Arrow> :l SF2.hs
[1 of 1] Compiling Main      ( SF2.hs, interpreted )
Ok, modules loaded: Main.
*Main Control.Arrow> let
*Main Control.Arrow| edge = proc a -> do
*Main Control.Arrow|   b <- delay False -< a
*Main Control.Arrow|   returnA -< a && not b
*Main Control.Arrow|
*Main Control.Arrow> runSF edge [False,False,True,True,True,False,False]
[False,False,True,False,False,False,False]

a や b が別の Arrow でも使える事で、記述がやりやすくなっている。Arrow の出力への名前付けの変換規則は次のようになる。

proc pat -> do
  x <- c2 ---------> (arr id &&& proc pat -> c1) >>>
  c2 --------------> proc (pat,x) -> c2

上の edge を point-free style で書くと次のようになる。

edge = (arr id &&& (arr (¥a->a) >>> delay False)) >>>
       (arr (¥(a,b) -> a && not b) >>> returnA)

ghci で実験したら次のようになった。

*Main> let
*Main| edge =
*Main|   (arr id &&& (arr (\a -> a) >>> delay False)) >>>
*Main|   (arr (\(a,b) -> a && not b) >>> returnA)
*Main|
*Main> runSF edge [False,False,True,True,True,False,False]
[False,False,True,False,False,False,False]

point-free style より arrow 記法のほうが読みやすいプログラムが書ける。また、a や b 等の名前が、do 記法の中ならどこでも使えるというのは便利だ。

今度は、do 記法を使って次の mapA のプログラムを描き直してみよう。

mapA f = proc xs ->
  case xs of
    [] -> returnA -< []
    x:xs’ -> (f *** mapA f >>> uncurry (:)) -< (x,xs’)

このプログラムでは4行目は point-free style で書かれている。これを出力に名前をつける方法で書き換えてみたのが次のプログラムだ。

mapA f = proc xs ->
  case xs of
    [] -> returnA -< []
    x:xs’ -> do
      y <- f -< x
      ys’ <- mapA f -< xs’
      returnA -< y:ys'

こうなると、普通のモナドのプログラミングによく似てくる。

ghci で動作確認をしてみた。

*Main> let
*Main| mapA f = proc xs ->
*Main|   case xs of
*Main|     [] -> returnA -< []
*Main|     x:xs' -> do
*Main|       y <- f -< x
*Main|       ys' <- mapA f -< xs'
*Main|       returnA -< y:ys'
*Main|
*Main> runSF (mapA (arr (*2))) [[1,2],[3],[4,5,6]]
[[2,4],[6],[8,10,12]]

このような pointed 記法を用いると、入出力に名前の付いているような論理回路を直観的に記述することができる。例えば、つぎのような「半加算器」がプログラムされている場合、

halfAdd :: Arrow arr => arr (Bool,Bool) (Bool,Bool)
halfAdd = proc (x,y) -> returnA -< (x&&y, x/=y)

この半加算器 halfAdd を使って全加算器 fullAdd をプログラムすることができる。

fullAdd :: Arrow arr => arr (Bool,Bool,Bool) (Bool,Bool)
  fullAdd = proc (x,y,c) -> do
  (c1,s1) <- halfAdd -< (x,y)
  (c2,s2) <- halfAdd -< (s1,c)
  returnA -< (c1||c2,s2)

全加算器のプログラムは、名つき出力を利用することによって、ネットリストでプログラムしたようになっている。

ghci で実験した。

*Main> let
*Main| halfAdd :: Arrow arr => arr (Bool,Bool) (Bool,Bool)
*Main| halfAdd = proc (x,y) -> returnA -< (x&&y, x/=y)
*Main|
*Main> let
*Main| fullAdd :: Arrow arr => arr (Bool,Bool,Bool) (Bool,Bool)
*Main| fullAdd = proc (x,y,c) -> do
*Main|   (c1,s1) <- halfAdd -< (x,y)
*Main|   (c2,s2) <- halfAdd -< (s1,c)
*Main|   returnA -< (c1||c2,s2)
*Main|
*Main> fullAdd (True,True,False)
(True,False)
*Main> runSF fullAdd [(True,True,False),(True,False,False)]
[(True,False),(False,True)]

この全加算器のプログラムを point-free style で記述した場合と比較すると、do 記法のほうがデータの流れを明確に記述できるのが分かるだろう。

<< 目次 >>
[PR]
by tnomura9 | 2013-04-23 11:11 | Haskell | Comments(0)

Programming with Arrows 読解 9

3 Pointed arrow programming

Arrow については、これまでは引数を明示せず関数の合成だけでプログラムを記述する point-free スタイルのプログラミングについて紹介してきた。しかし、Arrow のプログラミングでは、モナドと同じように、引数を明示した pointed style のプログラミングも可能である。この場合、モナドの場合と似た do 記法を使うことができる。

3.1 Arrow abstractions

Paterson によって Arrow に arrow abstruction (射抽象とでも訳すのだろうか)が導入された。これは、

proc pat -> body

という形をとる。pattern の部分で変数名の宣言を行い、それらの変数は、body の部分で Arrow へのデータの入力に利用される。また、body の部分は式ではなく、command と呼ばれる。

また、ghci で Arrow 記法を使うためには、:set -XArrows で -XArrows 言語拡張をオンにしておく必要がある。

Prelude> :set -XArrows
Prelude> :load SF2.hs
[1 of 1] Compiling Main ( SF2.hs, interpreted )
Ok, modules loaded: Main.

次の例は、ワンステップのディレイを持った AND ゲートのプログラムだ。

*Main> runSF (proc (x,y) -> delay False -< x && y) [(True,True)]
[False,True]

これは、Arrow 記法を用いない次のプログラムと同等だ。

*Main> runSF (arr (\(x,y) -> x && y) >>> delay False) [(True,False)]
[False,False]

body のコマンドが単純な場合、Arrow 記法は次のように翻訳できる。

proc pat -> a -< e ---------> arr (\pat -> e) >>> a

このことは、Arrow 記法で変数に使われた名前は -< 記号の左側には使えないということを示している。したがって、次のように変数名 f が -< 記号の左側に使われているコマンドは文法エラーになる。

proc (f,x) -> f -< x

これは、次のように書けば実行できる。

proc (f,x) -> app -< (f,x)

ghci で試すと次のようになる。

*Main> (proc (f,x) -> app -< (f,x)) ((*2),3)
6

上のような場合には、Arrow 記法には -<< というシンタックスシュガーがある。

proc (f,x) -> -<< x

ghci で試すと、

*Main> (proc (f,x) -> f -<< x) ((*2),3)
6

このような単純な例では Arrow 記法の特徴はあまり発揮されていない。Arrow 記法が便利になるのは、コマンドが組み合わされた複合コマンドの場合だ。例えば choice コンビネータ (|||) を使って条件分岐を記述する場合、述語 p の真偽にしたがって Left x か Right g を返す関数を記述する必要がある。

arr (\x -> if p x then Left x else Right x) >>> f ||| g

これは Arrow 記法を使うとつぎのようにスッキリと書くことができる。

proc x -> if p x then f -< x else g -< x

ghci で試すと次のようになる。

*Main> (arr (\x -> if odd x then Left x else Right x) >>> return "Odd" ||| return "Even") 5
"Odd"

*Main> (proc x -> if odd x then return "Odd" -< x else return "Even" -< x) 6
"Even"

この if ... then ... else ... は条件分岐コマンドだが、次のように翻訳できる。

proc pat -> if e then c1 else c2
------>
arr (\pat -> if e then Left pat else Right pat) >>>
(proc pat -> c1 ||| porc pat -> c2)

このばあい変数 pat のスコープは >>> による Arrow 適用の左右にまたがっていることが分かる。

上のような単純な条件分岐でも Arrow 記法の記述を簡潔にする利点は明らかだが、この利点は次の case コマンドを使用するとより明確になる。つぎのような Arrow コンビネータの定義について見てみよう。

mapA f = arr listcase >>>
    arr (const []) ||| (f *** mapA f >>> arr (uncurry (:)))
  where listcase [] = Left ()
    listcase (x:xs) = Right (x,xs)

上の mapA コンビネータの記述は case コマンドを利用すると次のように簡潔になる。

mapA f = proc xs ->
  case xs of
    [] -> returnA -< []
    x:xs’ -> (f *** mapA f >>> uncurry (:)) -< (x,xs’)

こちらのほうがはるかに読みやすい。

上のコードで returnA という Arrow があるが、これは何もしない Arrow だ。arr id と同等だ。上の returnA -< [] も arr (const []) -< xs と同等だが、returnA を使ったほうがずっと分かりやすい。

returnA を ghci て試すと次のようになる。

*Main> runSF (proc x -> returnA -< x) [1]
[1]

<< 目次 >>
[PR]
by tnomura9 | 2013-04-21 19:10 | Haskell | Comments(0)

Programming with Arrows 読解 8

2.4 Higher order arrows

Arrow にも高階関数のようなものがつくれるだろうか。言い換えると、別の Arrow を引数とする Arrow がつくれるだろうか。これまで述べたコンビネータでは作れないが、ArrowApply というクラスの関数 app を使うと作ることができる。

Prelude Control.Arrow> :t app
app :: ArrowApply a => a (a b c, b) c

ArrowApply クラスの概要は次のようになる。

Prelude Control.Arrow> :info ArrowApply
class Arrow a => ArrowApply a where
app :: a (a b c, b) c
-- Defined in `Control.Arrow'
instance Monad m => ArrowApply (Kleisli m)
-- Defined in `Control.Arrow'
instance ArrowApply (->) -- Defined in `Control.Arrow'

関数と Kleisli 射の Arrow についての apply の実装は次のようになる。

instance ArrowApply (->) where
  app (f,x) = f x

instance Monad m => ArrowApply (Kleisli m) where
  app = Kleisli (\(Kleisli f,x) -> f x)

関数型の app を試してみた。

*Main> let add_one = app (arr (+),1)
*Main> add_one 9
10

しかし SF (stream function) は ArrowApply のインスタンスの実装はしていない。

first や second 等の Arrow の関数は app で記述できるので、これらより app は適用範囲が広い。しかし、app で記述できる事柄は、Monad で完全に記述できるし、Monadの Kleisli 射は簡単に Arrow にすることができる。app を利用すれば Monad で記述するようなプログラムを Arrow で記述できるが、理論的な興味以外にはあまり意義がない。Arrow は Monad では記述できないものに使うべきだ。

2.5 Exercises

省略する

<< 目次 >>
[PR]
by tnomura9 | 2013-04-21 11:40 | Comments(0)

Programming with Arrows 読解 7

2.3 Arrows and feedback (続き)

フリップフロップがどういう動作をするかは Wikipedia の記事に書かれている。

『 Programming with Arrows 』で説明されているのは、このうちの RS フリップフロップだ。RS フリップフロップは2つの入力端子と2つの出力端子からなっている。入力の端子はそれぞれ S (set) 端子と R (reset) 端子という名前が付いている。また、出力は Q 端子と ¬Q 端子だ。Q 端子の出力と ¬Q 端子の出力は互いに反転している。

S 端子と R 端子の入力が Low のとき、出力の値は安定している。しかし、S 端子の入力が High になると、Q 端子の出力が High になる。また、R 端子の入力が High になると、Q 端子の出力は Low になる。S 端子と R端子が共に High のときは Q 端子の出力は安定せず発振してしまう。

RS フリップフロップは2個の NOR 素子で構成されている。Wikipedia では2個の NAND 端子と 2個の NOT 端子で構成されているが、これは2個の NOR 回路と等価だ。

RS フリップフロップでは出力から入力へのフィードバックがあり、Q端子 と ¬Q 端子の出力はそれぞれもう一つの NOR 素子の入力へつながっている。

このようなフリップフロップを Arrow で表現しようとすると次のようになる。

flipflop =
  loop (arr (\((reset,set),(c,d)) -> ((set,d),(reset,c))) >>>
    nor *** nor >>>
    arr id &&& arr id)

これだけでは何のことかわからないので、個々の部品について実験してみた。まず、前回の記事の最後で記載したサンプルプログラム SF2.hs を ghci にロードした。

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

それから、個々の部品の Arrow を調べてみた。まず、arr (\((reset,set),(c,d)) -> ((set,d),(reset,c))) の型を調べてみる。

*Main> :t runSF (arr (\((reset,set),(c,d)) -> ((set,d),(reset,c))))
runSF (arr (\((reset,set),(c,d)) -> ((set,d),(reset,c))))
:: [((t2, t), (t3, t1))] -> [((t, t1), (t2, t3))]

適当な Bool 型の値を与えてやると次のようになる。

*Main> runSF (arr (\((reset,set),(c,d)) -> ((set,d),(reset,c)))) [((True,False),
(True,False))]
[((False,False),(True,True))]

これは入力端子の値が (reset = True, set = False) で出力端子の値 (Q = True, ¬Q = False) のとき、(reset = True, Q = True) と (set = False, ¬Q = False) のペアを作り出す。この2つのペアは、RS フリップフロップを構成する2個の NOR 素子への入力になる。

次の Arrow の nor *** nor の型は次のようになる。

*Main> :t runSF (nor *** nor)
runSF (nor *** nor)
:: [((Bool, Bool), (Bool, Bool))] -> [(Bool, Bool)]

これは上のフィードバックを含めた2つの入力を NOR 素子に入力すると、それらの NOR 素子の出力が (Bool, Bool) になることを示している。

最後の arr id &&& arr id の型は次のようになる。

*Main> :t runSF (arr id &&& arr id)
runSF (arr id &&& arr id) :: [c'] -> [(c', c')]

これは、NOR 素子の出力を、複製して、arr (\((set,reset),(c,d)) -> ((set,c), (reset,d))) の型に合うように整形している。これで、個々の部品を >>> で繋いだとき合成の最初の入力と最後の出力の型が一致するので loop が記述できるようになる。

flipflop の定義の loop の第1引数の無名関数を flip1 として定義すると、flip1 の型と引数への関数適用例は次のようになる。

*Main> let flip1 = arr (\((reset,set),(c,d)) -> ((set,d),(reset,c))) >>> nor *** nor >>> arr id &&& arr id
*Main> :t flip1
flip1
:: SF ((Bool, Bool), (Bool, Bool)) ((Bool, Bool), (Bool, Bool))
*Main> runSF flip1 [((False,False),(True,False))]
[((True,False),(True,False))]

しかし、残念なことに上の flipflop のプログラムのプロトタイプは動かない。初期値が未定で計算が無限ループになってしまうからだ。

*Main> runSF (loop flip1) [(True,False), (True,False)]
Interrupted.

きちんと働くフリップフロップを記述するためには delay を入れて次のように記述する。

flipflop =
    loop (arr (\((reset,set),~(c,d)) -> ((set,d),(reset,c))) >>>
          nor *** nor >>>
          delay (False,True) >>>
          arr id &&& arr id)

ところが、『 Programming with Arrows 』の本文をコピーした上のプログラムは動作がおかしいように見える。

*Main> runSF flipflop [(False,False),(False,False),(False,False),(False,False),(False,False),(False,False)]
[(False,True),(False,True),(False,True),(False,True),(False,True),(False,True),(False,True)]
*Main> runSF flipflop [(False,False),(True,False),(False,False),(False,False),(False,False),(False,False)]
[(False,True),(False,True),(False,True),(False,True),(False,True),(False,True),(False,True)]
*Main> runSF flipflop [(False,False),(False,True),(False,False),(False,False),(False,False),(False,False)]
[(False,True),(False,True),(False,False),(True,True),(False,False),(True,True),(False,False)]
*Main> runSF flipflop [(False,False),(True,True),(False,False),(False,False),(False,False),(False,False)]
[(False,True),(False,True),(False,False),(True,True),(False,False),(True,True),(False,False)]

原因がわからないので、とりあえず結果だけ記載しておいたが。フリップフロップの出力が安定する以前の過渡現象を出力しているのではないかと思いついた。そこで、『 Programming with Arrows 』の信号のパターンを良く見たら、Reset や Set のパルス幅は3ステップある。試しにパルス幅を3ステップにしたら出力が安定した。

*Main> runSF flipflop [(True,False),(True,False),(True,False),(False,False),(False,False),(False,False),(False,True),(False,True),(False,True),(False,False),(False,False)]
[(False,True),(False,False),(True,False),(True,False),(True,False),(True,False),(True,False),(False,False),(False,True),(False,True),(False,True),(False,True)]

これでなんとかこのセクションを卒業できそうだ。

<< 目次 >>
[PR]
by tnomura9 | 2013-04-20 18:16 | Haskell | Comments(0)

休パソ日

昨日は朝から12時間以上パソコンにかじりついていた。これではあまりにひどいので、今週のウイークデーは私用のパソコン操作は禁止にすることにした。

絶対にパソコン中毒にかかっている。
[PR]
by tnomura9 | 2013-04-15 09:40 | 話のネタ | Comments(0)