🚀 go-pugleaf

Mariusz K. Grzeca napisał:
> On Fri, 6 Dec 2002, Tomek Czajka wrote:
> 
>> W jezyku leniwym odpowiednikiem takiego for-a jest fold
> 
> Nie wiem w jakim. W znanych mi nie ma funkcji fold dla list. Są między
> innymi foldl i foldr.

Chyba niepotrzebnie się czepiasz szczegółów.

>> W jezyku funkcyjnym leniwym bedzie to sie odbywalo w pamieci stalej.
> 
> Nie będzie. Prześledź sobie jak wygląda redukcja wyrażenia:
> 
> foldl (+) 0 [a1, a2, a3, a4, a5, ...]
> 
> foldl (+) (0 + a1) [a2, a3, a4, a5, ...]
> foldl (+) (0 + a1 + a2) [a3, a4, a5, ...]
> foldl (+) (0 + a2 + a3 + a4) [a5, ...]
> ...

> Po pierwsze foldl generuje wyrażenie reprezentowane przez łańcuch
> thunków o długości liniowej względem rozmiaru danych wejściowych.

> Po drugie ewaluacja tego wyrażenia wymaga liniowego stosu :)

A to niby dlaczego?

Nie będę powtarzał tego, co już zostało powiedziane:

     * From: Ketil Malde
     * Subject: Re: foldl, tail recursion, and strictness (was: stack
     * overflow)
     * Date: Mon, 26 Feb 2001 06:42:57 -0800

     ---------------------------------------------------------------------------

 "C.Reinke" <C.Reinke@ukc.ac.uk> writes:

 > So foldl is indeed tail recursive, but this doesn't help if its
 > operator isn't strict because the tail recursion only builds up the
 > expression to be evaluated. Making strictness explicit by defining a
 > variant of foldl that evaluates its accumulator at each step helps to
 > solve the problem and documents programmer intentions.

 > This is quite common a trap for Haskellers to fall into

 It makes me wonder if it's common enough that strict foldl should be
 the default?  Are there (many) cases where a partial foldl makes
 sense?

 -kzm

Foldl gorliwy na argumencie akumulatora można zapisać np. tak:

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f acc (x:xs) = (foldl' f $! (f acc x)) xs
foldl' _ acc []     = acc

> Po trzecie foldl i foldr, lub ich odpowiedniki są również w gorliwych
> językach funkcyjnych :)

Tak, ale one są gorliwe aż do przesady, więc trudno mówić, że jest to
odpowiednik pętli for. Pętla for nie musi budować w pamięci całej listy
elementów po których będzie iterować.

pozdrawiam,
tomek

-- 
.signature: Too many levels of symbolic links