18 września 2009

Pułapka

Pisałem ostatnio program wykonujący dość długo skomplikowane obliczenia. Przy pewnych danych wejściowych program przepełniał stos i się wysypywał. Po kilku godzinach frustracji postanowiłem przepisać każdą funkcję na wersję ogonową.
W trakcie tego jak to robiłem zacząłem się zastanawiać nad programowaniem funkcyjnym. Generalnie to jego główną ideą jest to, że piszemy w nim nie jak coś policzyć (tak jak to jest w programowaniu imperatywnym) tylko czym wynik danej funkcji ma być. I to jest bardzo przyjemne i bardzo fajnie się tak pisze - wszystkie funkcje wklepuje się niemal intuicyjnie. Problem jest jak dojdzie do funkcji ogonowych. Funkcje ogonowe (zwłaszcza nieco bardziej skomplikowanych obliczeń) są w ogóle nie intuicyjne. Trzeba zacząć się zastanawiać co ma być akumulatorem (może trzeba dać dwa akumulatory?) jakie dodatkowe informacje należy przekazać itp. itd.
Na szczęście udało mi się wszystkie funkcje przepisać na wersje ogonowe (Teraz jak ktoś spojrzy na kod to już się nie dowie co to a to robi :) ). Nie udało się przepisać tylko jednej. Może ktoś z was będzie miał pomysł. Funkcja dostaje długość listy l oraz sumę s i generuje wszystkie listy o długości l zawierające liczby dodatnie sumujące się co najwyżej do s. Na przykład: funkcja 3 5 = [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,3,1][2,1,1],[2,1,2],[2,2,1],[3,1,1]]. Kolejność list nie jest ważna.
Gdy już miałem prawie wszystkie funkcje ogonowe i sprawdziłem ręcznie, że program nie wywiesza się na tej funkcji nie ogonowej... program dalej się wywieszał :-) Zasięgnąłem zatem opinii dokumentacji i okazało się... że standardowa funkcja map nie jest ogonowa... Troszeczkę się zdenerwowałem. Gdzie kolejność elementów nie była dla mnie ważna użyłem funkcji rev_map. W innych sytuacjach napisałem własną funkcję map:

let mymap l p = rev (map l p);;
Program wciąż nie działa - typ razem już na mojej funkcji (opisanej wyżej). Przepisałem program do C++ działa i to sto razy szybciej ;)

1 komentarz:

stdin pisze...

A w takim leniwym Haskellu tkwią jeszcze inne nieprzyjemne zasadzki