🚀 go-pugleaf

"Lucifer" <przemek@nospam.pa55.bytom.sdi.tpnet.pl> wrote:

> > Leniwosc polega na tym, ze dana czynnosc jest wykonywana dopiero wtedy,
> > kiedy jej wykonanie jest niezbedne.
>
> Czyli odkladanie zadan jak dlugo to mozliwe?

Tak (koncepcyjnie).

> Czyli leniwe podejscie moze byc co najwyzej tak samo zlozone(powolne) co
>   gorliwe?

Tak.


> Przypuscmy, ze jestem funkcja :) i zalkladam ze jest tak jak piszesz i
> dochodze do wniosku, ze musze zbadac, czy otrzymany argument jest tym co
> chce czy jest thunkiem - wtedy musze go uruchomic.
>
> Ok, co w takim razie znaczy IO w deklaracjach funkcji? Powyzsze jakos
> nie bardzo pasuje do we/wy (co zauwazylem). IO zapobiega leniwosci?

Chyba nie rozumiem. Dla IO wazne sa tylko dwie rzeczy - a) aby wszystkie IO
zostaly wykonane przed zakonczeniem dzialania programu i b) aby byly
wykonane w zadanej kolejnosci.

IO sa zbudowane w ten sposob, ze pod nimi jest ukryty obecny stan. Stan ten
jest przekazywany *sekwnecyjie* wzdluz poszczegolnycha akcji.


> > Leniwe podejscicie umozliwia troche inne spojrzenie na konstrukcje
> > programow. Jest jakgdyby rozciagniecieciem rekurencji na dane inne niz
> > funkcje (1) i uogulnieniem jej przy pracy z funkcjami (2), przez co
> > doskonale wpasowuje sie do wiadomego stylu programowania [zreszta,
> > nie do konca... (3)].
>
> Mozna jakis przyklad?


1.

ones = 1:ones

[
    ones 0 = 1
    ones n = ones (n-1)
]


even = 0:[n+1 | n <- odd]
odd  = 1:[n+1 | n <- tail even]

[
    even 0 = 0
    even n = odd (n-1) + 1

    odd 0 = 1
    odd n = even n + 1
]


fact = 1:[a*n | (a, n) <- zip fact [1..]]

fib = 0:1:[a+b | (a, b) <- zip fib (tail fib)]

[
    w rzeczywistosci konstrukcja przebiega jakgdyby od drugiej strony,
    czyli:

    fact a = local 0  where
      local 0 = 1
      local n | (n == a) = n        -- zakonczenie rekurencji
              | otherwise = n * local (n+1)
]



2.

-- chyba najbardziej znany kombinator :-)
-- znajduje punkt staly funkcji
y f = f (y f)

-- silnia z ukryta rekurencja
fact = y (\f n -> if n == 0 then 1 else n * f (n-1))



Jak to dziala ?

niech r = \f n -> if n == 0 then 1 else n * f (n-1)

i

fixr jest punktem stalym tej funkcji

mamy:

fixr = r fixr

stad:

fixr = \n -> if n == 0 then 1 else n * fixr (n-1)

co oczywiscie jest silnia.


3. Nie zawsze chcemy aby dana struktora byla w ogole tworzona.

Spojrzen na iteracje jest wiele. Rekurencja ogonkowa dla podejscia
funkcyjnego jest mniej wiecej na poziomie `goto' z jezykow imperatywnych.
Oczywiscie chcielibysmy sie poruszac na duzo wyzszym poziomie abstrakcji
takze w obrebie tego paradygmatu.

Najprostszym rozwiazaniem tutaj jest konstrukcja leniwych list (zobacz punkt
1) i odpowiednie ich obrabianie.

Np.:

fFact n = fact !! n

fFib n = fib !! n


lub za pomoca dostarczanych narzedzi (podstawowe to fold i unfold [*]):

fact n = foldl (*) 1 [1..n]

fib n = fst (unfoldInf (0, 1) (\(a, b) -> (b, b+a)) !! n)


W ten sposob mozna zapisywac niemal kazdy iteracyjny algorytm. Problemem w
tym podejsciu jest wlasnie sama leniwosc. Leniwosc wymusza spamietywanie.
Tymczasem my oczekujemy, ze powyzsze funkcje beda wykonywaly sie w O(1) [**]
pamieci i O(n) czasie.

Rozwiazaniem (oczywiscie w Haskell'u nieodpowiednim) moglo by byc stworzenie
struktory, konwertowalnej w razie potrzeby na liste i obliczajacej zawsze od
poczatku wszystkie elementy.


Eh, szkoda, ze w "prawdziwych" jezykach funkcyjnych tak sie nie pisze...


> > Oczywiscie leniwosc ma sens tylko w jezykach czystych.
>
> Tzn? Czym sa czyste jezyki?

Nie umozliwiajace side-effect'ow.


[*]

`unfoldInf' to zwykly unfold bez warunku koncowego:

unfoldInf init f = init:(unfoldInf (f init) f)


[**]

Nie znam na tyle dobrze implementacji Haskell'a, aby powiedziec, czy
powyzsze przyklady wykonaja sie w O(1) pamieci (calkiem mozliwe, ze tak).
Jest to jednak bez znaczenia. W ogolnym przypadku tak nie bedie i na pewno
nie mozna na tym polegac (pozatym jak juz mowilem jest to niezgodne z
leniwoscia i nieintuicyjne).


mp