人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

プログラミングHaskell(Graham Hutton 著、山本和彦 訳) P.174 「13.6 連結を除去する」に書かれている

「式 xs ++ ys を評価するための簡約の回数が、リスト xs と ys が完全に評価されていると仮定できるなら、xs の長さよりも一つ大きい数であることを示すことは簡単である。そのため、演算子 ++ の効率は、一番目の引数の長さに比例する。このため、長さが n のリスト xs に対し、式 reverse xs にかかる簡約の回数は、1 から n + 1 までの整数の和、すなわち (n + 1)(n + 2) / 2 である」

という説明がよく理解できません。なぜ reverse xs の簡約の回数が 1 から n + 1 までの整数の和になるのでしょうか?

ちなみに reverse の定義は

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

を使っています。


●質問者: 匿名質問者
●カテゴリ:学習・教育
○ 状態 :キャンセル
└ 回答数 : 0/0件

回答がありません
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ