コードサンプルで括弧を使用し、末尾再帰を強調していることは、LispまたはSchemeからHaskellに来ていることを示しています。Schemeのような熱心な言語からHaskellに来る場合は、注意してください。末尾呼び出しは、熱心な言語の場合ほどHaskellのパフォーマンスを予測するものではありません。怠惰のために線形空間で実行される末尾再帰関数と、怠惰のために一定の空間で実行される非末尾再帰関数を持つことができます。（すでに混乱していますか？）
定義の最初の欠陥は、の使用ですlength theList == 0。これにより、リストのスパイン全体の評価が強制され、O（n）時間になります。foldlHaskellのこのナイーブな定義のように、パターンマッチングを使用することをお勧めします。
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
ただし、これはHaskellで悪名高いパフォーマンスを示します。これf z xは、呼び出し元がfoldl結果を要求するまで実際にパーツを計算しないためです。したがって、これfoldlは各リスト要素の未評価のサンクをメモリに蓄積し、末尾再帰であることによるメリットはありません。実際、末尾再帰であるにもかかわらずfoldl、長いリストに対するこのナイーブは、スタックオーバーフローにつながる可能性があります。（Data.Listモジュールにはfoldl'この問題のない機能があります。）
これとは逆に、多くのHaskellの非末尾再帰関数は非常にうまく機能します。たとえばfind、付随する非末尾再帰定義に基づいて、この定義を取りfoldrます。
find :: (a -> Boolean) -> [a] -> Maybe a
find pred xs = foldr find' Nothing xs
where find' elem rest = if pred elem then Just elem else rest
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (subfold xs)
where subfold = foldr f z
これは、怠惰のおかげで、実際には線形時間と一定の空間で実行されます。なんで？
- 述語を満たす要素を見つけたら、の値を計算するためにリストの残りの部分をトラバースする必要はありません
rest。
- 要素を調べて一致しないと判断したら、その要素に関するデータを保持する必要はありません。
私が今教えたい教訓は、熱心な言語からHaskellにパフォーマンスの仮定を持ち込まないことです。あなたはたった2日です。最初に言語の構文とセマンティクスを理解することに集中し、まだ関数の最適化されたバージョンを書くことに自分自身をゆがめないでください。最初はスタイルスタックオーバーフローに見舞われることがありfoldlますが、時間内にマスターします。
編集[2012年9月5日]：find末尾再帰ではないにもかかわらず、レイジーが一定のスペースで実行されるという単純なデモンストレーション。まず、簡略化された定義：
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
find :: (a -> Bool) -> [a] -> Maybe a
find p xs = let step x rest = if p x then Just x else rest
in foldr step Nothing xs
ここで、等号推論（つまり、上記の定義に基づいて、等号を等号に置き換える）を使用し、怠惰な順序で（最も外側から）評価して、次のように計算しましょうfind (==400) [1..]。
find (==400) [1..]
-- Definition of `find`:
=> let step x rest = if x == 400 then Just x else rest
in foldr step Nothing [1..]
-- `[x, y, ...]` is the same as `x:[y, ...]`:
=> let step x rest = if x == 400 then Just x else rest
in foldr step Nothing (1:[2..])
-- Using the second equation in the definition of `foldr`:
=> let step x rest = if x == 400 then Just x else rest
in step 1 (foldr step Nothing [2..])
-- Applying `step`:
=> let step x rest = if x == 400 then Just x else rest
in if 1 == 400 then Just 1 else foldr step Nothing [2..]
-- `1 == 400` is `False`
=> let step x rest = if x == 400 then Just x else rest
in if False then Just 1 else foldr step Nothing [2..]
-- `if False then a else b` is the same as `b`
=> let step x rest = if x == 400 then Just x else rest
in foldr step Nothing [2..]
-- Repeat the same reasoning steps as above
=> let step x rest = if x == 400 then Just x else rest
in foldr step Nothing (2:[3..])
=> let step x rest = if x == 400 then Just x else rest
in step 2 (foldr step Nothing [3..])
=> let step x rest = if x == 400 then Just x else rest
in if 2 == 400 then Just 2 else foldr step Nothing [3..]
=> let step x rest = if x == 400 then Just x else rest
in if False then Just 2 else foldr step Nothing [3..]
=> let step x rest = if x == 400 then Just x else rest
in foldr step Nothing [3..]
.
.
.
=> let step x rest = if x == 400 then Just x else rest
in foldr step Nothing [400..]
=> let step x rest = if x == 400 then Just x else rest
in foldr step Nothing (400:[401..])
=> let step x rest = if x == 400 then Just x else rest
in step 400 (foldr step Nothing [401..])
=> let step x rest = if x == 400 then Just x else rest
in if 400 == 400 then Just 400 else foldr step Nothing [401..]
=> let step x rest = if x == 400 then Just x else rest
in if True then Just 400 else foldr step Nothing [401..]
-- `if True then a else b` is the same as `a`
=> let step x rest = if x == 400 then Just x else rest
in Just 400
-- We can eliminate the `let ... in ...` here:
=> Just 400
後続の評価ステップの式は、リストを進めていくにつれて、次第に複雑になったり長くなったりすることはないことに注意してください。ステップnでの式の長さまたは深さは、nに比例せず、基本的に固定されています。これは実際find (==400) [1..]、一定の空間でどのように怠惰に実行できるかを示しています。