mltermでShift+PageUpが効かない問題
Xming経由でmltermを使っていて、気が付いたら Shift+PageUp でバッファをバックスクロールするのができなくなっていた。mlterm-configでも関連する項目が見当たらないし、しばらく放置してたんだけど、ようやく解を発見。
431 ： login:Penguin： sage：2010/07/28(水) 18:08:41 ID:znyBZ/Pg
>>338だけど
あれ以来ずっと忘れていたけど、ふと魔がさして
maskを外してmlterm-3.0.1にしてみた。
相変わらずスクロール不可だったけど、~/.mlterm/key に
Shift_L+Prior=PAGE_UP
の一行を加えると従来どおりスクロール可になった。
（デフォルトはShift+Prior=PAGE_UP）
ちなみになぜか右のシフトキーでも動作する。
意味不明だけどとりあえずclose。
PCまとめ - Gentoo Linux 30
上と同様の対策をしたところ改善。環境によってmodifierがうまく取れなかったりするんだろうか。
"例外は共有の秘密である"
Exceptions are shared secrets | Existential Type の内容が興味深かったので試訳してみました。
It's quite obvious to me that the treatment of exceptions in Haskell is wrong. Setting aside the example I gave before of an outright unsoundness, exceptions in Haskell are nevertheless done improperly, even if they happen to be sound. One reason is that the current formulation is not stable under seemingly mild extensions to Haskell that one might well want to consider, notably any form of parameterized module or any form of shadowing of exception declarations. For me this is enough to declare the whole thing wrong, but as it happens Haskell is too feeble to allow full counterexamples to be formulated, so one may still claim that what is there now is ok … for now.
私から見て、Haskellにおける例外の取り扱いが誤っているのは全く明らかだ。以前例に挙げたあからさまな不健全性の例はともかく、Haskellにおける例外は、仮にそれが健全に発生したとしても、不適切に処理されている。一つの理由は、現在の定式化は、誰でも思い付きそうなマイルドな拡張に対しても安定でないことだ。パラメタライズされたモジュールや、例外の宣言のシャドウイングについては特に。私からすれば、これだけでも「全てが間違っている」と宣言するには十分だ。しかし、あいにくHaskellは全ての反例を定式化しきれない程度に貧弱なため、「今のところは大丈夫じゃないか」と反論することはそれでも可能だった。……今までは。
But I wish to argue that Haskell exceptions are nevertheless poorly designed, because it misses the crucial point that exception values are shared secrets. Let us distinguish two parties, the raiser of the exception, and the handler of it. The fundamental idea of exceptions is to transfer a value from the raiser to the handler without the possibility of interception by another party. While the language of secrecy seems appropriately evocative, I hasten to add that I am not here concerned with “attackers” or suchlike, but merely with the difficulties of ensuring modular composition of programs from components. In such a setting the “attacker” is yourself, who is not malicious, but who is fallible.
しかし、私はそれでもなおHaskellの例外はまずい設計だと述べておきたい。なぜかといえば、例外の値というのは共有の秘密であるという最も重要な視点が抜けおちているからだ。プログラムを二つの関係者に分けて考えてみよう。例外の発生元と、発生した例外の受け取り先だ。例外の基本原理は、ある値を、他のどんな関係者にも傍受されることなく、例外の発生元から、例外の受け取り先へと転送することだ。秘密というといらぬ刺激をかきたててしまいそうだが、ここで言っておかねばならないのは、私が問題にしているのはいわゆる「攻撃者」のようなものではなく、単に、プログラムを複数のコンポーネントに分けてモジュラーに組み合わせられることを保証することの難しさだ。この場合、「攻撃者」というのはあなた自身だ。悪意はないが、誤りを犯しがちな。
By raising an exception the raiser is “contacting” a handler with a message. The raiser wishes to limit which components of a program may intercept that message. More precisely, the raiser wishes to ensure that only certain previously agreed-upon components may handle that exception, perhaps only one. This property should remain stable under extension to the program or composition with any other component. It should not be possible for an innocent third party to accidentally intercept a message that was not intended for it.
例外を発生させることで、例外の発生元は、何らかのメッセージによって例外の受け取り先と「契約を交わす」。例外の発生元は、そのメッセージを傍受しうるプログラムのコンポーネントをなるべく制限したいと考える。もっと正確にいえば、例外の発生元は、前もって確実に同意したコンポーネントにしか例外を受け取らせたくない。そして、そのコンポーネントはおそらく1つだけだろう。この性質はプログラムを拡張した場合や、ほかのどんなコンポーネントを組み合わせた場合にも安定に保たれるべきだ。善意の第三者が、受け取るはずでなかったメッセージを予期せず受け取ってしまうということがあるべきではない。
Achieving this requires a secrecy mechanism that allows the raiser and the handler(s) to agree upon their cooperation. This is accomplished by dynamic classification, exactly as it is done properly in Standard ML (but not O'Caml). The idea is that the raiser has access to a dynamically generated constructor for exception values, and any handler has access to the corresponding dynamically generated matcher for exception values. This means that the handler, and only the handler, can decode the message sent by the raiser; no other party can do anything with it other than pass it along unexamined. It is “perfectly encrypted” and cannot be deciphered by any unintended component.
これを達成するには、例外の発生元と受け取り先が協力関係に同意するための機密保証の仕組みが必要だ。この仕組みは、dynamic classificationによって正確に達成可能であり、Standard MLでは正しく実装されている(しかしOCamlではそうなっていない)。Dynamic classificationとは、例外の発生元は動的に生成された例外コンストラクタにアクセスでき、例外の受け取り先は、それと対応する動的に生成された例外マッチャにアクセスできるというアイディアだ。これは、例外の受け取り先が、そして受け取り先だけが、発生元が送ったメッセージを復号できるということを意味する。つまり、他の関係者はそれを無検査で通過させることしかできない。このメッセージは「完璧に暗号化され」、受け取ることが意図されていないいかなるコンポーネントによっても復号されることはない。
The usual exception mechanisms, as distinct from exception values, allow for “wild-card handlers”, which means that an exception can be intercepted by a third party. This means that the raiser cannot ensure that the handler actually receives the message, but it can ensure, using dynamic classification, that only a legitimate handler may decipher it. Decades of experience with Standard ML shows that this is a very useful thing indeed, and has application far beyond just the simple example considered here. For full details, see my forthcoming book, for a full discussion of dynamic classification and its role for ensuring integrity and confidentiality in a program. Dynamic classification is not just for “security”, but is rather a good tool for everyday programming.
よくある例外機構は、例外の値は別にして、例外の「ワイルドカード受け取り」を許している。これは、例外が第三者によって横取りされ得ることを意味する。これでは、例外の発生元は例外の受け取り先が確実にメッセージを受信することを保証できないが、dynamic classificationを使えば、正規の受け取り先だけがメッセージの内容を復号できることを保証できる。Standard MLでの長年の経験は、これは実に有用で、ここで考えたようなシンプルな例を遥かに越える応用性があることを示している。詳細については、近々出版予定の私の著書を読んで欲しい。そこでは、dynamic classificationと、それがプログラムにおける一貫性と機密性の保証について果たす役割について詳しく議論している。Dynamic classificationは単に「安全性」のためだけでなく、日々のプログラミングにおける非常によい道具となる。
So why does Haskell not do it this way? Well, I'm not the one to answer that question, but my guess is that doing so conflicts with the monadic separation of effects. To do exceptions properly requires dynamic allocation, and this would force code that is otherwise functional into the IO monad. Alternatively, one would have to use unsafePerformIO --- as in ezyang's implementation --- to “hide” the effects of exception allocation. But this would then be further evidence that the strict monadic separation of effects is untenable.
じゃあ何でHaskellはこの方法を採用しないんだろう？はて、私はこの質問に答える立場にないが、おそらくモナドによる副作用の分離と非常に相性が悪いからではないか、と考えている。例外を正しく扱うには動的なアロケーションが必要で、それが無ければ関数的だったコードを、IOモナドに押し込むことになる。これを避けようとすれば、例外のアロケーションという副作用を「隠蔽」するために、 unsafePerformIO を使わなければならない。 ezyang の実装のように。しかしそうすると、これはモナドによる厳密な副作用の分離は支持できないということの更なる証拠となってしまう。
追記(原文での追記部分)
Update: This account of exceptions also makes clear why the perennial suggestion to put exception-raising information into types makes no sense to me. I will write more about this in a future post, but meanwhile contemplate that a computation may raise an exception that is not even in principle nameable in the type. That is, it is not conservativity that’s at issue, it’s the very idea.
この例外についての議論で、なぜ長年私が、例外発生についての情報を型に記述することに意味がないと述べてきたのかについてもはっきりした。これについては今後の記事でより詳しく述べていくが、同時に、例外を発生させ得る計算が原理的にも型で言い表せないことについても考察していく。(訳注:最後の一文の意味がとれず。)
IOがコンテナでありFunctorでもあるということ その1
モナドは「プログラム可能コンテナ」(by kazu_yamamotoさん, モナモナ言わないモナド入門 第2版)である、という考え方でIOを理解しようとしてみたのでちょっと書いてみる。
fmapとjoinによるモナドの定義
class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a
となっている。一方で、Philip Wadlerによる1992年初出の論文、Monads for functional programmingでは、以下のような定義も書かれている(p12)。(この論文ではbind演算子(>>=)が⋆, return相当の関数がunitという名前になっているので、適宜読み替える)
map :: (a -> b) -> m a -> m b map f m = m >>= \a->return (f a) join :: m (m a) -> m a join z = z >>= \m->m
ぱっと見、何がなんだかよくわからないが、ここでいうmapはシグネチャをみてわかるとおりFunctorクラスのfmapと同じモノである。
class Functor f where fmap :: (a -> b) -> f a -> f b
以下、mapを(Listのmapと区別する意味で)fmapと読み替える。そうすると
fmap :: (a -> b) -> m a -> m b fmap f m = m >>= \a->return (f a) join :: m (m a) -> m a join z = z >>= \m->m
となる。ひとまず、ここで定義したfmapがFunctorにおけるfmapと同じ意味になるかをListで確認してみよう。Listにおける(>>=), returnは
instance Monad [] where m >>= k = concat (map k m) return x = [x] fail s = []
であるから、
fmap f m = m >>= \a->return (f a) = concat (map (\a->return (f a)) m) = concat (map (\a->[f a]) m) -- map (\a->[f a]) [m0,m1,...] = [[f m0],[f m1],..] -- concat [[f m0],[f m1],...] = [f m0,f m1,...] = map f m
となって、めでたくListにおけるfmapはmapと同じであると導けた。
では、joinとはなんじゃらほい。
join : 二重構造を潰す演算子
上述のとおり、joinのシグネチャは "m (m a) -> m a" となっている。これも先ほどと同じくListを例に意味を確認してみよう。Listにおける(>>=)の定義を用いて展開すると、
join :: [[a]] -> [a] join z = z >>= \m->m = concat (map (\m->m) z) = concat (map id z) = concat (id z) = concat z
となって、join = concat となってしまった。
ここでListモナドの定義を振り返ってみると
m >>= k = concat (map k m) -- fmap = map, join = concat だから m >>= k = join (fmap k m)
と書ける。実はこの定義が、Listに限らず他のモナドでも同様に使えることを以下で確認していく。
「モナド = 二重構造を作って潰すこと」と理解してみる
Listにおける(>>=)の仕事は、
- k :: a -> [b] をfmapして [a] から二重リスト [[b]] を作り、
- join :: [[b]] -> [b] で二重リストを一重リストに潰す
ということだった。これが別のモナド、例えばMaybeではどうなるかを見てみよう。
Maybeのfmapの定義は
instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just x) = Just (f x)
となっている。(Haskell 2010 Standard Prelude)ではこれに合わせてjoinを定義してみよう。
join :: Maybe (Maybe a) -> Maybe a join Nothing = Nothing join (Just (Nothing)) = Nothing join (Just (Just x)) = Just x -- ∴ join (Just x) = x
これを、joinとfmapによる(>>=)の定義に適用してみる。
-- m >>= k = join (fmap k m) Nothing >>= k = join (fmap k Nothing) = join Nothing = Nothing (Just x) >>= k = join (fmap k (Just x)) = join (Just (k x)) = k x
となり、めでたくMaybeモナドの定義
instance Monad Maybe where (Just x) >>= k = k x Nothing >>= k = Nothing
と一致した。
読者におかれましてはまったくIOのアの字も出てこないのでやきもきされていることとは思うが、長くなったので次回へ続く。
和音の擬人化
ちょっと面白いエントリを見かけたのでわかる範囲で訳してみる。
(AとかBとかC+とかいうのは胸のサイズ？)
5：妹，病娇。A
4：青梅竹马，眼睛娘，天然。B
4: 幼馴染、眼鏡っ娘、天然。
(青梅竹馬というのは「竹馬の友」と同じ語源の故事成語。ただし「竹馬の友」と違って「男女の幼馴染」を指すらしい)
参考: 青梅竹马_百度百科
Maj7：偷窥狂，隐藏御姐属性。C
Maj7: 覗き魔、隠れ姉属性(？)。
Aug4：小恶魔。B+
Aug4: 小悪魔。
Maj3/Min3：双胞胎，姐姐喜欢做饭，妹妹控 BL。C/B
Maj3/Min3: 双子。姉は料理好き。妹は腐女子(=控BL)。
Maj2：治愈系班长，黑长直。C+
Maj2: 癒し系委員長。黒髪ストレート。
参考: 黑长直_百度百科
Min2：主角的女性人格，只在病中出现。A
Min2: 主人公の女性人格。体調不良時のみ出現。
Dom7：学生会长，女王，两性双杀。D
Dom7: 生徒会長、女王様キャラ、両性キラー(？)
Maj6：房东大姐姐，剑道，举止端庄。C+
Maj6: 大家(房东)のおねーさん、剣道、おしとやか系。
Min6：新搬来的邻居，萝莉，最喜欢甜食，傲娇。A
Min6: 隣の部屋に新しく引っ越してきた。ロリ(萝莉)、スイーツ大好き、ツンデレ(傲娇)。
参考: 萝莉_百度百科, 傲娇_百度百科
没救了。。。
「救いがねぇ……」
音楽やってる方はこれわかるんでしょうか……^^;;
エンジニアとして尊重されるってどういうことだろう
以下の記事を読んで、同じ「ソフトウェアエンジニア」として思ったところがあるので、記しておく。
尊重されたいすべてのソフトウェアエンジニアへ - tagomorisのメモ置き場
「尊重される」って？
まず、自分の言語感覚として、この記事では「尊重される」という言葉が随分多義的に使われているように見受けられた。
とはいえ唯々諾々とつまんない仕事ばっかりやる毎日はできればごめんだと思っている。コードを書くのは楽しいからコードを書ける仕事をしたいし、特に面白い問題やまだ誰も手をつけてなさそうな問題を解決する仕事ができれば最高だ。
つまり、そう、尊重されたい。自分のやれること、やりたいことを尊重されるようになりたい。自分がやった仕事には価値があると思われるのは嬉しいし、そのように(勤務先以外の)他人から認められれば面白い話も聞けるようになるかもしれない。尊重されるソフトウェアエンジニアになれれば楽しそうだ。
尊重されたいすべてのソフトウェアエンジニアへ - tagomorisのメモ置き場
この部分を読むと、「自分が一個の人格として尊重される」「自分の希望・願望が尊重される」「自分が出した成果が尊重される」というようなことをすべて「尊重される」という一言で表現しようとしているように見える。ただ、自分の感覚としてそれらは全て別々のことだ。
「自分のやれることを尊重される」というのは、自分の能力を理解し、それに合った仕事を適切に振ってもらえることだ。
「自分のやりたいことを尊重される」というのは、自分の願望を理解し、認めてもらえることだ。ただし、それは必ずしも仕事と直結するかどうかはわからない。
「自分が出した成果が尊重される」というのは、「自分がやったこと」の意義を誰かに理解してもらえたり、自分が属する組織や社会から評価してもらえたりすることだ。これは、エンジニアとしての能力とは別に、どういうプロジェクトに関わることができたか、また関わったプロジェクトが成果を出せたかどうかというような、「運」が大きく関わる側面でもある。
「自分の人格が尊重される」というのは、能力の多寡に関わらず、一人の人間としてその存在を尊重してもらえるかどうかだ。いくら問題解決能力にすぐれ、業務遂行能力があり、人並み外れた交渉力やプレゼンテーション能力があったとしても、周囲の人間に対する態度、部下との接し方、プライベートでの言動などなど、様々な要因でけむたがられている人、場合によっては恨まれていたりする人というのはいる。また、いくら「エンジニア」として問題解決能力にすぐれていても、必ずしも組織や社会で適切とされる振る舞いができず、「変人」「困った人」扱いされるいわゆる「ギーク」「ハッカー」というような人種もいる(c.f. 管理職のためのハッカー FAQ )。
私は上の中で言えば、どちらかというと「自分のやれることを尊重され」たい人間なんだと自覚している。加えて言えば、「誰に」「尊重して」もらいたいかという範囲がたぶんかなり小さいし、尊重といっても、むしろ「理解」を重視する人間だ。たとえ批判的意見であっても、私が認識した自己と相手が認識した私の像が一致していると、ときとして凄くうれしくなる。
正直、おそらく私はまともな社会人としては周囲から認識されていないと思う。時間や締め切りは守れない、アウトプットは不安定、空気は読まない、思い込めば突っ走る。組織の中で働くものとしては著しく不適格だ。
だけど、それでも「自分ができること」については直属のボスを含むいくらかの人からは認められているという自負がある。というより、周囲の他の人ができない(それどころか、どうやっていいかすらおそらく想像がつかない)ようなことを気まぐれのようなノリでさくっとやってのけてしまうので、「認めざるを得ない」といった方がいいかもしれない(……まぁおかげで、なかなか他の人に代わりをやってもらうことができないんだけど)。
閑話休題。
ここまで書いて、やっぱり「尊重」という言葉の使い方に違和感を覚える。尊重って「あなたの考えは尊重しますよ」みたいに、悪く言えばあまり踏み込まない、どちらかといえば傷つけないように「大事にする」という態度だと私は思うんだけど、「尊重されたい！」みたいな進んでもっともっとと求めるようなものだっけ？
次の一節を読んでも、彼の主張は、私の考える「尊重」よりもっと踏み込んだことを述べているように見える。
例え話で申し訳ないが、たとえば世の中に服飾デザイナーという仕事がある。服飾デザイナーのうちごく一部の人達は極めて有名で世間的にも尊重されていることを自分達ですら知っている。
が、もちろんそれをもって服飾デザイナーという仕事に就いている人々全体が尊重される位置にいるかというと、そんなことは、もちろん全くない。尊重される位置にいるのはごくごく一部であり、その他の大多数については特別な尊重を受けるということも多分なく、淡々と毎日の仕事をしている。どのような給与体系・契約習慣なのかは寡聞にして知らないが、おそらく特別に優遇されるということはないと思う。そのような人達が、たとえば自分やあなたが毎日着ているTシャツや短パンやポロシャツやトランクスや靴下のデザインをやっている。
尊重されたいすべてのソフトウェアエンジニアへ - tagomorisのメモ置き場
なんか違うと思う。これじゃ、服飾デザイナーみんなが、ISSEY MIYAKEみたいなごくごく一部の人を除いて、「尊重されてない」つまり職業人として大事にされてないみたいじゃないか。そりゃ、社会には色んな職場があって、こき使われて給料も地位も低いみたいなところだってあるのはわかる。でも、大多数の人は、それぞれの地位でそれなりに仕事を尊重されながら生きてるもんなんじゃないのかな。
「ソフトウェアエンジニア」という仕事
だから、世の中の人が毎日使っている給与計算システムや税金収集システムや銀行ATMや流通管理システムのプログラミングだけをやっている人間が、特別に尊重もされず、特に名前を知られることもなく、他の仕事とあんまり変わらない契約体系(時間あたりいくら)の金額で仕事をしているのは、たぶん正しい。他に同じことをやっている人が大勢いるからだ。ソフトウェアエンジニアだけがそうであってはいけない、なんてことはない。
尊重されたいすべてのソフトウェアエンジニアへ - tagomorisのメモ置き場
ここを読んで、彼が考える「ソフトウェアエンジニアリング」って、随分狭い世界なんだな、と思った。およそ世の中に存在する「ソフトウェアエンジニア」がみんながみな、ここに挙がったいわゆる「業務アプリ」の類ばかりを書いてるわけじゃない。VoIPモデムのファームウェアを書いている人もいれば、携帯電話やスマートフォンのカメラに搭載する顔認識のアルゴリズムを開発してる人もいれば、DNAシーケンサから出てきた大量のデータを処理するソフトウェアを書いている人もいれば、医療用画像診断機器の画像処理エンジンを開発してる人もいれば、ソースコードのメトリックを解析するソフトウェアを開発してる人もいれば、あるいは我々が全く想像がつかないような分野のソフトウェアを書いている人もいるだろう。
確かに、いわゆる「業務アプリ」のようなものを日々書いている人たちは、職場を変えれば彼の言うようなオープンソース的な流儀で自分の仕事をアピールして、そうやって公開したソースコードを評価してもらえるような立場に移れるかもしれない。
だけど、上に挙げたような専門性の高い分野では(よいソースコードの価値が低いとはもちろん言わないが)、「どういうソースコードを書けるか」以前に、「何ができるのか」「どういう技術をもっているか」が重要視される。そういう世界では、まずは、目的とするアプリケーションの要素技術を実現できるかがそもそも重要で、ソースコードの質がどうかなんていうのは二の次だし、目に留まった人が書いた「ソースコード」をつぶさに読んでその人を評価するなんでことは稀だろう。
しかも、そういった専門性の高い、もしかするとR&Dといったような性質に近い分野では、そもそもソフトウェアというのは重要なノウハウ、資産なのでおいそれとgithubに公開したりといったことは出来ない。それは職場を変えたからほいほいと実現されるようなことでもない。
もちろん「ソースコードが云々」という点に引っかかりを感じているだけで、外部と積極的に交流を持つことには大賛成だ。ただし、それは彼の言うようなオープンソース的流儀とは違う形態であるかもしれない。カンファレンスやシンポジウムで技術報告をしたり、そういった場で同じ分野の人間とディスカッションをしたり、あるいは有志で勉強会を開いたり、やり方はいろいろあるだろう。
多分、私と彼とでは経験してきた世界が違うんだろうと思う。もしかすると彼は毎日クソつまらない業務アプリを書くことに明け暮れて、くたびれた、向上心のないエンジニアを沢山見てきたのかもしれない。私はどちらかといえば、他に誰もやってない、一人一殺的な仕事で活躍する人を身の回りで多く見てきた。だから、「毎日クソつまらないソフトウェアを書くだけの世界から脱出するには」という視点になるんだろうし、ソースコードを公開して自分のプレゼンスをアピールしていこうという考え方になるのかもしれない。
そんなところ。
(ソースコードの公開を「自己アピール」だと考えることにも私は異議があるんだけど、それはまた別の稿で。気が向いたら)
Haskellの foldr と foldl と foldl'
前の記事で、Haskellでfoldlを使った場合の動作について書きました。
ここで、Haskellでfoldlを実際に使ってみて動作を確認してみようと思います。
{- fold1.hs -} import Data.List result = foldl (&&) True (map even [1..1000000]) main = print result
colinux> ghc --version The Glorious Glasgow Haskell Compilation System, version 7.0.4
colinux> ghc fold1.hs [1 of 1] Compiling Main ( fold1.hs, fold1.o ) Linking fold1 ... colinux> /usr/bin/time ./fold1 Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. Command exited with non-zero status 2 0.58user 1.23system 0:01.91elapsed 94%CPU (0avgtext+0avgdata 361712maxresident)k 0inputs+0outputs (0major+22665minor)pagefaults 0swaps
あっという間にスタックオーバーフローしました。
代わりに foldl' を使ってみます。
{- fold1_.hs -} import Data.List result = foldl' (&&) True (map even [1..1000000]) main = print result
同じく実行してみます。
colinux> ghc fold1_.hs [1 of 1] Compiling Main ( fold1_.hs, fold1_.o ) Linking fold1_ ... colinux> /usr/bin/time ./fold1_ False 0.08user 0.00system 0:00.08elapsed 100%CPU (0avgtext+0avgdata 7328maxresident)k 0inputs+0outputs (0major+515minor)pagefaults 0swaps
ほぼ一瞬で実行が終了しました。
foldrでも試してみます。
{- fold2.hs -} import Data.List result = foldr (&&) True (map even [1..1000000]) main = print result
colinux> ghc fold2.hs [1 of 1] Compiling Main ( fold2.hs, fold2.o ) Linking fold2 ... colinux> /usr/bin/time ./fold2 False 0.00user 0.00system 0:00.00elapsed ?%CPU (0avgtext+0avgdata 5264maxresident)k 0inputs+0outputs (0major+386minor)pagefaults 0swaps colinux>
実行時間が短くて比較になりませんが、max resident sizeが若干小さくなっています(7328k -> 5264k)。
スタックオーバーフローしたfoldl版はともかく、foldl'とfoldrの実行時間が比較にならなかったので、リストのサイズを100倍にしてみました。
foldl'での実行結果
colinux> ghc fold1__big.hs [1 of 1] Compiling Main ( fold1__big.hs, fold1__big.o ) Linking fold1__big ... colinux> /usr/bin/time ./fold1__big False 3.75user 0.00system 0:03.75elapsed 100%CPU (0avgtext+0avgdata 7312maxresident)k 0inputs+0outputs (0major+514minor)pagefaults 0swaps
foldrでの実行結果
colinux> ghc fold2_big.hs [1 of 1] Compiling Main ( fold2_big.hs, fold2_big.o ) Linking fold2_big ... colinux> /usr/bin/time ./fold2_big False 0.00user 0.00system 0:00.00elapsed ?%CPU (0avgtext+0avgdata 5264maxresident)k 0inputs+0outputs (0major+387minor)pagefaults 0swaps
foldl'では実行時間がかなり延びましたが、foldrは相変わらず計測不能な時間内に終了しました。
最適化を有効にしてみると……
ちなみに、 ghc -O2 で最適化を有効にすると、foldl と foldl' の差がほとんどなくなります。
foldl(入力リストのサイズは100,000,000)
colinux> ghc -O2 fold1_big.hs [1 of 1] Compiling Main ( fold1_big.hs, fold1_big.o ) Linking fold1_big ... colinux> /usr/bin/time ./fold1_big False 1.71user 0.00system 0:01.72elapsed 99%CPU (0avgtext+0avgdata 7184maxresident)k 0inputs+0outputs (0major+506minor)pagefaults 0swaps
foldl'(同条件)
colinux> ghc -O2 fold1__big.hs [1 of 1] Compiling Main ( fold1__big.hs, fold1__big.o ) Linking fold1__big ... colinux> /usr/bin/time ./fold1__big False 1.81user 0.01system 0:01.82elapsed 100%CPU (0avgtext+0avgdata 7184maxresident)k 0inputs+0outputs (0major+506minor)pagefaults 0swaps
それでも、最適化なしのfoldrには追いつけませんでした。
Haskellの評価戦略とfoldl/foldr (2)
前の記事 d:id:linglang:20110909:1315561320 で、
foldl (<+>) (z<+>a0) (a1:[a2,a3,a4,a5,a6])
という式を評価するとき、2通りの簡約(計算)順序があることを示しました。
foldl (<+>) b0 (a1:[a2,a3,a4,a5,a6]) {- 内部簡約 -} foldl (<+>) ((z<+>a0)<+>a1) (a2:[a3,a4,a5,a6]) {- 最外最左簡約 -}
Haskellでfoldlを評価する
今度は、Haskellの評価戦略である、最外最左簡約でfoldlを評価してみます。
一番外側から順に展開していくので...
result = foldl (<+>) z (a0:[a1,a2,a3,a4,a5,a6]) = foldl (<+>) (z<+>a0) (a1:[a2,a3,a4,a5,a6]) = foldl (<+>) ((z<+>a0)<+>a1) (a2:[a3,a4,a5,a6]) = foldl (<+>) (((z<+>a0)<+>a1)<+>a2) (a3:[a4,a5,a6]) = foldl (<+>) ((((z<+>a0)<+>a1)<+>a2)<+>a3) (a4:[a5,a6]) = foldl (<+>) (((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4) (a5:[a6]) = foldl (<+>) ((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5) (a6:[]) = foldl (<+>) (((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) [] = (((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6)
となります。ここまで来ると、あとは一番内側しか簡約できる候補がないので、
result = (((((((z<+>a0)<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) = ((((((b0<+>a1)<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) = (((((b1<+>a2)<+>a3)<+>a4)<+>a5)<+>a6) = ((((b2<+>a3)<+>a4)<+>a5)<+>a6) = (((b3<+>a4)<+>a5)<+>a6) = ((b4<+>a5)<+>a6) = (b5<+>a6) = b6
という風に式が消化されていきます。
せっかく末尾再帰で記述したのに、なんだか内部簡約の時のfoldrと同じような感じになってしまいました。
これは、場合によっては嬉しくないので、Haskellの標準仕様(Haskell2010)には、内部簡約と同じ順序で計算を行う foldl' という関数が用意されています。
Haskellの評価戦略とfoldlはあまり相性がよくない
さて、(今更ですが)なんで私がこんな記事を書き出したのかというと、[twitter:@kazu_yamamoto] さんとの以下のような呟きが発端です。
ここで、[twitter:@kazu_yamamoto]さんが例に出されている
foldl (&&) True [False,(trace "Haha!" True),True,True]
という式を同じように評価してみます。
最外最左簡約ですので、
foldl (&&) True [False,(trace "Haha!" True),True,True] = foldl (&&) True (False:[(trace "Haha!" True),True,True]) = foldl (&&) (True&&False) ((trace "Haha!" True):[True,True]) = foldl (&&) ((True&&False)&&(trace "Haha!" True)) (True:[True]) = foldl (&&) (((True&&False)&&(trace "Haha!" True))&&True) (True:[]) = foldl (&&) ((((True&&False)&&(trace "Haha!" True))&&True)&&True) [] = ((((True&&False)&&(trace "Haha!" True))&&True)&&True) = (((False&&(trace "Haha!" True))&&True)&&True) = {- 注:(trace ...)は評価されない -} ((False&&True)&&True) = (False&&True) = False
という簡約順序になります。論理積の途中にFalseが混じっているので、評価を打ち切ってほしいところですが、
- 最外最左簡約によって畳み込みが全て式に展開されてしまう
- foldl が演算を左結合で繋げるので、演算を途中で打ち切れない
ために、期待に沿わない結果となってしまいました。
ここでfoldrの出番
実は、上の式でfoldlの代わりにfoldrを使うと、あっけなく計算が終わります。
foldr (&&) True [False,(trace "Haha!" True),True,True] = foldr (&&) True (False:[(trace "Haha!" True),True,True]) = False && (foldr (&&) True [(trace "Haha" True),True,True]) = False {- False && _ = False なので！ -}
こちらの方が、元々の期待に沿った動作なのではないでしょうか？
