計算作業（xは、x）は

Question

だが、私はこの機能を持っているとしましょうか？

最初は明らかに一定だと思っていましたが、xのタイプが有限でない場合、xは任意の量のメモリを取ることができますか？ 1つは、xもコピーすることによって行われた作業を考慮する必要がありますか？

これは、関数によって行われた作業が入力のサイズにおいて実際は線形であると私に信じさせました。

これは、自分自身のための宿題ではありませんが、私は関数によって行われた作業を定義しなければならなかったときに思いついた：

f x = [x] 

同様の問題を持って、私は信じています。

Answer 1

非常に非公式に、実行される作業は、言語の操作上のセマンティクスによって異なります。 Haskellは、まあ、それは怠け者だ、あなたはにのみ一定の要因を支払う：その引数

リターンaに(,)を適用(,)

のヒープ・セルを割り当てるスタック

にxに

• プッシュポインタヒープセルへのポインタ

完了。 O（1）作業者は、発信者がfの結果を確認したときに実行されます。

(,) - の内部を調べると、評価が行われ、その作業はxの評価作業に依存します。 Haskellではxへの参照が共有されているため、一度だけ評価します。

したがって、結果を完全に評価した場合、ハスケルの仕事はO（仕事のx）です。あなたの関数fは、定数を加えるだけです。

Answer 2

Chris Okasakiは、いくつかの（または全体的な）怠惰が導入されたときに、関数呼び出しに費やされる仕事を決定する素晴らしい方法を持っています。純粋に機能的なデータ構造に関する彼の論文にあると思います。私はそれが本の版にあることを知っています - 私は先月のその部分を読んだ。基本的には、作成された約束/サンクの一定の要素を請求し、約束/サンクスを評価するために何も請求しません（彼らは既に強制されていると仮定します[通常の形式[WHNFだけではありません]）。それは過小評価です。あなたが過大な課金をしたい場合は、通常の形式に強制する/変換するコスト。関数によって作成された約束/サンク。少なくとも、それは私が非常に疲れた状態でそれを覚えている方法です。

岡崎で調べてみましょう：http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis - 私はダウンロードして使用される論文を誓います。