#すごい。やればできるじゃないですか！ > chop
#チュートリアルに採用させて頂きます。
#tailDropWhile という高階関数にすると双対っぽくていいのかも。
#コンビネータの例として名前を挙げたいものを募集します。
#今のところ、パーサー、XML、SQ,
#SQL、商取引、ハードウェア設計
#が挙っています。
#あと一つぐらい欲しいです。
#(上の SQ, は誤植です。)
#図形言語？
#プリティプリンタ
#図形言語って、SICP のやつですか？
#プリティプリンタはよさそうですね。
##一応、チュートリアルの資料ができました。
##意見を言って頂けると嬉しいです。
#tailDropWhile だと reverse . dropWhile isSpace . reverse より効率が悪るそう。
#えーと、maoe さんの実装自体が効率が悪いという意味ですか？ それとも、nobsun の chop とかは効率はいいが、tailDropWhile だけが効率が悪いという意味ですか？
#原因をうまく説明できないので曖昧ないいかだになりましたが、少くとも chop :: String -> String に関してはmaoeさんの実装も、私の実装も reverse .dropWhile isSpace . reverse よりも効率が悪いように思います。chopの実装にtailDropWhileを使うのはうまくないということです。
#末尾空白が短く、全体が長い文字列で実験すると顕著にちがうように見えます。
#goの適用がリストのすべての要素上で評価されます。つまり go でのパターンマッチによる検査が毎回怒ることになりそれがネックになるのではないかと思います。
#[] の部分を、ガードの null に変えてもダメでしょうか？
#もっと遅くなります。
#どうやって計測してますか？
#ああ、分かった。このコードは遅延評価と相性が悪い。
#ものすごくアバウト。ghci> :set +s
#右側を計算し終わらないと、c : できないですね。
#そうです。
#右側の計算結果が [] だったら、c : してはいけないから。
#単純に x : f x とかだと、x : を忘れて f x を後で計算できます。
#でも、このコードではダメですね。
#です。
#では、reverse を使った tailDropWhile も示して、foldr バージョンは遅いとコメントに書くことにします。
#書き換えておき直しました。> PDF
#import List; import Maybe; import Char
chop xs = catMaybes $ snd $ mapAccumR f True xs where
f endp x | isSpace x && endp = (True, Nothing)
| otherwise = (False, Just x)#本質的に maoeさんのと同じか。
#ただ isSpace を先にチェックした方がいいですよね。
#末尾空白が短く全体が長い文字列でも大丈夫じゃないかな。
#↑遅くないですか。sample = replicate (10^6) 'a' と定義しておいて length $ chop sample の計算時間を比べてみると遅さが判ります。
#うーーん、長い文字列の先頭数文字取るだけだったら速いかなと思ったんだけど。
#あ、コンシューマーがいたら速いかなという意味でした。
#全文字処理したらアドバンテージないですが。
#ああそうですねぇ。でも、tailDropWhile をわざわざやるということは、後ろがオチていることを見ることが大事になるわけだろうから。先頭数文字だけ使いたいという場合の方が少ないとおもうなぁ。
#全文字処理なら
#take (fst . foldl' f (0,0) xs) xs
#f (b,n) c | isSpace c = (b,n+1)
#| otherwise = (n, n+1)
#というのも考えたけどスピードどうだろう。
#fst $
#使い方によって変わる性能差をきちんとみたいなら、progression を使いましょう。 http://t.co/taQX9ge #mapAccumR版は無限文字列にも対応してるぞ、ドヤッ。ということで。
#しょせんぼくはトイプロブレムしかやりませんよ。いじいじ。
#勘違いしてました。その方が早いです。kazuさん：[] の部分を、ガードの null に変えてもダメでしょうか？
#[1..100]>>=penさんの指摘どおり
#tailDropWhile :: (a -> Bool) -> [a] -> [a]
tailDropWhile p = foldr go []
where
go c cs | p c && null cs = []
| otherwise = c:cs#あ、mapAccumR 使わなくよかったのか。
#ただ、これでも reverse . dropWhile isSpace . reverse のほうが性能はいいようですねぇ。
#reverse の性能がいいんでしょうね。
#そうおもって、reverseとdropWhileを手で素朴に定義しなおしてます。
#mapAccumR 版は foldr 版と違って、fold/build で融合変換できないので、与えるデータと最適化の有無で両者の性能は変わってきそうです。 http://j.mp/qWgQx1 http://j.mp/qzFBkW #みんな探求精神旺盛でえらいなあ。
#.｡oO(まあ、最適化オプションを使わないのが前提なら、どうでも良い話ですが。)
#chop単独では融合変換とかは関係なさそうに思えるのですがそうではないのですか？
#hkothaさん（だっけ？）召喚せねば。
#chop に与える String、chop が返す String が中間データ構造なので、これを排除するような融合変換が考えられますよね。
#foldr や foldr を使って定義した関数を chop の定義に使えば、前者の chop に与える String を排除するような融合変換ができます。
#で、確かに chop 単体では関係ないですけれど、実際に利用する場面を考えたら融合変換は重要だということです。
#はい。たとえば length $ chop s が最終目標ならそういうことなんですが。chop単独の性能についてはというつもりだったんです。
#やはり GHC とライブラリを読まんといかんな。
#でもって、tailDropWhileの意図は後ろを落としたリストを得ることなので、tailDropWhileをつかっておきながらdeforestationしたいという場面を想定するのが私には難しいです。
#私は、chop の性能を言う場合に chop 単体の性能を言って意味があるのか、実際に利用されるケースについて考えないといけないのではないか、というところに引っかかりを覚えました。
#そんなことはないか。deforestationしたことはいくらでもあるな。
#した→したい
#まあ、人間普段の活動で１００ｍだけ走ることはないけどオリンピックの１００ｍ競争はそれはそれで意味あるからなあ。両ケースでの効率わかるといいですね。
#遅延評価で呼ばれる度にリストの次の要素を作成する関数と、tailDropWhile、この二つの間に発生するリストを排除したくなっても良いですよね？
#一番簡単なれいはまさに length $ chop s ですよね。
#reverseとdropWhile手作りバージョン楽しみです。
#え？何を期待してます？↑
#スピードがどうなるか。もう結果でました？手作り版でも reverse版の方が速いということですか？
#そうだとしたら関数コールのスタック使うのが遅い原因かもということか。
#いやそもそもghciでのいい加減な比較だから :p
#当然コンパイル済みのコードかそうでないかの性能差がでる。
#な、な、なんだってー！ ghci！
#だから手作りしたんだってば。
#reverse版が速いのは分岐判断の数が少ないからだとおもう。つまり分岐判断処理が重いってこと
#でも分岐は dropWhile で同じことしてるでしょ。
#あ、違うか。
#理解しますた。
#深いなあ。
#じゃあ、foldr（foldlじゃなくて） で長さだけ先に計算させて take するのはどうでしょう。
#やってみそらしど。reverse版と
#おなじ構造になるから。
#逆文字列つくらない分軽そうな気がするんだけど。
#やってみそらしど。
#やらないね（他人（ひと）まかせ）
#どちらも関数コールがスタックにたまってるから同じなのかな。
#かずかぞえるのにけっきょくさいごまでリストたどるでしょ？
#全部なめるのはしょうがないのはOK。
#ああさっきのコードですか？
#長さだけ計算すると途中に作る構造が少なくてすむかなあああと。
#foldr版の話。
#メモリはせつやくできるけど、述語適用がやっぱり要素分だけひつようになるんじゃない？
#一回の適用が軽くならないかなあああという願望。
#なんないと思うなぁ。
#そうかい、そうかい。明日自分でやってみるよ。プンプン。
#まぁちょいまちねぇ。
#なにか面白いネタが残ってますか。
#竹のこーどかいてみるから。
#wktk
#竹とｄろｐ。
#あかん。おそすぎ
#orz
#寝ます。
#replicate (10^7) 'a' くわせたら帰ってこん。
#とても勉強になりました。
#みんなありがとう。月が綺麗ですね。
#ありや、おぬしのコードまちごうとるぞ
#おぬしって誰。
#そこのおぬじゃ。
#あれ。
#わしか？
#foldどっち版？
#chop' s = take (fst $ foldl' f (0,0) s) s
where f (b,n) c | isSpace c = (b,n+1)
| otherwise = (n,n+1)#であってる？
#foldlじゃない方で、って書いたでしょう。
#コードかいて？
#foldr で末尾から計算した版をつくって欲しい。
#今日は私はもう書かない。
#ちょいまて。
#待ちましょう。
#zip [1..
#zip [1..] したのと直接カウントアップするのではどちらが速いかな。
#chop' s = take len s
where
len = foldr f 0 s
f c n | isSpace c && n==0 = 0
| otherwise = n+1#でいいかい？
#ゆっくり確認しますのでそれで試してみてください。
#これスタックふくれまくりだとおもうけど。。。
#どっかで seq でいないかな。
#そらむり。foldl'じゃないと
#あ、関数コールスタックはしょうがないか。
#まつびさいきでないとだめでしょ。
#ともかくやってみてください。すでにテスト中かな。
#かえってこないので、データちいさくするね。
#*Main> length $ chop sample
1000000
(0.11 secs, 54012312 bytes)
*Main> length $ chop' sample
1000000
(4.46 secs, 261028772 bytes)
#| isSpace c = n
#みたくしたいな。
#n を１ずらしたらできないかな。
#って、そんな小細工したくらいじゃ追いつかない差？
#そう。
#foldl' 版の方がましじゃない？
#orz。
#この版は一往復半するからなあ。
#だって、どうせ長さかぞえるなら、foldl' じゃない？
#でもコードがびみょうにちがうんだな。
#だって条件分岐が効くからって言うからー
#。
#1ずれてる > foldl'
#だからfoldr版条件分岐へってないじゃん。
#興味が出てきたので明日考え直してみます。
#いや、長さの計算のときに減ってるはず。
#なんで？
#| otherwise = n+1
#で c を使ってない。
#え、勘違いしてる？
#してるような気がしてきた。
#さっきの
#tailDropWhile :: (a -> Bool) -> [a] -> [a]
tailDropWhile p = foldr go []
where
go c cs | p c && null cs = []
| otherwise = c:cs#だって使ってなくね。
#isSpace でスペースでなければ直帰するつもりでいたけど
#してないようなきがしてきた。
#and/or が途中で直帰できるのはなんでだっけ。
#してまへんがな。第二引数について正格だから直帰できない。
#あ、そうだ。
#第二引数について正格でなくてもよいことがあるから。
#zip [1..] 版ならどうだ！
#おんなじじゃね。
#今度は直帰できるでしょうがー！
#どうやって？
#あれ、どうだっけ。
#うしろまでみなくちゃいけないことにはかわりないでしょうが。
#だからちょっきできない。
#foldr なんかやめて再起にしろー！
#おんなじじゃっちゅうとろうが。
#再帰だった。orz
#いや、再帰なら直帰できる。
#できまへんて
#いや、できるね。（根拠なし）
#さいごまでみなきゃいけないのはchopの本質!!!
#foldr の帰りの途中で直帰できるのでは。
#あっ。
#foldr は順番いかえっていくのですね。orz
#callCC の出番か。
#もやは敗北状態。
#ちょっきできるようにするためにはまえからたどったときにそれをちくせきしておく必要がある。でも蓄積は逆順になるから、reverseが必要になる
#継続的なことすればなんかできような気がしてきた。（根拠なし）
#けっきょく最低1往復必要
#明日で勘弁してください。
#ならん!
#１往復が必要なのはOK.
#あ、そう言ってないか。
#直帰できるって言ったな。
#ちょっきできるけど、先につんだものをreverseするから、1往復と同じ
#コンパイルエラー全部記録しますから今日は勘弁してください。
#きょうのところは勘弁してやろう :p これきりだぞ :)
#ありがとうごぜーます。
#うむ。おやすみ。
#：)
#「コンパイルエラーの年貢は全部納めますから」と書くべきだった。
#寝る前にメモ。
#・reverseには不利であろうすべて空白文字列での比較。
#・本当に直帰する catch try を使ったら。
#寝る。
#すべてくうはくはreverse版に不利にはならない
#ちょっきするときに持って帰るものをどうやってつくるのかが問題
#融合変換の可能性があるというが本当か？それが欲しい具体的例題はなにか？foldr版tailDropWhileの使い道は本当にあるのか？
#あたりが課題だろうけど、感覚的にはNOだとおもうなぁ。
#とおもったけど。こんな例題ならどうだろう
#テキストデータの80桁を超える部分を切り捨て、末尾の空白も切り捨てたい
#末尾→行末
#ああこの例題よくないなぁ
haskell-ja > Archives > 2011/09/13