Warto być leniwym

08.12.2009 - Krzysztof Skrzętnicki
TrudnośćTrudnośćTrudność

Ciąg Fibonacciego : podejście pierwsze

Sztandarowym przykładem wykorzystania leniwości jest ciąg liczb Fibonacciego. Jest on zdefiniowany następująco:

Pierwszym wyrazem jest 0. Drugim wyrazem jest 1. Każdy kolejny wyraz stanowi sumę dwóch poprzednich.

Jest wiele sposobów obliczania wyrazów tego ciągu. Najbardziej naiwna implementacja, wynikająca wprost z definicji ciągu, może wyglądać następująco:

1
2
3
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Ma ona zasadniczą wadę: obliczenie n-tego wyrazu ciągu wymaga wykładniczej liczby operacji, z których bardzo wiele wykonywanych jest kilkukrotnie. Przykładowo dla obliczenia fib 5:

1
2
3
4
5
fib 5 = 
fib 4 + fib 3 =
(fib 3 + fib 2) + (fib 3) =
((fib 2 + fib 1) + fib 2) + (fib 2 + fib 1) =
(((fib 1 + fib 0) + fib 1) + (fib 1 + fib 0)) + ((fib 1 + fib 0) + fib 0)

W każdym kolejnym kroku pojawia się coraz więcej zduplikowanych wartości. Spróbujmy więc innego podejścia, które wykorzystywać będzie leniwość Haskella.

Zdefiniowaliśmy już wcześniej nieskończony ciąg liczb naturalnych. Być może uda nam się teraz zdefiniować nieskończony ciąg liczb Fibonacciego?

Pożyczanie z przyszłości

Powiedzieliśmy już sobie, że leniwość pozwala nam definiować wartości, które obliczone będą dopiero wtedy, gdy będą wykorzystane. Można obrócić to stwierdzenie i powiedzieć inną rzecz: możemy definiować nowe wartości przy użyciu takich, których wartości jeszcze nie znamy, pod warunkiem że później będą one znane. Brzmi trochę skomplikowanie? Zobaczmy więc przykład.

Chcemy zdefiniować nieskończony ciąg naprzemiennie występujących elementów [1,2,3]. Oto jak to zrobić w Haskellu:

ciag1 = 1 : 2 : 3 : ciag1

W momencie definiowania listy ciag1 mówimy, że pierwsze trzy elementy to 1, 2 i 3, zaś ogonem całej listy jest ona sama! W ten sposób otrzymujemy nieskończoną listę 1,2,3,1,2,3,1,2,3,1,2,3...

take 20 ciag1
[1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2]


Ćwiczenie (take + ciag1)
Myślenie o rekurencyjnej definicji ciągu ciag1 może przegrzać szare komórki. Aby ułatwić im zadanie spróbuj pobawić się tym ciągiem za pomocą funkcji take. W poniższym polu możesz zdefiniowanych jest kilka ciągów: ciag1, ciag2, ciag3, ciag4. Spróbuj zgadnąć ich definicje.
Przykładowe odpowiedzi:
1
2
3
4
ciag1 = 1 : 2 : 3 : ciag1
ciag2 = zip ciag1 (tail ciag1)
ciag3 = 1 : 2 : [ x*2 | x <- ciag3 ]
ciag4 = [ x^2 | x <- [1..] ]    

Pójdźmy teraz krok dalej. ciag1 zawierał tylko 3 ustalone elementy, zaś ciąg Fibonacciego ma nieskończenie wiele różnych elementów. W poprzednim artykule poznaliśmy operację zipWith. Działa ona prosto: bierze dwa ciągi i każde dwa odpowiadające sobie elementy przekazuje jako argumenty dla pewnej funkcji. W wyniku tworzony jest nowy ciąg wartości. Przykładowo możemy wymnożyć ze sobą elementy ciągów [1,2,3] i [4,5,6]:

1
2
zipWith (*) [1,2,3] [4,5,6]
[4,10,18]

Ponieważ zipWith generuje elementy ciągu w sposób leniwy, możemy go wykorzystać do definiowania nieskończonych list. Możemy więc stworzyć listę kwadratów:

1
2
naturalne = [1..] :: [Integer]
kwadraty = zipWith (*) naturalne naturalne

I taka definicja zadziała, o czym możemy się przekonać:

1
2
take 12 kwadraty 
[1,4,9,16,25,36,49,64,81,100,121,144]

Ciąg Fibonacciego : tym razem szybciej

Możemy już wrócić do ciągu Fibonacciego. Potrafimy już definiować ciągi przy użyciu zipWith. Wiem już także, że możemy używać wartości ciągu podczas tworzenia samej jego definicji. To wszystko pozwala nam napisać definicję tego ciągu w jednej linijce!

1
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Zastanówmy się jak to działa. Pierwsze dwa elementy to 0 i 1 - o tym mówimy wprost. Następne elementy tworzone są jako suma sąsiednich elementów dwóch ciągów: fibs czyli oryginalnego ciągu i tail fibs czyli ciągu fibs z pominięciem pierwszego elementu. Aby otrzymać kolejny element sumujemy więc ze sobą dwa sąsiednie elementy. Wygląda to następująco:


Ćwiczenie (fibs)
Używając funkcji take i zip wypisz pierwszych 20 liczb Fibonacciego wraz z ich numerami ((1,0),(2,1),(3,1),(4,2),(5,3) itd.). Lista fibs jest już zdefiniowana.
Przykładowa odpowiedź:
1
2
        take 20 (zip [1..] fibs)
    

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com