匿名質問者
匿名質問者匿名質問者とは「匿名質問」を利用して質問した質問者。
「匿名質問」では、ユーザー名を公開せずに匿名の質問ができます。
詳しくはこちら

プログラミング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]

を使っています。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2016/07/31 21:12:17
  • 終了:2016/08/07 21:15:03

回答(0件)

回答はまだありません

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません