Here are the implementations of
foldl
and foldr
in Haskell ..foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
foldl
is tail recursive, while foldr
is not. But throw in Haskell's non strict evaluation strategy in the mix and we find some non-obvious consequences in using the supposedly optimized foldl
against foldr
.In case of
foldl
, Haskell will defer the evaluation of the entire result till the end of the list is reached. And this can lead to a stack overflow if the final expression is big enough. Hence foldr
, despite not being tail recursive is a better option in many cases. And Haskell also offers a strict version of foldl
(fold'
) that forces the evaluation of the initial parameter before making the recursive call.Here is an example of summing over a list, that uses accumulator based summing and tail recursion ..
sumList acc [] = acc
sumList acc (x:xs) = sumList (acc+x) xs
When I try ..
Main> print . sumList 0 . take 1000000 $ [1..]
*** Exception: stack overflow
It's tail recursive, but lazy evaluation keeps accumulating the result till the end of the list is reached, and ultimately results in a stack overflow.
Instead try the
foldl'
combinator ..sumList’ xs = foldl’ (+) 0 xs
and you will be happy !!
Let us take a look at how exactly Haskell evaluates an expression lazily. Instead of evaluating a value directly, Haskell uses a machinery called *thunk* to abstract the computation of the expression. Thunks contain instructions to compute the value, which will be activated when the evaluation is forced. Let us consider the following snippet, which takes out every third element from the input list ..
thirds [] = []
thirds [x] = []
thirds (_:_:x:xs) = x : thirds xs
Consider the interesting recursive case above. Haskell produces a thunk that contains a list cons cell. The cons cell contains the element value (x) and another yet unevaluated thunk for the rest of the list. The function
thirds
is lazy and will consume only that part of the input which is required to produce the result. Hence if we request for the first element of the result list, it gets back instantly without evaluating the rest of the list. Hence if we compute head $ thirds [1..10000000]
we get the first element 3 in constant time. Another important advantage of lazy evaluation is that Haskell can handle infinite data structures seamlessly. In the above example, we can change the invocation to
head $ thirds [1..]
and will get back 3 instantly and in constant time.
Now consider what happens if we implement the same function using tail recursion .
thirds_tc :: [Int] -> [Int] -> [Int]
thirds_tc acc [] = reverse acc
thirds_tc acc [x] = reverse acc
thirds_tc acc (_:_:x:xs) = thirds_tc (x:acc) xs
Nice and tail recursive .. but to get the first element the function takes O(n) time. Try .
head $ thirds_tc [] [1..10000000]
and compare the difference in time with the earlier implementation.
So, as we find, tail recursion is not a be-all and end-all with respect to optimization even in case of non strict languages like Haskell. And use combinators like
foldl'
or foldr
depending on your application requirements. Combinators abstract away many of the language semantics and can make lots of high level optimizations that may not be obvious while programming with bare recursion.
3 comments:
Try this:
sumList acc [] = acc
sumList acc (x:xs) = (sumList $! acc+x) xs
Thank you. Nice observation, I'll actually strengthen your conclusion to say that the notion of proper tail recursion is completely irrelevant to haskell, here:
http://muaddibspace.blogspot.com/2008/08/tail-call-optimization-doesnt-exist-in.html
キャッシング
大阪 賃貸
中古車 販売
ルームウェア
大阪 マンション
賃貸マンション 神戸
中古 ゴルフクラブ
クールビズ
フィットネスクラブ
大阪府 司法書士
クレジット 申し込み
ベビードール
矯正歯科 東京
ホワイトニング 東京
大阪 ラブホテル
リサイクルショップ
不動産
カードローン
投資 信託
下着
即日 キャッシング
三井住友銀行
神戸市 中央区 税理士
FX
消費者金融
ローン
引越し
生命保険
ジェルネイル
人材派遣
ネット証券
アフィリエイト
格安航空券
ウィークリーマンション
レンタカー
SEO
オフィス家具
合宿免許
ペット用品
高速バス
デリヘル
キャバクラ
派遣
コラーゲン
化粧品
インテリア
ウェディング
結婚相談
投資物件
留学
貸事務所 大阪
経営コンサルティング
工芸品
高級品
自動車保険
ホテヘル
レストランウェディング
バイク買取
運転免許
ベビーカー
外反母趾
圧力鍋
腕時計
フェラガモ
デリヘル
キャバクラ
セレブ
プラセンタ
カルシウム
青汁
ブルーベリー
家具
脱毛クリーム
除毛クリーム
コスト削減 大阪
弁護士 大阪
車買取 大阪
バイク買取 大阪
エステ 大阪
リフォーム 大阪
大阪 歯科
派遣 大阪
アルバイト 大阪
転職 大阪
大阪 住宅
大阪 専門学校
グルメ 大阪
ホテル 大阪
一戸建て 大阪
大阪 宿泊
大阪 マンション
デリヘル 大阪
印刷 大阪
不動産 大阪
賃貸 大阪
ブライダル 大阪
リサイクル
アダルト SEO
賃貸
SEO 大阪
イベント コンパニオン 大阪
転職 大阪
大阪 ラブホ
ペット ショップ 大阪
豆腐
京都 不動産
運転免許 合宿
ヘアアイロン
ダイエット
ダイエット
デリヘル
キャバクラ
Post a Comment