- 関数型プログラミング言語Haskell Part26
933 ：デフォルトの名無しさん[sage]：2015/01/05(月) 13:38:45.45 ID:rVk7ZNEd - >>929
その方法が一番いい。
1. 素直な方法なので実装しやすくバグが入りにくい。
2. 空リストを考慮しなくてもよく場合分けが必要ない。
3. プログラムソースが見やすく何を求めているのかがよく分かる。
4. 奇数番目だけでなく、x 行おきの場合にも対応でき応用が利く。
|
- 関数型プログラミング言語Haskell Part26
937 ：デフォルトの名無しさん[sage]：2015/01/05(月) 14:25:19.60 ID:rVk7ZNEd - >>934
>>929 の方法でも走査は一度きりなんだが・・・
|
- 関数型プログラミング言語Haskell Part26
943 ：デフォルトの名無しさん[sage]：2015/01/05(月) 16:26:46.03 ID:rVk7ZNEd - >>942
あぁ走査って、リストの要素数 n に対して、
zip の計算量 n、filter の計算量 n とすると、
全体で 2n の計算量になる、と言う意味なのか。
勘違いしてた。
でもそれだと今度は、融合変換しても走査数は変わらないのでは？
融合変換って、中間データ構造（今の問題ならタプル）を消すことでしょ。
|
- 関数型プログラミング言語Haskell Part26
946 ：デフォルトの名無しさん[sage]：2015/01/05(月) 17:43:05.75 ID:rVk7ZNEd - >>944
中間リストって、filter が作る中間リスト？
zip が作る [(String, Int)] に対して「ひとつおきに取り出す処理」は、
あなたの言う走査には含まれない？
融合変換で中間リストが消えて走査数が減ると言うのなら、元々の操作数は、
1. zip が引数のリストを分解する
2. zip がリストを作る
3. filter がリストを分解する
4. filter がリストを作る
の 4 つで、そのうち 2 と 3 が消えて 2つになるのでは？
あるいは、zip は「2つのリスト」に対して処理するから、
元々の走査数は zip 2、filter 1 で計 3 つになるとか？
走査数の意味がイマイチ分からなくなった。
何を以て走査数と言ってる？
|
- 関数型プログラミング言語Haskell Part26
950 ：デフォルトの名無しさん[sage]：2015/01/05(月) 19:20:48.83 ID:rVk7ZNEd - >>947
そもそも遅延評価だから、zip に 1回、filter に 1 回というたどり方はしなくて、
走査の定義をハッキリさせておかないと非常にややこしくなるんだが・・・
リストに対する融合で消えるのはあくまで、
「リストの作成」とその直後の「リストの分解」という一対の処理だけだよ。
zip が行う「タプルを作る処理」や filter が行う「奇数番目かどうか判定する処理」は消えない。
この 2 つの処理が全体で何回行われるかというと、融合されようが、されまいが、
きっちり最初に zip に渡されたリストの要素数分だ。
減りも増えもしない。
（正確には、結果のリストをどう評価するかによるが）
融合によってリストの作成分解処理が一対消えるから、
この処理のことを走査と言うのなら確かに走査数は減ることになる。
タプルの作成や奇数判定も走査の中に含めるのなら、走査数は変わらんよ。
で、俺は走査と言えば、たとえば GCC は C 言語の構文解析を一度スキャン（走査）で行える、
とかいう時のスキャンのイメージがあるから、それなら zip と filter の組み合わせは
リストに対して一度のスキャンで行える、と言ったんだ。
遅延評価だから二度もスキャンする必要はないからね。
|
- 関数型プログラミング言語Haskell Part26
954 ：デフォルトの名無しさん[sage]：2015/01/05(月) 21:34:27.09 ID:rVk7ZNEd - >>952
内容は調べていないから融合できているかは知らんが、
何のために融合しようとしているの？
本末転倒になってはいないか？
適当なテストプログラムを書いてコンパイルし、
RTS オプション の -s を付けて実行して処理時間を測ってみ。
素直に filter と zip を使った方が速いから。
と言っても、かなり大きなリストで試さないと差は見えてこないから、
>>929 の使い方なら実用上どちらを使っても変わらんが。
|
- 関数型プログラミング言語Haskell Part26
955 ：デフォルトの名無しさん[sage]：2015/01/05(月) 21:49:58.07 ID:rVk7ZNEd - >>952
ちなみに、それよりも >>947 の方法の方が速い。
また、ヒープ領域の使用量も速さと同じ結果。
素直に実装した方が少ない使用量で済む。
|
- 推薦図書/必読書のためのスレッド 75 [転載禁止]©2ch.net
250 ：デフォルトの名無しさん[sage]：2015/01/05(月) 23:04:16.08 ID:rVk7ZNEd - >>249
本編6ページまでは Amazon で読めるのに
|