Old/sampou.org/Programming_WayToHaskeller_つかまり立ち

Programming_WayToHaskeller_つかまり立ち

Programming:WayToHaskeller:つかまり立ち


つかまり立ち

(「つかまり立ち」を編集する)|(Haskellerへの道)

すでに勉強してきたネタも尽きたし、改めて やさしいHaskell入門とかモナドのすべてとか読み込まないといかん。

リストもモナド?

んで早速、ここを読んでたら、 リストもモナドなんだってさ。これって実は 以前も読んでたんだけど、それほど気にならなかった。でも、今の自分にはな ぜか衝撃的! だってさ、そうだとするとオイラはモナドなんぞチンプンカンプン・・・・ ってこたリストを分かってねーじゃんっ!!げげげ。(+_+;

んで、リストの型構築子は [] だっちゅーわけですな。 [a] ってな感じで a を [ と ] ではさんでやれば、 a を要素にもつリストです。

ほほぅ、こんなんは表記の問題だからさ、もしかしたら、実装者の気の向きよ うによってはList a ってな書き方してたとしてもいーわけよ。逆に IO a っ てやつも <> って表記する様になってた可能性だってあるよね?

実際に、

Haskell の構文では[t] を[] t と書くことも許されています。

ってここにも書いとる。これって List ってのが [] になっただけじゃん? じゃーさじゃーさ、

main :: IO a

だっつー感じで書けるんだとすると、

main :: List a

って書けたっていーじゃんね?っちゅーことはさ、

main :: List a
     ↓
main :: [] a
     ↓
main :: [a]

なんだよね?・・・・・・・・・・・・・・・えぇぇぇぇええええぇぇっっっ!!? ちょい待て、 [a] ってリストだよん?これってどういう関数だ?

main は関数じゃねーのか?

どういう関数もこういう関数もリストはリストだわなぁ。

こことかには -> ってのも型構築子の一種で a -> b って書くと a を引数に 取って、b を返す関数って型になると書いてあった記憶がある。

同じように -> は型構築子です。与えられた 2 つの型 t と u に対して、 t->u は型 t の要素から型 u の要素への写像をおこなう関数の型です。

あ、コレコレ!この文章!・・・ってことはやっぱり、これ関数じゃないよ? main って名前なもんだから、何の疑いも持たずに関数だと思い込んでたけど、

main :: IO a

って、どこをどうみても関数らしい型宣言になってねーぞ?じゃあ何よ?

#!/usr/pkg/bin/runhugs

> main :: [a]
> main = [1,2,3]

ってしてみて、ロードしてみる。

Type checking
ERROR "/home/cut-sea/script/haskell/test2.lhs":3 - Cannot justify constraints in type annotation
*** Expression    : [1,2,3]
*** Type          : [b]
*** Given context : ()
*** Constraints   : Num b

Prelude> 

ありゃ?なんで? Type は [b] ってことは、別に [a] でも正しいような気が するんだけど、とりあえず型を外してみるか?

#!/usr/pkg/bin/runhugs

> main = [1,2,3]

これでどーだ!ロード!!

Main> main
[1,2,3]
Main> main 1   <= 例の常套手段で型を教えてもらってる
ERROR - Type error in application

*** Expression     : main 1
*** Term           : main
*** Type           : [Integer]
*** Does not match : a -> b

あー、[a] じゃダメなんだ。[Integer] なのかぁ。間違っちゃいない気もする んだけどなぁ。 (Type参照:ほう、なるほど) まぁいいや。今はそれどころじゃ ないし。

#!/usr/pkg/bin/runhugs

> main :: [Integer]
> main = [1,2,3]

Main> main
[1,2,3]

おっけー!走るとは思えないけど一応コマンドラインから実行!

[email protected]> ./test.lhs 

Program error: fromDyn failed.  Expecting <<IO ()>> found <<[()]>>
runhugs: Error occurred

うむ。まぁいい。これは無視! とにかく、これと同じことなんじゃないだろうか?つまり、これまで悶々とし ててイマイチ釈然としなかったんだけど、 IO () とかを関数だと思ってたの が間違いなんじゃね?もしかすっと。

恐れ多くてとても口に出来ないので書いちゃいますけど。もしかするともしか してIO ()型の main は関数じゃなくて値 なんでないすか?

んじゃーどういう値よ?って言われたらアクションっていう値なんじゃないか?

Main> main
[1,2,3]

って感じで、main がたまたまリストの場合は評価された結果、リスト[1,2,3]っ てのがオメミエするわけだけど、 main の値がたまたまアクションの場合は評 価結果としてアクションを取って見せる、と。

全然話が違うけど ASCII コードの 07h ってコードに bell ってのがあるね。 ほとんど、どのコードも印字された時の表示形式があるけど、 bell は我々の 目には見えず、耳に聞こえる形で、その存在をみせてくれる。平たく言えば ビーッって泣きやがる。あ、良く見たら他にもあるわ。BS とか DEL とか。。。 そだ! BS や DEL なんか、まさにそのアクションでもって、その文字コード がそこにあることを教えてくれるよね?

・・・えっと、何言いたかったんだっけ?(^^;; ・・・ど、どーゆー理屈だか自分でも不可解だけど、値ってやつが全て印字さ れたときの表示形式を持ってなくちゃならないって決まってなくて、我々の視 覚以外の感覚器官に訴える形であっても良いわけよ。あるいは何も訴えなくたっ ていいわけで、cp.lhs なんかその最右翼じゃない? (まだ作ってねーけど) アクション型(勝手につけてるし・・・)の場合には、我々の目に見えるとか聞 こえるとかが本質じゃなくて、まさに何らかのアクションをするって形で、そ の存在を示すんじゃないかしらん。たまたま、Hello,World!って印字したりと か、ビーってビープ音を出すかもしれんけど。

数値だって本質は整数の何番目の数とか、そーゆー難しい抽象的な存在なわけ で、それ自体はそもそも目に見えるものじゃないんじゃないかな。多分。その 印字名として 1 とか 2 とかって表示が与えられてるにすぎねーのよ。人間に とって便利だからさ。うん。 逆に数値だって印字表現がなくてカワイイ女の子の声で「いち♪」とか「に♪」 とかって表現されたらどうよ?もしそうだったら数値は目には見えないけど、 やっぱりデータだよね?この論法、かなり無理くさいですか?そうですか・・・

Haskell では印字可能クラスというのあります。Show class です。Integerや Charなどは Prelude で、Show class のインスタンスとして宣言されています ので、評価結果が Integer や Char になるものはインタープリタで評価した ときに評価結果が表示されます。要素 a が Show クラスのインスタンスであ れば、[a] も Show クラスのインスタンスであることが宣言されていますので、 [Integer] なども印字可能です。

しかし、id とか head とか Prelude で Show クラスのインスタンスであるこ とが宣言されていない関数は、評価すると印字用の show 関数(Show クラスの メソッド)がないぞ、というエラーが出るはずです。

IO a の a と [a] の a

でもさ、そうすっと IO a って本来は、そのお姿を見せてくれないんだから、 IO () だろうが、 IO String だろうが、 IO [String] だろうが同じじゃねぇ か?つまり、String とか [String] とか IO にとっては違いは関係ないんじゃ ね?

・・・うーむ、脳味噌が沸騰しはじめた。ε=(+_+;=3

いやいやリストだって同じだ。確かに IO a において a は内部に隠されてて 見えないけど、 [Integer] とか [String] ってリストだって同じなんだよ、 きっと。

実際には List a の a は内部に隠し持ってて、本来リストとして見たときに は Integer とか String とかは見えないんじゃねーかな?

Main> [1,2,3]
[1,2,3]
Main> ["cut-sea","nobsun"]
["cut-sea","nobsun"]

こんな風に確かに 1 とか 2 とか “cut-sea” とか “nobsun” とか見えている けど、そりゃーたまたま(?) Haskell の実装においてリストの表示は、その 内部に隠し持っているメンバであるところの 1 とか 2 とか “cut-sea” とか “nobsun” とかを表示する様になってるだけなんじゃん?

もしかしたら、実装者になんかの気の迷いがあったりして、

Main> [1,2,3]
#<List 0x8121e60>          <= こんな印字形式とかさ
Main> ["cut-sea","nobsun"]
#<List 0x8121e64>

みたいな、そういうリストの印字表現を持つような、そんな実装があったとし ても、それはそれでいいんじゃないかなぁ。 リストの先頭っていうかルートへのポインタを指すオブジェクトをこう、さ。うん。

そのポインタから継っている全体がリスト、そういう構造みたいなのがリスト であって、内部に持っている要素にアクセスする手段として car/cdr じゃねー や、 Haskell だと head/tail があって、これを使えば、全要素にアクセスで きるし、それにアクセスした時にリストが [Integer] なら Integer の 1 と か 2 とか、 [String]なら “cut-sea” とか “nobsun” が見えると。これは実 際には [Char] だから、そういう実装だと、 “cut-sea” とは表示されずに、 さらに #みたいな表示になっちゃうだろうから〜・・・ うぇっ!すんげー不便だ、なんだこりゃ!美的センスゼロじゃん。 ともかく、そういう実装だとしたらリストだって、結局 [a] の a ってのは内 部に 隠し持たれてるものであって、リストの印字表現に含まれなきゃならな いものじゃないんだよ〜、多分。リストの本質は head とか tail とかって演 算によってアクセスされたり、 :って演算によって構成されたりする、そうい う構造そのものが本質だと。

同じ様に IO a でも IO () ってのと IO String ってのと IO [String] って のは、 IO っていう(リストと同様に何らかの構造とか性質を持った)値として 存在してて、そいつが内部に隠し持っているデータとして () とか String と か [String] とかがある?

んじゃ、そういう目でもっかい echo.lhs を見てみるとしようか。

Main> main 1 2 3
ERROR - Type error in application
*** Expression     : main 1 2 3
*** Term           : main
*** Type           : IO ()
*** Does not match : a -> b -> c -> d

Main> main

Main> 

うむ。やっぱ関数じゃない。main の値が現れました。 おぉっ、見える!わたしにも値が見えるぞ!ラ○ァ!! ・・・えっと、とり あえず、自分の中ではナットク出来た気がするんだけどなぁ。

見えねぇもんが見えるなんて、なんか瞳孔おっぴろげて変な宗教にハマってる ヒトみたく、危ない方向につっ走ってますか、私?

thunk はどう書くのか?

うぅっ、こんなつもりじゃなかったのに、次々に疑問が湧き出す。 そもそもアクションが値なんて勢いで言ったけど、アクションて結局は関数の 評価プロセスそのものなんじゃないか? カッコがないと、いまいち違いが分かりにくいので、あえてScheme?で書くけど、

gosh> (define f (lambda () body))

ってな定義があったときに、

gosh> f

これを評価した結果得られるのは、関数実体つまり第一級のデータですねぇ。

gosh> (f)

これは関数を評価した結果生まれるアクションですねぇ。 UNIX システムで言 えば、 f の評価の結果として得られるのはプログラムで、 (f) の評価の結果 得られるのはプロセスだな。これ、トーゼン全くの別人さんです。はい。

前者は関数型言語におけるデータと言って差し支えないけど、その評価プロセ ス(?)は違うな。 [] a と IO a とのアナロジーからの話の展開に自信持っ ちゃってましたけど。 あぁぁあ((((( ;゜Д゜))))ガクガク。 要は何が言いたいかっちゅーと、アクションが値だってーのはかなり嘘くさい ぞ?私のゴーストがそうささやいとる。つまり勘です。はい。

そーすっとすぐさま気になるのは! ‘引数を持たない関数 thunk は Haskell ではどう書くのか?’ っちゅーことです。そういや、勉強はじめてからまだ一度も見てない気がする。

純粋関数型言語では同じ式は何度評価しても同じ値を返すっちゅーので、引数 という、関数の動作を変更する源が無い場合には、結局即値と同じモノって気 がしないでもない。

ell にはサンクという概念がありません。だって、Lazy なんだから。値は必要になるまで計算されません。敢て言うなら、全部サンク。

 = sum [1..]

いてあっても、hoge の値は必要とされているわけではありませんよね。 、ここでクイズ、hoge の値は、何時、どんな場合に必要とされるでしょう? –nobsun

型は?その本体の定義は?っちゅー訳で探し回ってみる。 ・って、探している内に神の声で thunk って概念はないよ、とのこと。 む、thunk についての理解が足りてないのか??どうも神の問かけに詰まっ まった。

げーおーげー、まぁ落ち着け。ここは一つクールにいこう。・・・まず、 トが含まれている。と思う。

 = sum [1..]

は’敢えて言うなら全部サンク’の例でしょう。 も停止しない式として書かれておる。

> hoge 123 <= 例の常套手段 R - Type error in application Expression : hoge 123 Term : hoge Type : Integer Does not match : a -> b

。 Type は Integer か。実は、

 :: -> Int     <= 苦しまぎれ

ってすると、

ing file “/home/cut-sea/script/haskell/test.lhs”: ing……………………………………………………. R “/home/cut-sea/script/haskell/test.lhs”:16 - Syntax error in type signature (unexpected `->’) ude>

構文エラーが出るし、

 :: _ -> Int   <= 悪あがき

すると、

ing file “/home/cut-sea/script/haskell/test.lhs”: ing……………………………………………………. R “/home/cut-sea/script/haskell/test.lhs”:16 - Haskell 98 does not support anonymous type variables ude>

叱られる。 Haskell では関数は引数が無きゃならんのかもしれん。と思 めてたとこだったりする。引数の無い関数ってのは、そのままデータだっ うことか。 言えば、あらゆるデータは全て thunk だってことでしょう。

ゃ、 thunk を復習してみるとしよう。

> (define (f x y) (* 2 x)) <= 第二引数は評価の必要無い関数を定義

> (f (+ 2 3) (read)) <= 正格評価を試してみる

                       <= 第二引数が停止しないので強制終了!
                          標準入力から何か打ち込みゃ良いけど疑似的にね

ERROR: unhandled signal 2 (SIGINT) k Trace: ___________________________________

 (read)
    At line 9 of "(stdin)"

> (define (h x y) (* 2 (x))) <= thunk 用です。やはり第二引数評価は不要

> (h (lambda () (+ 2 3)) (lambda () (read))) <= 非正格評価

>

ですね。Haskell においてはデータは全てサンクだってことは、 Haskell 全ての値は (lambda () value) って感じにくるまれているのか。でもっ Haskell の式評価は (thunk) って感じで force しているのか。

ゃ、問題の hoge の値は何時、どんな場合に必要とされるか?ですな。

> (define (h x y) (* 2 (x)))

> (define hoge (lambda ()

                 (let loop ((n 1))
                   (+ n (loop (+ n 1))))))  <= hoge はこう

> (define five (lambda () 5)) <= Haskell での 5 はこうか?

> (h five hoge) <= Haskell での評価をエミュレート

> (h hoge five) <= hoge が必要な計算の例

                                      <= したがって強制終了

ERROR: unhandled signal 2 (SIGINT) k Trace: ___________________________________

 (loop (+ n 1))
    At line 7 of "/home/cut-sea/script/scheme/test.scm"
 (loop (+ n 1))
    At line 7 of "/home/cut-sea/script/scheme/test.scm"
 (loop (+ n 1))
    At line 7 of "/home/cut-sea/script/scheme/test.scm"

>

む。・・・ムツカシイ(–;) ゃ、どんな場合に必要とされないか?を考えてみるか。

> (h (lambda () (+ 2 3)) (lambda () (read))) <= 非正格評価

>

場面で (lambda () (read)) は結局必要とはされなかったなぁ。実際私が しなくても計算は勝手に完了した。これはまさに (read) が評価されなかっ 拠だな。うん。

 て値は (read) に無関係に決まった値ですねぇ。

り、ある式が結果として、ある値に至る場合を考えると、その値に hoge が影響を与える場合に hoge は必要とされるんですね!

・って分かったような気になったけど、コレってお題を言い換えただけ?(^^; ません。いっぱいいっぱいまで脳圧上げて考えましたが降参です。お許し下せぇ。

例えば、次のような関数を定義してみよう。

isLT7 :: Int -> Bool
isLT7 = \ n -> n < 7

これは、与えられた引数が 7 より小さいかを判定する関数です。さて、 Haskell では、hoge も isLT7 も定義しただけでは、計算は何もおこりません。 これがまず、Scheme と違うところです。

では、計算はいつ起るかというと、式を評価しようとした時です。

isLT7 hoge 

をインタープリタのプロンプトのところで評価すると何が起るかを考えてみましょう。

注意することは、 lazy evaluation では、必要になるまでは計算されないと いうことです。

つまり、なにを求められているか、それには何が必要か、という順で考えることです。

インタープリタのプロンプトのところに、isLT7 hoge と入力すると、

  1. インタープリタは、isLT7 hoge の値を印字しようとする
  2. 印字ためには、isLT7 hoge の値を(False または True に)確定しなければならない
  3. そこで、isLT7 hoge の関数適用を計算する
    1. isLT7 を定義にしたがって、置き換えると (\ n -> n < 7) hoge
    2. λ式の本体の仮引数を、実引数で置き換えると hoge < 7
    3. これが、確定したBool型を返すには、hoge と 7 の確定値が必要
      1. hoge の確定値を計算
      2. 7 の確定値を計算(これは 7 ですね)
    4. hoge < 7 の確定値計算
  4. isLT7 hoge の確定値を得たので、これを印字

となる(はず)ですね。つまり、hoge の(確定)値は 3.3. のところで始めて必 要とされるわけです。で、実際には、この値を確定しにいくところで、無限の 計算にはいってしまって、先へは進まなくなるわけです。このような状態の hoge の値は ⊥ です。

正格(strict)とは、x = ⊥ ならば f x = ⊥ となるような関数 f の性質 のことで、非正格(non-strict)とは、x = ⊥ であっても g x ≠ ⊥ となる ような 関数 g の性質のことを言います。

もうひとつ別の例を考えてみましょう。

from :: Int -> [Int]
from n =  n : from (n + 1)

longerThan :: Int -> [a] -> Bool

longerThan 0 (_:_)  = True
longerThan _ []     = False
longerThan n (x:xs) = longerThan (n-1) xs

hage :: [Int]
hage = from 0

こんな定義をしておいて、今度は、

longerThan 3 hage

を評価すると何がおこりますか?

longerThan 3 (repeat (1 `div` 0))

ではどうでしょう?

(2004/09/30 11:48:42 JST): ごめん。(0/0)じゃなくて(1 `div` 0)にしてく ださいな。 (0/0) だと、⊥にならなくて,NaNになっちゃう。以下の (0/0) を 全部、(1 `div` 0) に置き換えちゃいます。

うぅむ。 何を求められているか?ってのが、すんげぇポイントなのかぁ。

これまで未定義値を含む式は誰がなんと言おうと未定義値!ってそういう頑固 オヤジだと思ってましたよ、あたしゃ。(いや、非正格を非正確に認識してま したねぇ。まだまだブルーだわ。) んが、どうも様子が変なんだよなぁ。それを求めて(要求して)いるヤツ(な んちゅーか継続?)ってのがいて、どの辺まで突っ込んだモノを求められて (要求されて)いるか?ってのが評価されるかどうかのミソ?

最後の例で repeat (1 `div` 0) って式がありますなぁ。こいつは (lambda () (1 `div` 0)) って thunk を一要素として無限のリストを構成する。

こいつは直感的には

[(lambda () (1 `div` 0)),(lambda () (1 `div` 0)),(lambda () (1 `div` 0))..]

おぉっ、 Haskell と Scheme? のダブルさんだ。(^^; ま、とりあえず、こんなんだねぇ?あくまで直感的にね。こいつをトップレベ ルが求めているのだとすると (lambda () (1 `div` 0)) の 印字をするところ まで求められる。っちゅーことは、これを印字したい、印字する必要が出てき たところで _|_ か。

ところが、上の例で repeat (1 `div` 0) の値を求めている longerThan って やつは、そこまで突っ込んだものは欲しがってないんだ!

型宣言をみてみよー!

ん、んん?・・・どあぁーーーーーっ!!! なんかめちゃくちゃ当ったり前のことに今ごろ気付いたかもしんない。もう、 まるで巨大恐竜が足を蚊に刺されてから何分も経って、ようやく気付いて「か ゆ〜」って思う様に私の頭脳はめちゃめちゃ遅延評価です。はい。(意味がち が・・・)

longerThan :: Int -> [a] -> Bool

これ!これを見ると [a] ってのがある。これは [Int] だっていいし、 [String] だって許される。もち、 [IO ()] だって、きっと許されるだろう。 多分。単にそういう任意の型を表すという側面でしか見れて無かったです、 えぇ。(^^;

これって別の言いまわしをすると、 longerThan は [a] っていうリスト構造 にのみ関心があり、 リスト構造までを要求しており、リストの内部までは要 求してない っていうことでも有りますよね?そうですよね?!そうだ!そう に決まった!!!

もう、目が血走って、今にも犯罪犯しそうな雰囲気マンマンにコーフンしちゃっ てます。こういう時にイキオイで書いた文章が間違ってると、死ぬほどはずい です。えぇ。でも私は懲りません。全然。漢(オトコ)って感じしませんか? そうですかしませんか。がっくり。

longerThan :: Int -> [a] -> Bool

この型宣言において、

longerThan 3 hage
longerThan 3 (repeat (1 `div` 0))

この二つの式は、( hage も repeat も)ともに longerThan からは [a] ま でしか求められておらず、リスト構造さえ作って提供してくれりゃ、中に格納 されているデータが (lambda () (1 `div` 0)) だろうが、気にしな〜い気に しな〜い♪ってことだ。

もしも、もしもですよ?

longerThan :: Int -> [Int] -> Bool
                       ↑
                     コレね

なんて型宣言になるような関数だったら、そんな longerThan 関数から呼ばれ た repeat (1 `div` 0) は [Int] って形までを求められる。つまり、 (lambda () (1 `div` 0)) の値を評価する必要を迫られる。

[(lambda () (1 `div` 0)),(lambda () (1 `div` 0)),(lambda () (1 `div` 0))..]

こいつを

[1/0の値,1/0の値,1/0の値..]

な形にまで簡約されることを求められる。ゆえにぃ、v(^^)v 1/0 の値を求め る段で多分 _|_ を返すと。

んじゃ、お題に戻ると、こういう回答になるんでしょうか?

hoge :: Int
hoge = sum [1..]

と書いてあっても、hoge の値は必要とされているわけではありませんよね。
では、ここでクイズ、hoge の値は、何時、どんな場合に必要とされるでしょう?

それは、 hoge を引数に持つ関数が評価される場面において、その関数の型宣 言で hoge が位置する引数の型が Int として型宣言している場合は hoge の 値は必要とされる。

仮に

fuga :: a -> Bool
deya :: Int -> Bool

という二種類の関数の型宣言があって、 fuga および deya の値が要求されて いる場面において、 fuga hoge とある場合には hoge はその値までは必要と はしないし、 deya hoge とある場合には hoge はその計算された値を必要と する。と。

もちろん、再帰的に呼び出し元にも同じ事が言えて、 deya を引数に持つもの が、 Bool を必要としてれば、その値を要求されるけど、 deya を呼んでいる のが、 deya の引数のところの型を a として宣言しているなら、deya hoge であっても hoge は値を要求されることはないと。 結局 main などのエントリポイントから a とかって型変数に行き当たったら、 そっから先は値そのものは要求されない。多分 リストだとかほにゃららモナ ドと称される様な構造にしか関心はないんじゃね?一方で、末端構成員まで具 体的な型が宣言され続けている場合には値が必要になる・・・可能性がある? (if とかがあるんでちょっと自信なくした)のかと。

遡って確認すると、 isLT7 はどうなっとる?

isLT7 :: Int -> Bool
isLT7 = \ n -> n < 7

これで、

isLT7 hoge

を評価すると、 isLT7 は引数 hoge に対して Int まで突っ込んだ情報を欲し がってる。つまり、hoge は計算された値を必要とされる。

・・・ってことで終了しねぇ計算がぁ〜!

あうあうあう じゃあ、

dorya :: Int -> Int dorya = const 1

と定義しておいて、

dorya (1 `div` 0)

を評価するとどうなる?

がぁん!なにやらイキオイで書いたのが、案の定間違っとるくさいぞ?(^^; やべぇ。ネット中引き回しの上さらし首だ。

const ってのは多分固定値を返すんじゃないかと思うんだけど、まぁここでは あまり本質的な問題じゃないな。いちおー、 const を調べておくか。

const          :: a -> b -> a
const k _       = k

あら?引数二つ持つのか。でも第二引数はシカトしとる。

とにかく、引数が dorya 本体に無関係だってのがポイントなんだ。にも関わ らず、その引数の型は Int に縛られとるがな。そんな御無体な・・・(–;

・・・ここで dorya ってのは Int -> Int ってあるけど、この型宣言は a -> Int でも良さげに思えますねぇ。っつーか私の理屈だと、それなら通るんだよ なぁ。でも Int -> Int となると、確かにダメだわ、こりゃ。早速、破綻しちゃ いましたねぇ。

デジャブったので、ずーっと上の方を見ると、

> main :: [a]
> main = [1,2,3]

ってした時にもエラーを食らってますな〜。この時私は「間違っては無い気が する」って感想を漏らしておる。

ここでも同じく a -> Int で間違っちゃいない気がするのだが、多分 a -> Int ってすると全く同じエラー食らっちゃいそうだな。とにかく試してみるか?

> dorya :: a -> Int
> dorya = const 1

こうしておいて、どりゃ?!

Main> dorya (1 `div` 0)
1

あー、そっか。 dorya の型としては a -> Int でいけるんだ、 const が a -> b -> a だから。うん。じゃさ、じゃさー Haskell の型推論システムとし てはどうなんじゃろ。予想は多分同じじゃねーかと思うんだけどね。ってわけ で型宣言を削って例の常套手段でお伺いを立ててみる。

Main> dorya
ERROR - Cannot find "show" function for:
*** Expression : dorya
*** Of type    : a -> Integer

・・・ということは、ユーザがコードに書く型宣言て Haskell の型推論と同 じか、もしくは、それより厳しい方向には宣言可能?なんでしょか。ゆるゆる にする方向には叱られたもんねぇ。多分厳しくする分には問題ないけど、ゆる ゆるにすると、本体で足し算してるのに、ゆるゆるの隙を突いて String とか IO () とか、足し算をすることが出来ないシロモノが入って来ちゃうからかな。

いずれにせよ、型宣言を見て値の計算が要求されるかどうかを見分けるのは無 理なんですねぇ。

んじゃ、 Haskell の型推論で見たらどうなんでしょ? Haskell の型推論がコー ド全体を解析した結果、ある関数の型の引数部分に a って型変数が残ったも のは、型を具体的に特定できなかったってことっすよね? ・・・あれ??、なんで特定出来なかったんだろ。(?_?;) とりあえず、その関数の評価においては、その型変数が残った引数は値を求め られず、先送りにされるんでないすかね?

あーでも、違うわ、こりゃ。 const ってのがまさに、それを物語っておる。

const          :: a -> b -> a

これは全部型変数だけど、

Main> const (1 `div` 0) 0

Program error: {primQrmInteger 1 0}

Main>

こんなんなります。つまり、 (1 `div` 0) の値を求めようとされてる。えぇ。 ガックリ、型変数 a だけどキッチリ値を求められることを要求されとるがな。

って思ったんだけど、いやいやこれってトップレベルか要求してるからじゃね? トップレベルに印字することを要求されるからか。例えば、

Main> length [const (1 `div` 0) "cut-sea"]
1

うむ。ここで (1 `div` 0) の値は最後まで評価されずに遅延されて、評価さ れず仕舞いだよね。結局誰も、(1 `div` 0) の値に関心を持たなかった、それ を要求しなかったからだ。 length の型は

length           :: [a] -> Int

だしね。

あー違う!頭ぐるぐるんなる・・・。これって longerThan でやったのと変わっ てねーじゃん。同じトコぐぅるぐぅる回ってますよ〜いつもよりたくさん回っ てます。はい。

何を求められているか、何が必要かがポイントなんだった。落ち着けオレ!返 り値と引数をちゃんと区別せんといかんように思う。

const          :: a -> b -> a

ここで、 最初の a と二番目の b は引数だ。この引数の値については const は必要としないのではないかな?

んで、返り値の a については const 式を引数として呼び出した側の関数がど う思っているかだよね?その呼び出し側が値を求めて(要求して)れば計算さ れるし、求めて(要求して)なければ計算されずにさらに先送り。と。

・・・ってことは、トップレベルってどういう関数になってんだろ?これって 絶対に値を要求してるけど、型は不問だよねぇ。 まぁ考えても無駄ってか、ハマルと挫折が待ってそうなんで逃げます。はい。 あっしの脳ミソの限界はるか彼方に越えてます。

ただ、一応メモっておこう。 main から末端構成員に向けて調べるってのは逆 だわ。少なくとも。 末端構成員から、そいつが値を求められる(要求される)のはどこか?ってのを main なんかのエントリポイントに向かって調べることになりそう。最後まで 値の計算を先送りにされた時に行きつくのがそこだしねぇ。

型の計算ってのは実行の前処理として行われるだけなんじゃないでしょうか。 型推論機構と評価機構は分けて考えるべきものなのでは。

型推論より厳しい型宣言の必要性

んで、結論は分かんないけど、疑問だけはどんどんでてくるわけよ。(^^; Int -> Int な dorya において、引数の型チェックを Int とする事に意味が あるような、そんな場面てどんな状況だろう。そもそもあるのだろうか。

Haskell ではそれを許しているってことは必要だからかなぁ、やっぱ。一つ言 えることは、振舞の上で、こんな違いが生まれますなー。

> dorya :: a -> Int
> dorya = const 1

でもって、

Main> dorya "cut-sea"
1

いえーす!おっけ。じゃぁこっちね。

> dorya :: Int -> Int
> dorya = const 1

Main> dorya "cut-sea"
ERROR - Type error in application
*** Expression     : dorya "cut-sea"
*** Term           : "cut-sea"
*** Type           : String
*** Does not match : Int

うん。まぁそだね。なんかの入力チェックか?でも弾いても弾かなくても結果 同じ気がする。むむむ(–; そろそろコードを・・・

まぁ、今の私がこーゆーもろもろの疑問を抱えてるって事を未来の自分に託し ておいて、 (問題先送り、これぞ遅延評価?)そろそろコードを書かんといか んすねぇ。はい。 多分 Haskell のコードを書かないと、いつまで立っても二足歩行に行けません。

その前に、上でさらっと流しちゃった部分を確認しときます。 `div` っての は、ここ にあるように関数値を中置演算にするものだそうです。あ、 div が じゃなくて注目はバッククウォートで括ってるってトコです。中置演算を前置 にするのが (++) みたいにするのに対して、その逆ですね。んじゃ、早速ため してみましょう。

Main> 1 `const` 2
1

できました。んじゃ、これはどーなんでしょ?

Main> "abc" `(++)` "xyz"
ERROR - Syntax error in expression (unexpected `(')
Main> (`const`) 1 2
ERROR - Syntax error in expression (unexpected `)')

あらら、どうも構文エラーになっちゃいますね。まぁ、そういうものみたいね。

あと、も一個確認してみます。なんとなく IO a 型の main において、 a は本体内にどんな影響があんのか(どんな風に現れるのか)が気になってます。

#! /usr/pkg/bin/runhugs

> main :: IO ()
> main = putStrLn "んちゃ!"

これはうまく動作しますね。んじゃ、 main を IO Int にするとどうなるんで しょうか?

> main :: IO Int
> main = putStrLn "んちゃ!"

ERROR "/home/cut-sea/script/haskell/dummy.lhs":4 - Type error in explicitly typed binding
*** Term           : main
*** Type           : IO ()
*** Does not match : IO Int

型が違うって叱られました。なんとなく、こうかなぁ?

> main :: IO Int
> main = putStrLn "んちゃ!" >> return 123

おー、おっけーみたいですね。じゃ、同じようにこんなんも出来そうです。

> main :: IO String
> main = putStrLn "んちゃ!" >> return "うりゃ!"

さらに

> main :: IO [String]
> main = putStrLn "んちゃ!" >> return (repeat "うりゃ")

おぉ? return は

return :: Monad m => a -> m a

だからいいのかな。repeat “うりゃ” 自体は値を必要としないんだね。なんか 実行前にはプロンプトに戻ってくんのか不安でしたけど。

さらにさらに

> main :: IO (IO Int)
> main = putStrLn "んちゃ!" >> return child
> 
> child :: IO Int
> child = putStrLn "ぷびー" >> return 0

いや、単に IO (IO Int) を main の型にしてみたかっただけっすけど。 ここまでの所結果は全部

Main> main
んちゃ!

って感じです。はい。いやぁ実に変わり映えしないですね。すんません。ん じゃ、これは?

> main :: IO a
> main = putStrLn "んちゃ!" >> return child
> 
> child :: IO a
> child = putStrLn "ぷびー" >> return main

相互再帰的にしちゃろうと思ったんですけど、どうでしょう?

ERROR "/home/cut-sea/script/haskell/dummy.lhs":7 - Inferred type is not general enough
*** Expression    : child
*** Expected type : IO a
*** Inferred type : IO (IO a)

うーん。ダメでした。ちょっと調子に乗りすぎましたね。まぁ、いいです。 ずーっと振り返ってみると何となく分かった気がしないでもないですが、 IO () だけ return が無くてもおっけーなのがちょい気になります。

> main :: IO ()
> main = putStrLn "んちゃ!" >> return ()

これでイケるかな〜?まさかなぁって思ったら、

Main> main
んちゃ!

あらら、大丈夫でした。なんか統一的に扱えるんですね。いちおー。 return ってのが生み出したものは、一体どこへ消えていくのでしょう?(?-?)

Hugsでは、インタープリタのプロンプトに IO a 型が渡されると、対応するア クションが実行され、結果の値は無視されるようです。ただ、‘:set +I’ とす ると、結果の値が表示されるようです。 (ここ参照)

ここまで >> ってやつを使ってましたが、これは例のパスを渡さない奴なんで、 右項側で好き勝手出来るんで、こうやって遊んでみるのには楽チンな感じです。 はい。

とにかく、 main が IO a 型なら、最終的に return a が返ればおっけーそう ですね。理解は出来てないですけど、一応押えておきます。はい。 return は

Monad m => a -> m a

なので、どっから m が IO だと知るのかが、謎ですけどね。もし良きに計らっ てくれるんだとすれば、

IO String
   ↓
[] String

って置き換えても良さげですね。っちゅーわけでぇ

> main :: [] String
> main = return "んちゃ!"

んじゃ、ロード!

Main> main
["\164\243\164\193\164\227!"]

いいですね。

> main :: [String]
> main = return "んちゃ!"

上のはこれと同じですんで、 return ってのは、モナドのインスタンスを作っ てるようなものってことでしょうか?そうだとすると、どんなプログラムも取 り合えず return 使って終端すりゃー万事おっけーですかい?

でも、String のリストを作るのかと思ったら、

> main :: [String]
> main = return "んちゃ!" "ぷぽ?"

えい!

ERROR "/home/cut-sea/script/haskell/dummy.lhs":4 - Type error in explicitly typed binding
*** Term           : main
*** Type           : [Char]
*** Does not match : [String]

型から言えば当然ですけど、さすがに [“んちゃ!”,“ぷぽ?”] を作ってくれる わけでは無いんすねぇ。(–; うーむ、 return って一体・・・

リストがモナドである事を示すために定義されているのでしょう。 一応、ここにリストのreturnの使用例があります

たらいまわし関数

えーっと、たらいまわし関数を作って結果を印字させるプログラムを組んでみ ます。なんせ、たらいまわし関数なら LL 中、 まぁ最速じゃねぇ?と言われ ている位です。たらいまわし関数を計算するコマンドは、やはり Haskell で 実装すべきでしょ。 それ以外考えられません。はい。 え?一体何に使うのかって?そんなちっちぇコト気にしちゃダメっす。もっと おーっきな目で見ないとね、おーっきな目で。

もち、現時点でホントに私の手元には影も形もありません。内容的にはそれほ ど難しいとは思ってないのですが、ここまでで出て来なかった関数なんかも必 要になりそうな気がしてます。

[email protected]> tak 12 6 0

みたいにコマンドラインから実行出来るようにしたいと思っているので、真っ 先に、どうやるんだろ?って浮かぶ課題が、

  1. 引数は文字列で渡されるので、こいつを数値に変換
  2. 計算した数値を文字列にして、結果を印字

この二点です。で、「やさしいHaskell入門」とかを斜め読みしてると、まぁ た横道それるんだけど、 ここに「アクションは Haskellの値です」って書い てある。ってことは、理詰めで導いたのは正しくて、私のゴーストのささやき (要はカンね)の方が間違ってたらしい。まさに「自分のゴーストが信じられ ない」状態に。うますぎ(^^; ちなみにすぐ横道にそれたり、どんどんスタック積み上げまくって本筋に戻っ て来れずにオーバーフローするのは私の特技だったりします。しかもスタック の上限が異常に浅いです。はい。

おっとっと、いかんいかん!目的をすぐ見失いそうになります。数値を文字列 に変換したり、文字列を数値に変換するんだった。

えーっとー。・・・結構探したけどそれっぽいのが見当たらないっす。まぁい いです。何事も勉強です。 digitToInt とか intToDigit ってのが ここにあっ て、型からして、使えそうなんで試してみましょう。

Main> digitToInt '7'
7
Main> digitToInt '9'
9

はい、まずはこれが文字列から数値に変換する時に使えそうな気がします。

Main> intToDigit 7
'7'
Main> intToDigit 9
'9'

これが、数値から文字列を作るのに使えそうな感じなんですけど、あまりにも 遠そうですんで、もしかしたら作ってるうちに使えそうな関数に出会えるのを 期待することにします。まぁ、こいつはキープってことで。

無謀ですけど、まず型宣言を書いてみましょう。実際に Haskeller な方がど ういう感じでコーディングするのかは、リアルタイムで見たことが無いのでど ういう順かは知りませんが、多分、型から入るんじゃないかなぁと思ったって ことでチャレンジ!

まず、main です。とりあえず、印字だけさせようと思います。 return も書 かないつもり。

main :: IO ()

main 内では putStrLn とかを使って書こうと思います。したがって、 putStrLn に渡すたらいまわし関数の返り値を文字列に変換する必要があるん で、その関数は整数から文字列への関数になると。

numberToStr :: Int -> String

あ、その前に getArgs から貰った引数の文字列を整数に変換する関数が要りますな。

strToNumber :: String -> Int

んで、このコマンドのまさに核部分です。言わずと知れた超有名な関数です。 ちなみに tak 関数とかたらいまわし関数とか色々言われるみたいなんですけ ど、正式にはどうなんですかね?まぁ、引数に整数を三つ貰って、んでから返 り値も整数です。

tak :: Int -> Int -> Int -> Int

こんなとこでしょうか?あと必要になったら、気付いた時点で追加することにします。

んじゃ、まず文字列を整数に変換してみます。

Prelude> map digitToInt "123"
[1,2,3]

map に関しては実は mapM だの mapM_ だのを見てたので、どーしよーかと思っ たんですが、小細工なしで map でいったれ!ってやってみたら、すんなり動 いてくれちゃいました。

んじゃ、[1,2,3] とかってなったリストを各桁と見なした複数桁の数値にします。

Prelude> foldl1 (\x y -> 10*x+y) [1,2,3]
123

わーい、意外とすんなりいきました。ちょっと飲み会の後で少しアルデヒドが 脳細胞に刺激を与えている位が丁度いいのかもしれません。このすんなり具合 は中毒症状では無いので大丈夫(^^)v

んじゃ、strToNumber を作ります。

#!/usr/pkg/bin/runhugs

\begin{code}

main :: IO ()

numberToStr :: Int -> String

strToNumber :: String -> Int
strToNumber str = foldl1 (\x y->10*x+y) $ map digitToInt str

tak :: Int -> Int -> Int -> Int

\end{code}

これでロードしてみます。

Reading file "/home/cut-sea/script/haskell/tak.lhs":
Parsing........................................................................
ERROR "/home/cut-sea/script/haskell/tak.lhs":5 - Missing binding for variable "main" in type signature

ありゃ?えーっと、なになに? main 変数に束縛がねーぞって叱ってる。あー、 本体の定義後まわしにしようと思ったんだけど、ダメなんだぁ。残念。

んじゃ、

#!/usr/pkg/bin/runhugs

main :: IO ()

numberToStr :: Int -> String

\begin{code}

strToNumber :: String -> Int
strToNumber str = foldl1 (\x y->10*x+y) $ map digitToInt str

\end{code}

tak :: Int -> Int -> Int -> Int

こんな感じになるかな?んで、走れ!

Main> strToNumber "123"
123

いぇーい!!d(^-^)b いや、感心してないで次いきましょう。 numberToStr です。

numberToStr :: Int -> String
numberToStr num = do (q,r) <- (quotRem num 10)
                     (numberToStr q) ++ [intToDigit r]

パターンなんぞをタプルに適用してみました。いや、使えるのかどうか知らん けどね。これでいけんじゃね?えいやー!

Type checking
ERROR "/home/cut-sea/script/haskell/tak.lhs":13 - Type error in generator
*** Term           : (q,r)
*** Type           : (a,b)
*** Does not match : Int

うがっ?なんだこれ?

quotRem :: Integral a => a -> a -> (a, a)

ってある。なんか Integral が意味分からんが、 (a, a) を返している。問題 は上のエラーメッセージ中で (a, b) って出ているところ。んーと、んじゃ、 これはどうよ?

numberToStr :: Int -> String
numberToStr num = do q <- quot num 10
                     r <- rem num 10
                     if (q == 0) then [intToDigit r]
                                 else (numberToStr q) ++ [intToDigit r]

タプルをパターンにするのがダメだったのかもしれんと思ったわけだ。ほれ!

Type checking
ERROR "/home/cut-sea/script/haskell/tak.lhs":13 - Type error in generator
*** Term           : num `quot` 10
*** Type           : Int
*** Does not match : a b

あ?だめだこりゃ。 これ見てもどうも何が悪いのかよくわかんねぇっす。はい。

doはモナド専用なので、 let,whereを使いましょう

・・・・・・・・・・・・・・・・・・・・・・・・おっと、ついのめり込ん でしまっちゃって実況中継忘れた。もう意地で do にこだわったんだけど、全 然型が通らない。押してダメなら引いてみなってことで、もちっと簡単にして みる。

numberToStr :: Int -> String
numberToStr num = if (num < 10)
                  then [intToDigit num]
                  else (numberToStr $ quot num 10) ++ [intToDigit $ rem num 10]

こいつでどーだっ!!

Main> numberToStr 123
"123"
Main> numberToStr 987654321
"987654321"

ほっ。よっしゃ!何とかいけたね。

んじゃ、 tak 関数を作ってみます。えーっと、私のずたぼろの「はじめての 人のためのLISP」を見ます。私を S式の世界にいざなってくれた真っ赤なハレ ンチ本です。

tak :: Int -> Int -> Int -> Int
tak x y z = if (x > y) then tak (tak (x-1) y z)
                                (tak (y-1) z x)
                                (tak (z-1) x y)
                       else y

んで、ロード!

Main> tak 6 3 0
6
Main> tak 8 4 0
8
Main> tak 10 5 0
10
Main> tak 12 6 0
12
Main> tak 100 50 0
100
Main> tak 200 100 0
200

うーっむ、定義を間違ってねーか?って思うくらい異常に早いです。信じらん 無いくらい。ボーゼンとしてしまいます。

えっと、残るは main だけ?よしゃ。その前にだいたいの流れを確認。

Main> map (strToNumber) ["200","100","0"]
[200,100,0]

こいつに tak を適用すりゃいいだけ!うわ (^^) 取ったもドーゼン!!へへへ〜 ・・・あら?リストの各要素に適用しないとダメじゃん。しまった、どしよ。

とりあえず、 Scheme? とかだと apply とかってのを使う方向に考えるんだけど、 :find apply とかしても出て来ない。しょーがないから、急遽関数を作ることにしましょう。

apply f [x,y,z] = f x y z

こんなんアリ?だいたい型はどーなるんだよ?

Main> map (strToNumber) ["200","100","0"]
[200,100,0]
Main> apply tak [200,100,0]
200

おぉっ!動くじゃん。すげえすげえ。じゃあ例の常套手段を使って〜って、今回は違うぞ!一応型を自分で作ってみよう。

apply :: (tak の型) -> [a] -> a

かな?ってーことは、

apply :: (Int -> Int -> Int -> Int) -> [a] -> a

え、違うわ、 全部 Int かな。

apply :: (Int -> Int -> Int -> Int) -> [Int] -> Int

んでロードだ。

Main> apply (tak) [100,50,0]
100

おっけー!もー得意気になっちゃうよ!天狗天狗!!

一応 Haskell の型推論を確認すっと、

Main> apply
ERROR - Cannot find "show" function for:
*** Expression : apply
*** Of type    : (a -> a -> a -> b) -> [a] -> b

あらら。めちゃめちゃ応用範囲広いじゃん。オレってばすんげぇ apply の活 用を絞りすぎた。やっぱ難しいなぁ。型宣言するのが良いのって、ある程度プ ログラマの方も型推論がしっかり出来なきゃあまり意味無いって思うのオイラ だけっすか? どーも、具体例が頭にあるだけについ絞っちゃうんだよね。型宣言するときに、 具体的に考えている使い方以上に抽象化して考えないと、実際には Haskell の型推論レベルのものが得られない気がする。

import System

main :: IO ()
main = do args <- getArgs
          putStr $ numberToStr $ apply (tak) $ map (strToNumber) args

こんなんですね。えっと、ロードがうまくいくんでファイルに実行権限つけて コマンドラインから実行!

[email protected]> ./tak.lhs 6 3 0
[email protected]>

あ、そっか。 putStr じゃなくて putStrLn の方がいいか。 んで、書き換えたんでコード全体はこんな感じになります。

#!/usr/pkg/bin/runhugs

\begin{code}

import System

main :: IO ()
main = do args <- getArgs
          putStrLn $ numberToStr $ apply (tak) $ map (strToNumber) args

apply :: (a -> a -> a -> b) -> [a] -> b
apply f [x,y,z] = f x y z

numberToStr :: Int -> String
numberToStr num = if (num < 10)
                  then [intToDigit num]
                  else (numberToStr $ quot num 10) ++ [intToDigit $ rem num 10]

strToNumber :: String -> Int
strToNumber str = foldl1 (\x y->10*x+y) $ map digitToInt str

tak :: Int -> Int -> Int -> Int
tak x y z = if (x > y) then tak (tak (x-1) y z)
                                (tak (y-1) z x)
                                (tak (z-1) x y)
                       else y

\end{code}

実行例じゃー。

[email protected]> ./tak.lhs 6 3 0
6
[email protected]> ./tak.lhs 100 50 0
100
[email protected]> ./tak.lhs 200 100 0
200
[email protected]> ./tak.lhs 300 150 0
300
[email protected]> ./tak.lhs 400 200 0
400

よしゃ!すばらしい!!オレってすげぇ!! んじゃ、引続きこのコードを他にも書き換えられねぇか少し遊んでみよう。

しかし、やっぱはえぇっ!! 400 200 0 って与えた時はさすがに回答まで一 呼吸置くんだけど全然待たされてる気がしない。同一マシンで Emacs Lisp で の 12 6 0 を評価した時は、カップラーメンが作れちゃったくらいでしたよ? しかもかなりふやけてしまってスカスカになってたし。いや、そこまで律義に 待つオイラもどーかと思うけどさ。

#!/usr/local/bin/runhugs
\begin{code}
module Main where
import System
import IO
main :: IO ()
main = do args <- getArgs
          case args of 
            x:y:z:_ -> print $ tarai (read x) (read y) (read z)
            _       -> hPutStr stderr usage
usage :: String
usage = "Usage: tarai x y z"

tarai :: Int -> Int -> Int -> Int
tarai x y z | x <= y    = y
            | otherwise = tarai (tarai (x-1) y z)

                                (tarai (y-1) z x)
                                (tarai (z-1) x y)
\end{code}

おぉっ、引数チェックの様なものを入れたいと思ってたとこ。いくつか確認し たいので自分のコードをいじくる前にちょい見てみる。まず、大幅に楽チンに 済ませているのが read と print ですな。

んーっと :find read ってすると、なんだかごちゃごちゃしてるんだよな。芋 づる式でぐちゃぐちゃ readHogeってのが出てくるんすよ。マニュアル類を見 ていると ここに read ってのと show ってのが出てくるなぁ。ふむふむ。ど うやら型だの型クラスだのを少しかじっておいた方が良さげな感じ。

でもいきなり意味不明用語連発で死にたくなってくる。少しもどって、ちまち まやってみよう。 カタにハメてやろうか

さらに戻ってみると、 Color って型を定義してます。 んが、イマイチよう分からん。まぁ、よく理解できない時にはHaskellとお話 をして反応をうかがうんです。

data Color = Red | Blue | Green
isColor :: Color->Bool
isColor c = case c of
              Red -> True
              Blue -> True
              Green -> True
              _ -> False

んで、遊んでみましょう。

Main> :e color.hs
Main> isColor Red
True
Main> isColor 123
ERROR - Cannot infer instance
*** Instance   : Num Color
*** Expression : isColor 123

Main> isColor "Red"
ERROR - Type error in application
*** Expression     : isColor "Red"
*** Term           : "Red"
*** Type           : String
*** Does not match : Color

Main> isColor Yellow
ERROR - Undefined constructor function "Yellow"

Main> Red == Red
ERROR - Cannot infer instance
*** Instance   : Eq Color
*** Expression : Red == Red

ふむ。なんとも面白いのは Red だの Blue だの Green だのってリテラルが data Color の右辺、つまりデータ構築子として出現しただけで、存在しちゃ うってこと。 C の enum なんかと同じみたいなんだけど、これってScheme?で 言えばどういうこと?敢えて書くとするとこんな感じでシンボル自身を指すシ ンボルを作るって感じだろうか?

(define Color '(Red Blue Green))
(define Red 'Red)
(define Blue 'Blue)
(define Green 'Green)
(define (isColor c) (if (memq c Color) #t #f))

と思ったら、

Main> Red
ERROR - Cannot find "show" function for:
*** Expression : Red
*** Of type    : Color

あー、 show クラスじゃないから印字表現がねぇよって言われます。つまり、

(define Red 'Red)
(define Blue 'Blue)
(define Green 'Green)

ってトコまではやりすぎかな。まぁ全然内部でやってることは違うくさいけど。 どうも、RedとかBlueとかGreenとかってシンボルをColorってグループの一員 としてインターンしているって感じだろう。とりあえず、そう思ってみる。

んじゃ、お次は show クラスってやつだね。でも、つらつら見ててやっぱりキ ビシー!!いや、一部が分からない分にはいいんです。えぇ、大半が分からな いと気持ちが萎えます。

それでもケナゲに ここの導出されたインスタンスを見て、deriving ってな単 語に遭遇!わおっ。由来するとかって意味?しかもクラスっぽいのを継承して ますよ〜って電波をバシバシ感じます。

data  Tree a            =  Leaf a | Branch (Tree a) (Tree a)  deriving Eq

こーゆーとこに(^^) ちゅーわけで、

data Color = Red | Blue | Green deriving (Eq, Show)

これならどーよ!じゃじゃじゃーん!!

Main> Red
Red
Main> Green
Green
Main> Blue
Blue

やたっ。正解じゃん。なんかそれっぽいのを継承したみたいっす。 でまぁ、 Eq ってクラスも継承してるつもりなんで、

Main> Red == Red
True
Main> Red == Blue
False
Main> Red == 123
ERROR - Cannot infer instance
*** Instance   : Num Color
*** Expression : Red == 123

ってなワケでさっきは叱られた == なんかも適用可能と。クラスってのは他の 言語でいうクラスと同じようなもんなんでしょう。適用可能なメソッドとかも そのレベルで持っていると思われる。

・・・えーっ?そーいや、ずっと型がクラスみたいなもんかと思ってたぞ。(^^; そうか、違うのか。んー(-“-)

Haskell でのクラスとほかの言語でのクラスの意味が違うだけでしょう。 Java と比較するとこんなかんじ。

Haskell Java
クラス インターフェイス
インスタンス (型) クラス
インスタンス(オブジェクト)

まーいーや、show クラスってのがなんか見えてきた。多分関数なんかも show クラスを継承させられると、Scheme?みたく関数だけを入力してやるとエラー じゃなくてそれっぽい印字名で見えてくるんだろう。しかし、さっきはどう表 示するのか指定しなかったのによきに計らってくれたな。関数とかだとどう指 定するんだろうね。

じゃあ引き続き、read クラスに行ってみようか。

Main> read
ERROR - Unresolved overloading
*** Type       : Read a => String -> a
*** Expression : read

って感じになってますな。 Read a ってのが List a ってのや IO a ってのと 似た様に a をなんかでくるんでるモノってやつです。

Read a は、型 a がクラス Read のインスタンスでなければならない、という 制約です。 ここ参照

Main> read "123"
ERROR - Unresolved overloading
*** Type       : Read a => a
*** Expression : read "123"

Main> read "Hello"
ERROR - Unresolved overloading
*** Type       : Read a => a
*** Expression : read "Hello"

んー、どうもトップレベルは Read a ってやつの印字表現が分からず困ってる んでしょうか。そのままでは使えない感じです。でも、

Main> (read "123") + (read "456")
579 

ってのは動作してくれますねぇ。どういうこったろ。

Main> (read "Hello") ++ (read "World")
ERROR - Unresolved overloading
*** Type       : Read a => [a]
*** Expression : read "Hello" ++ read "World"

って感じでだめだしさぁ。(–;

ちゅうわけで再度この辺を読んでみます。さっきより若干なりとも触った経験があるので、少しは読めるようになってんじゃない?っていうとっても甘い考えです。

Read クラスには、その値を表現する文字列を構文解析する演算が用意されています。
Show クラスの最も単純な関数は show です。

だそうですね。これってあるデータオブジェクトの印字表現をXとするような データオブジェクトxがあったら、Read X により x を作りますよってことか な。だとすると、read “Hello” ってのはまずくて、 read “\”Hello\“” って しないとだね。

Main> read "\"Hello\""
ERROR - Unresolved overloading
*** Type       : Read a => a
*** Expression : read "\"Hello\""

は?もしかして受取り側がいるのかな。

Main> putStrLn $ read "\"Hello\""
Hello

うむ。どうもそうみたいね。では、 ++ に渡してみましょう。えいや!

Main> (read "\"Hello\"") ++ (read "\"World\"")
ERROR - Unresolved overloading
*** Type       : Read a => [a]
*** Expression : read "\"Hello\"" ++ read "\"World\""

あ、そっかすぐ忘れる。これでどーよ?

Main> putStrLn $ (read "\"Hello,\"") ++ (read "\"World\"")
Hello,World

おおーっ、ぱちぱちぱち。

Main> (read "123")::Int
123
Main> (read "\"123\"")::String
"123"
Main> (read "\"Hello, \"" ++ read "\"World!\"")::String
"Hello, World!"

お?何やら神のお告げによると、値の型を指定出来ちゃうんだ?んー、 :: っ て一体・・・?(+_+) Cで言えば強制的に値をキャストするようなもんだろか。

型を指定するというよりは、型推論とプログラマの意志の突き合わせができるという感じかなあ。

Main> ((read "123")::Int) + ((read "456")::Int)
579
Main> ((read "\"123\"")::String) ++ ((read "\"456\"")::String)
"123456"

うむ。これで所望の型に指定できちゃうわけね。なかなか便利じゃん。これ。

Main> read “\”Hello,\“” ++ " " ++ read “\”World!\“” “Hello, World!” Main> let x = read “123” in x + 0 123 Main> (\ x -> x + 0) (read “123”) 123 Main> read “123” `asTypeOf` length [1..] 123

ほう。

Main> let x = read "123" in x + 0
123

これ見た瞬間に awk の var “” とか var+0 とか思い出してしまった。どうも 周囲の型とつき合わせて、 辻褄が合うような解釈が可能なら、そういう型だ と解釈してくれる って感じかなあ。 でも、そうするってーと、

Main> (read "\"Hello\"") ++ (read "\"World\"")
ERROR - Unresolved overloading
*** Type       : Read a => [a]
*** Expression : read "\"Hello\"" ++ read "\"World\""

これと

Main> read "\"Hello,\"" ++ " " ++ read "\"World!\""
"Hello, World!"

これの差がわかんないね。なんで上のはエラーが発生しちゃったんだろ。(?_?) " " ってやつは空白文字1文字を含むリストだな。ん?もしかして read “\”Hello\“” は [a] であって a = Char までは解決してくんないのか。あー はいはい。 ++ はあくまでリスト同士をつなぐだけだからこいつは、中に格納 されている要素が ‘H’ だとか ‘e’ だとか評価せずに [a] ってリスト構造を そのまんま返すんだ。

・・・いやいや、やっぱ納得できてないや。そいつを受け取ったトップレベル は印字できねぇの?印字しようとして値を求めた瞬間に具体的に “Hello,World” って分かるはずだよね。んむむ〜。

とにかく " " ってのが具体的にリスト内の型を特定するのに役立っているん だろうけど、どうにも釈然としないぞ。順を追ってみようか。

Main> (read "\"Hello\"") ++ (read "\"World\"")

ここで “\”Hello\“” ってのは [‘“’,’H’,’e’,’l’,’l’,’o’,’”’] だよね。こい つに read を apply すると read 自身は String->a (但し a は Read a) だ から、 “\”Hello\“”自体が String ってのはいいんだ。こいつが Read a って のを返すんだな。あー、こいつに ++ を apply しようとしたってダメなんか? ++ は [b] と [b] とを引数にとるわけだから、 Read a なんてリストじゃな いものを渡したらそりゃ怒るわ。カンカンですわ。そっかトップレベルが印字 できねぇって怒ってるんじゃなかったのか?もしかして。

んじゃ、オッケーな方を検証してみようでないの。

Main> read "\"Hello,\"" ++ " " ++ read "\"World!\""

これは read “\”Hello,\“” ってした結果 Read a な a が得られるよ、と。 " " については [Char] だね。そうすっと ++ は [b]->[b]->[b] だから [b]->[Char]->[b] で b = Char だと。んで、 Read a な a は [b] なわけだ から a = [Char] だとみなされる?あーやっぱ awk の var “” を連想します ね。私は。

もっかいダメダメな方を考えると (read “\”Hello\“”) ++ (read “\”World\“”) は a ++ a (但し a は Read a)なんだけど、 ++ 自体は確か に [b]->[b]->[b] だから a はリストだとはみなしてくれるのかもしれない なぁ。ありゃ?(^^; だったら、やっぱリストとして ++ をしてくれて、トップレベルが印字しよう と評価した瞬間に String だと分かるんで無いか?やっぱダメじゃん。理解で きてねーじゃん。うぁぁああ。(+,+;;

  1. read “Hello” てしたら多分 Hello ってのを内部にもった Read オブジェクトを作るんだよね?
  2. read “\”Hello\“” ってしたら “Hello” ってのを内部にもった Read オブジェクトを作るんだろう。
  3. read “123” ってしたら 123 を内部にもつ Read オブジェクトを作るだろうし、
  4. read “\”123\“” なら “123” ってのを内部にもった Read オブジェクトを作るはず。

仮に read が Scheme? で言うところの read-from-string 的なものだとすれ ば、 1番目のやつはシンボルHelloなオブジェクトを作り出すだろう。 2番目 と4番目は文字列オブジェクトを作るし、 3番目のだと数値データオブジェク トを作るはず。

ただ、Haskellだとreadが返す時点では、まだシンボルだとか数値だとか文字 列だとかってのは分かってないんじゃないかと思うのだ。別に根拠ねーんだけ どさ。

shiro: たぶん、「ここで帰って来る値はこういうオブジェクト」という考え方をしない方がいいんじゃないかと思います。Schemeなんかだと、実際にメモリ上にある型タグ付きのオブジェクトに触っている感触がありますが、 Haskellの場合、実行前に型推論が解決してるので、実行時にオブジェクトの型を見る必要は無い。「何かを中に持つReadオブジェクト」なんて存在しないんですよ。実行時にはreadが何の型を返すかは既に決まっていて、それを実行時に判断する必要はない。ただ、そのためには、readが何の型を返すかがコンパイル時にわかってないとならないってわけです。

へぇっ。最初よくわからなかったんだけど、何度か反芻してるうちにようやく ウンウン!て激しくヘッドバンキング! くくぅ!年も考えずに変なコトしたから首の筋痛めたくさい・・・。osz

そっか。型推論と評価は完全に分離したフェーズなんだ。だから型推論してい るフェーズ(段階)では、値を求めた結果として分かる様な具体的な型っての は分からないよと。型推論の段階で決め切れなかった結果、 showメソッドが ないねぇって思われたらジエンドっすね?

ってことはだ、

Main> read "\"Hello,\"" ++ " " ++ read "\"World!\""

ここで " " をはさむって行為は ::[Char] って感じで型を指定(プログラマ の意図とすり合わせる?)のと同じ意味を持つんだ。もちろん、ここでは実際 に空白文字を一文字挟んじゃうわけだけど。

とか何とか思ってたら、Lazyってページに遅延評価についても、いろいろ解説 されてるようだよ。実にタイムリー!ってかオイラの理解が一向に好転しない んで見かねて解説はじめてくれちゃったか?

ふむふむと分かった気になるかと思ったが、また新たな敵(味方?)が・・・ WHNF? ってなんや〜!!

ってわけで google に教えてもらったら、haskell-jp の豊福さんのスレッド に遭遇。ふむふむ。やっぱ同じようなとこで同じような疑問を持つんだよなぁ と感心。しかしやはり WHNFってほとんど断りなく使ってるな。 Weak Head Normal Formってのか?なんのこったか分からんが[Lazy]には、

WHNF というのは、乱暴にいうと一番外側(の一番左)に
データコンストラクタが出てきた形、または、 λが出てきた形です。

だそうだ。この一番外の一番左ってのは、後続の具体例を読まないとイマイチ 釈然としなかったんだが、引数ってわけでもなさそうね。 show (1+1) だと show ってのがそうらしい。そいつが WHNF? になるまでは評価(簡約?)され るんだと。

うーむ。いろいろ出てきて自分が立っているところが分からなくなってきたよ。ガク。

ただ、haskell-jp のスレッドのNothingputCharのあたりをざーっと読ん で、Lazyもふんがーって読むと、

Prelude> 1 + 1

を入力すると、show (1 + 1)を「評価をする」というのが 出発点と考えられるわけです。

ってのが、知りたかったとこかもしれん。実質 show は print から必要とさ れているんで、段階を踏むんだけどさ。この show ってやつが、ここずーーーっ と引っ掛かってる部分なわけだったんだ。

とりあえず、確認のため :find print ってしてみると、

print     :: Show a => a -> IO ()
print      = putStrLn . show

ふむ。show して文字列にしてから putStrLn に渡すと。

あ、あとさっきの haskell-jp の話題でおぉっってのは「トップレベルのロジッ クはフツーに read-eval-print-loop だよ〜」ってとこ。但し eval はクセモ ノだけど。

その辺を気にかけながら、read とか show を使ってもっかい Haskell と対話 してみようか。

Main> show $ putStr "Hello"
"<<IO action>>"

Main> show [putStr "Hello",putStr "World"]
"[<<IO action>>,<<IO action>>]"

まずは噂の <> を拝んでおこう。 putStr “Hello” は印字までは 実行せずとも WHNF? ってやつになるらしく、 “Hello” とは印字せず、そうす る IO 型のオブジェクトになる。そいつを show に渡したら一応 show クラス らしくて印字表現があるため、 (っつっても <> だけだけど)って のを印字すると。二番目の例だと show が適用される段階では [IO a] だって ことなんだろうな。

Main> "Hello"
"Hello"

Main> show "Hello"
"\"Hello\""

Main> show $ show "Hello"
"\"\\\"Hello\\\"\""

Main> show $ show $ show "Hello"
"\"\\\"\\\\\\\"Hello\\\\\\\"\\\"\""

Main> show $ show $ show $ show "Hello"
"\"\\\"\\\\\\\"\\\\\\\\\\\\\\\"Hello\\\\\\\\\\\\\\\"\\\\\\\"\\\"\""

・・・爆笑。いや、オレってば何がしたいんだ?って。 えっと、何したかったんだか忘れちゃった。えーっと、これは “Hello” 自体 は印字形式は文字列 “Hello” になる。つまり、こいつは ‘H’,‘l’,‘l’,‘o’ になるね。こいつに show を適用すると、

show :: show a => a -> String

なので、この場合、 a 自体も String になっている。たまたまね。そのため に左右のダブルクォーテーションもリストのメンバに取り込まれるんだね。 ‘“’,’H’,’l’,’l’,’o’,’”’ってな感じにさ。さらにそいつがエ スケープされると。まぁ print も同じなんだろうな。

Main> print $ show "Hello"
"\"Hello\""

あれ? print も一発 show を含んでいるから show $ show "Hello" ってしたのと同じようになると思ったんだけど、なんでだろ?

Main> print "Hello"
"Hello"

Main> putStrLn "Hello"
Hello

あー、 putStrLn がこうなるんだっけ。これは返り値が文字列ってワケじゃな くて、イタコのチャネル(この場合には標準出力)に Hello ってディスプレ イするっていうアクションの結果として見えているんだな。出力先がファイル ディスクリプタだったら書きこまれるだけで、モニタ上にはなんも出ないと。

続たらいまわし

だいぶスタックの深いトコから一気に戻るけど、窒素酔いを起こさないよーに。 たらいまわしコマンドをHaskellで実装したわけだが、こいつを色々いじくり まわして遊んでみようじゃないかってことです。

っつーわけで再掲。

#!/usr/pkg/bin/runhugs

\begin{code}

import System

main :: IO ()
main = do args <- getArgs
          putStrLn $ numberToStr $ apply (tak) $ map (strToNumber) args

apply :: (a -> a -> a -> b) -> [a] -> b
apply f [x,y,z] = f x y z

numberToStr :: Int -> String
numberToStr num = if (num < 10)
                  then [intToDigit num]
                  else (numberToStr $ quot num 10) ++ [intToDigit $ rem num 10]

strToNumber :: String -> Int
strToNumber str = foldl1 (\x y->10*x+y) $ map digitToInt str

tak :: Int -> Int -> Int -> Int
tak x y z = if (x > y) then tak (tak (x-1) y z)
                                (tak (y-1) z x)
                                (tak (z-1) x y)
                       else y

\end{code}

まずは一度挫折している numberToStr の一時的な束縛を使ったコード。あの 後、神のささやきにて let,where を使うよろし!だって。(なぜに中国人風?)

numberToStr :: Int -> String
numberToStr num = let (q,r) = (quotRem num 10)
                  in (numberToStr q) ++ [intToDigit r]

こんな感じになるはず。多分。 let decl in body ってな具合です。んで emacs 上で試してみる。

Main> numberToStr 123
"
Process hugs illegal instruction (core dumped)

あ、がぁん!!Hugs殺しちゃったよ〜。そんなに悪いことした?オレ(++;アタフタ えっとーどういうこったろ。

Main> numberToStr 1
"
Process hugs illegal instruction (core dumped)

ダメだ。でもよーく見るとコアダンプの直前に " ってダブルクォーテーショ ン一個だけの断末魔の叫びが。

どうやら処理しようとはしてくれている。しばし考えててようやく分かりまし た。いやぁ、何とも間抜けなんだけど再帰で書いてて基底条件が無いじゃん。

numberToStr :: Int -> String
numberToStr num = let (q,r) = (quotRem num 10)
                  in if q == 0
                     then [intToDigit r]
                     else (numberToStr q) ++ [intToDigit r]

こんな風に in の中に書いてやる。そんでからプロンプトにぃ〜食らえ!!

Main> numberToStr 123
"123"
Main> numberToStr 987654321
"987654321"
Main> 

やたっ!ちなみに where 節ってのも使えるらしいから、試しておこう。

numberToStr :: Int -> String
numberToStr num | q == 0 = [intToDigit r]
                | otherwise = (numberToStr q) ++ [intToDigit r]
                where (q,r) = (quotRem num 10)

otherwise とかいけんのかな?って思ってたら大丈夫でした。えーっともしか して _ とか使えないかな?

                | _ = (numberToStr q) ++ [intToDigit r]

こうやって、ロードしてやると・・・

Type checking..................................................................
Compiling......................................................................
Reading file "/home/cut-sea/script/haskell/tak.lhs":
Parsing........................................................................
Dependency analysis
ERROR "/home/cut-sea/script/haskell/tak.lhs":27 - Illegal `_' in expression
System> 

あーだめか。 case っぽいのとはまた違うのかな?うーん。どうも整理できて ないんだよな。まーいーんだけどね。

‘_’はパターン部(’|‘の前)でしか使えません。ガード部(’|‘の後)には真偽値しか来ません。 ちなみに、’otherwise’ が使えるのは、Prelude で True と 定義 されているからです。

とにかく time とかで計測してみたけど、この三種類ではあんまし大差ない感 じ。ところが、意外だったのは神の提示された read を使っているコードが若 干遅めだったこと。これって凄い不思議な感じ。なんでかって?だって read って個人的には言語核の read-eval-print における read だと思ってたんだ よね。これは高速だろうなと、はい。

一方 numberToStr はっつーと別の関数として実装してて、一文字ずつ読み込 んでは変換してって作業をしているわけだから明らかに遅そうじゃん?一体全 体なんなんでしょう。もしかして read ってのは read-eval-print の read とは別モンなんだろうか。(–; それとも read 自体の問題じゃなくて他になんか遅くなる要因があるんだろう か。もしくは私のread は速えぇって感覚の方がおかしいんだろうか。

プロファイラとかあればいいんだろうけどなぁ。そういやデバッグの標準的な やり方とかも知らんな。なんとなくエラーメッセージからアタリつけたり、あ と神のツッコミだよりって感じ。あ、あと遅延評価(要は問題先送り精神のこ とね)。

http://cvs.haskell.org/Hugs/pages/users_guide/observe.html[ Hugs のマ ニュアル]によると、デバッグには Observe (もしくは Hugs.Observe)モジュー ルが使えるようです。このモジュールをインポートして、監視したい値の前に ‘observe “name”’ と付ければ、実行後に値を表示してくれます。

Observe> let f x = if x == 0 then 1 else x * observe "f" f (x-1) in f 10
3628800

>>>>>>> Observations <<<<<<

f
  { \ 9  -> 362880
  , \ 8  -> 40320
  , \ 7  -> 5040
  , \ 6  -> 720
  , \ 5  -> 120
  , \ 4  -> 24
  , \ 3  -> 6
  , \ 2  -> 2
  , \ 1  -> 1
  , \ 0  -> 1
  }

strToNumber = foldl1 (\x y -> 10 * x + y) . map digitToInt

に対して hugs +s で

Main> strToNumber "123"
123
(124 reductions, 212 cells)
Main> read "123" :: Int
123
(1048 reductions, 1537 cells)

でした。

readはただの関数でRead Intも /usr/local/lib/hugs/libraries/Hugs/Prelude.hs で定義されています。御参 考まで。

余計なお世話かもしれませんが、型推論の時のエラーと実行時のエラーを混同 されているように見受けられます。 (特に read の辺り) Hugs では、実行時のエラーは ‘Program error:’ と表示されます。

Prelude> [1] !! (-1)

Program error: Prelude.!!: negative index

ここまでの WayToHaskeller に載っているエラーメッセージで、 ‘Program error:’ と表示されているのは2箇所だけです。つまり、今までのエラーは、 ほとんど型推論の段階で起きていて、コードはいっさい実行されていない、と いう事になります。

ふむふむ。ちょっとしたデバッグプリントやオプションが使えるんだぁ。言わ れてみれば確かに read って色々分岐しまくってたな。 reduction ってのは 何回簡約されたかですな。cells ってのは消費したメモリセル? Lispのご本 尊みたいなものの消費量かなぁとか予想してみる。とりあえず簡約回数だけみ ても、あー read って何回も色々やることがあるんだぁってのが伺えちゃいま す。

デバッグの手段を知ろう

この辺りを知って、しかも話の流れからすると・・・たらいまわし関数の値の デバッグプリントとか見てみたくないですかい?わしゃ見たい!っちゅーわけ で見てみることにしてみましょう。はい。

まずは、Observe をインポートすんだね。import System の下あたりに追加します。

import System
import Observe  <= コレ

でもって emacs 上で Ctrl-c Ctrl-l でロードしてから、

Main> observe "tak" tak 6 3 0
6

>>>>>>> Observations <<<<<<

tak
  { \ 6 3 0  -> 6
  }

あれぇ? 6 3 0 じゃ小さいのか?そんな問題じゃねーよな。でも、一応確認 してみよう。

Main> observe "tak" tak 200 100 0
200

>>>>>>> Observations <<<<<<

tak
  { \ 200 100 0  -> 200
  }

うーん。やっぱ関係ないね。もっかい神の啓示を振り返ってみると、

Observe> let f x = if x == 0 then 1 else x * observe "f" f (x-1) in f 10

・・・あーっそっか!ハイハイ。デバッグプリントだった。評価するステップ で印字するんだ。

Main> let tak x y z = if (x > y)
                      then tak (observe "tak" tak (x-1) y z)
                               (tak (y-1) z x)
                               (tak (z-1) x y)
                      else y in tak 10 5 0
10

>>>>>>> Observations <<<<<<

tak
  { \ 9 5 0  -> 9
  , \ 8 5 0  -> 8
  , \ 7 5 0  -> 7
  , \ 6 5 0  -> 6
  , \ 5 5 0  -> 5
  , \ 3 0 6  -> 6
  , \ 2 0 6  -> 6
  , \ 1 0 6  -> 6
  , \ 0 0 6  -> 0
  , \ 3 0 7  -> 7
  , \ 2 0 7  -> 7
  , \ 1 0 7  -> 7
  , \ 0 0 7  -> 0
  , \ 3 0 8  -> 8
  , \ 2 0 8  -> 8
  , \ 1 0 8  -> 8
  , \ 0 0 8  -> 0
  , \ 3 0 9  -> 9
  , \ 2 0 9  -> 9
  , \ 1 0 9  -> 9
  , \ 0 0 9  -> 0
  , \ 3 0 10  -> 10
  , \ 2 0 10  -> 10
  , \ 1 0 10  -> 10
  , \ 0 0 10  -> 0
  }

おおぉっ!でけたでけた。ぱちぱちぱち。 一方Schemeインタプリタだと、どうなるかってーと、

gosh> (define (tak x y z) (if (> x y)
                              (tak #?=(tak (- x 1) y z)
                                      (tak (- y 1) z x)
                                      (tak (- z 1) x y))
                              y))
tak

さぁ、試してみましょう。

gosh> (tak 10 5 0)
      :
      :

・・・(+_+)えぇ、とても書き込めません。そんな必要無いですし。 しかし、最初の引数を observe しただけでもアレですから大変なもんです。 全部を observe したらどうなるでしょうかね。

Main> let tak x y z = if (x > y)
                      then tak (observe "tak" tak (x-1) y z)
                               (observe "tak" tak (y-1) z x)
                               (observe "tak" tak (z-1) x y)
                      else y in tak 10 5 0
10

>>>>>>> Observations <<<<<<

tak
  { \ 9 5 0  -> 9
  , \ 8 5 0  -> 8
  , \ 7 5 0  -> 7
  , \ 6 5 0  -> 6
  , \ 5 5 0  -> 5
  , \ 4 0 6  -> 6
  , \ 3 0 6  -> 6
  , \ 2 0 6  -> 6
  , \ 1 0 6  -> 6
  , \ 0 0 6  -> 0
  , \ (-1) 6 1  -> 6
  , \ (-1) 6 2  -> 6
  , \ (-1) 6 3  -> 6
  , \ (-1) 6 4  -> 6
  , \ 4 0 7  -> 7
  , \ 3 0 7  -> 7
  , \ 2 0 7  -> 7
  , \ 1 0 7  -> 7
  , \ 0 0 7  -> 0
  , \ (-1) 7 1  -> 7
  , \ (-1) 7 2  -> 7
  , \ (-1) 7 3  -> 7
  , \ (-1) 7 4  -> 7
  , \ 4 0 8  -> 8
  , \ 3 0 8  -> 8
  , \ 2 0 8  -> 8
  , \ 1 0 8  -> 8
  , \ 0 0 8  -> 0
  , \ (-1) 8 1  -> 8
  , \ (-1) 8 2  -> 8
  , \ (-1) 8 3  -> 8
  , \ (-1) 8 4  -> 8
  , \ 4 0 9  -> 9
  , \ 3 0 9  -> 9
  , \ 2 0 9  -> 9
  , \ 1 0 9  -> 9
  , \ 0 0 9  -> 0
  , \ (-1) 9 1  -> 9
  , \ (-1) 9 2  -> 9
  , \ (-1) 9 3  -> 9
  , \ (-1) 9 4  -> 9
  , \ 4 0 10  -> 10
  , \ 3 0 10  -> 10
  , \ 2 0 10  -> 10
  , \ 1 0 10  -> 10
  , \ 0 0 10  -> 0
  , \ (-1) 10 1  -> 10
  , \ (-1) 10 2  -> 10
  , \ (-1) 10 3  -> 10
  , \ (-1) 10 4  -> 10
  }

Main> 

スゴイデスネ〜ワタクシビックリギョウテンデゴザイマス〜。 こりゃ速いハズだわ。うん。ちなみに observe したやつはコマンドラインか ら ./tak.lhs 10 5 0 とかってしても印字はされません。投げてるポートか違 うんでしょうね。

でもってよーく考えてみると、事実上たらいまわし関数の値を求めるのに必要 な評価ってのはこれだけで済む訳で、考えようによっては、これって一種のコ ンパイラの最適化じゃない?

さらに trace なんかもあるらしい。こいつも試してみよう。 Everyday:2004-10-31を参考にしてみる。

apply :: (a -> a -> a -> b) -> [a] -> b
apply f [x,y,z] = trace ("trace:"++show x++","++show y++","++show z++"=") $ f x y z

さあ、これでどーよ?

Type checking
ERROR "/home/cut-sea/script/haskell/tak.lhs":31 - Cannot justify constraints in explicitly typed binding
*** Expression    : apply
*** Type          : (a -> a -> a -> b) -> [a] -> b
*** Given context : ()
*** Constraints   : Show a

Trace> 

?! Cannot justify constraints in explicitly typed binding って型があ わねぇっておっしゃってるんだろうか。 show a がまずいのかな?ってゆーか、 もしかしてこうかい?

-- apply :: (a -> a -> a -> b) -> [a] -> b
apply :: (Int -> Int -> Int -> Int) -> [Int] -> Int
apply f [x,y,z] = trace ("trace:"++show x++","++show y++","++show z++"=") $ f x y z
apply :: Show a => (a -> a -> a -> b) -> [a] -> b

でもうまくいきます。

どうかな?

Main> apply tak [6,3,0]
trace:6,3,0=6
Main> 

あ、おっけーですね。でもまた同じ間違いをしちゃいました。こんなトコに書 いたってしょーがねーじゃんね。

tak :: Int -> Int -> Int -> Int
tak x y z = if (x > y)
            then trace ("trace:"++show x++","++show y++","++show z++"\n") $ tak (tak (x-1) y z)
                                                                                (tak (y-1) z x)
                                                                                (tak (z-1) x y)
            else y

ここでした。これで一応それっぽい動きが確認できますな。

Main> tak 6 3 0
trace:6,3,0
trace:5,3,0
trace:4,3,0
trace:2,0,4
trace:1,0,4
trace:2,0,5
trace:1,0,5
trace:2,0,6
trace:1,0,6
6

ってね。ぱちぱちぱち〜。 でも正直 observe の方が便利な気がするんですけどね。それって gosh の #?= に慣れちゃってるからかなぁ。

いずれにせよデバッグの秘宝も手にしたし、ページもでかくなって来てそろそ ろ編集するのも辛いので (すでに理由をナメてんな)よちよち歩きへGO!!

【ちょっとひとやすみ】メイビー?

やっぱりまだまだ先。。。

(「つかまり立ち」を編集する)|(Haskellerへの道)


Last modified : 2006/06/12 12:48:43 JST