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