Początki w programowaniu funkcyjnym

Hi, od kilku dni myślę nad programowaniem funkcyjnym.
Dużo na ten temat czytałem i jako środowisko waham się między OCamlem a Haskellem. Nie jestem programistycznym geniuszem, znam podstawy C++, Javy i Pythona, trochę algorytmów. Chciałbym jednak spojrzeć na programowanie z innej strony.

Pytanie jest następujące - które ze środowisk (OCaml, Haskell) uważacie za korzystniejsze z punktu widzenia laika w dziedzinie programowania funkcyjnego. Nie pytam co będzie dla mnie lepsze, proszę tylko o Wasze opinie razem z krótkim uzasadnieniem.

Pozdrawiam i dziękuję za poświęcony czas.

Wybierz to które ze składnią Ci bardziej odpowiada by nauczyć się myśleć, potem naucz się drugiego i będziesz miał porównanie.

(Znaczniki dla odstraszenia upierdliwców)

Nie jestem ekspertem, ale trochę pisałem funkcyjnie w celach "rozwojowych". OCaml to strata czasu, jest niewiele bardziej funkcyjny niż Common Lisp, język nafaszerowany jest elementami imperatywnymi i obiektowością (która jest zaprzeczeniem prawdziwej funkcyjności). Haskell ma znacznie czytelniejszą składnię, nieporównywalnie potężniejszy system typów (kompletny w sensie Turinga, przynajmniej z 'rozszerzeniami' GHC, który jest de facto standardem), leniwą ewaluację (którą w OCamlu trzeba wymuszać). Monady pozwalają spojrzeć na działanie programu z nieco innej strony, technicznie to "kontynuacje wokół danych", ale typem danych może być równie dobrze może być abstrakcyjny typ danych co typ funkcji. Oczywiście nie są one "jedynym słusznym rozwiązaniem", ale to pewien sposób tworzenia abstrakcji, który z powodzeniem można zastosować do rozwiązywania niektórych problemów w niemal dowolnym języku. Co do popularności - obecnie na stackoverflow są 584 otagowane jako OCaml, 3,736 jako Haskell. Poza tym do Haskella jest znacznie więcej literatury, tak tej przystępnej dla początkujących, jak i "poważnej", np. Pearls Of Functional Algorithm Design, książka warta poznania niezależnie od zawodowo stosowanego języka.

Jeżeli masz się w to zagłębiać to poznaj prawdziwy czysto funkcyjny język programowania, jak najpoteżniejszy i najpopularniejszy. Przy takich kryteriach wybór jest tylko jeden.

Zajmując się AI spłodziłem kiedyś bodajże taką funkcję pomocniczą (nazwa by wszystko zepsuła):

wtf = any . flip all

Ktoś podejmie się krótszego rozwiązania w innym języku? :]
Druga wersja, w pewnych przypadkach efektywniejsza, z odwróconymi argumentami (wymaga Control.Monad.Instances):

wtf ps xs = foldl (filterM ($)) ps xs /= []

Formalnie zamiast ($) można zastosować id, ale wtedy kod straci na oczywistości, w końcu (->) a też jest monadą, to nie tylko "strzałeczka" w "prototypach" jak myślą niektórzy początkujący.

To jak, ktoś podejmie się wyjaśnienia kodu i zaproponowania krótszej wersji? :]

@Wibowit, Scala to język hybrydowy, średnio się nadaje do nauki prawdziwego, ale do tworzenia realnego oprogramowania jak najbardziej. Haskell nie jest obiektowy i chwała mu za to, FP i OOP to wzajemne przeciwieństwo - jedno jest zorientowane na przepływ danych, drugie na ich reprezentację. Jedno opiera się na cechach typu, drugie na cechach obiektu. W OOP (miejscami) funkcje zastępuje się strukturą typów, w FP odwrotnie. Scala to dobry język, ale programowanie w nim to kompromis pomiędzy OOP a funkcyjnością. Do nauki FP jako abstrakcji, nie "fajnego zamiennika pętli", mają sens jedynie języki czysto funkcyjne. Bez OOP można żyć i nikt za nim nie płacze, to nie jest jakiś Święty Graal programowania tylko jedna z wielu pomocnych technik, które mają swoje zastosowania i ograniczenia.

Jeżeli masz się w to zagłębiać to poznaj prawdziwy czysto funkcyjny język programowania, jak najpoteżniejszy i najpopularniejszy. Przy takich kryteriach wybór jest tylko jeden.

Widzę że fanatyk przez Ciebie przemawia :P

Zależy czy chcesz pisać czysto funkcyjnie czy przestawiać się na pisanie czysto funkcyjne. Z ciekawszych:
OCamla nie znam, polecałbym raczej F# (funkcyjny, pozwalający jednak jeśli ktoś jest uparty na pisanie imperatywne). Ma wszystko to co OCaml + jeszcze trochę.
Clojure - ciekawy język, funkcyjna wersja Lispa.
Haskell - powyżej ofidyfil się nad nim rozpisał.
Scala - zapytaj Wibowita, on znajdzie milion powodów żeby w tym pisać.
Unlambda ;).

Z powyższych nie pozwala na żadne efekty uboczne tylko Haskell - dobre jeśli chodzi o zastosowania akademickie, ale programy się pisze trudniej. Owszem, Haskell to piękny język ale może Ci być trudno na początku coś napisać.

To co powinieneś teraz wybrać zależy w dużej mierze od tego wczym wcześniej pisałeś.

MSM napisał(a)

Jeżeli masz się w to zagłębiać to poznaj prawdziwy czysto funkcyjny język programowania, jak najpoteżniejszy i najpopularniejszy. Przy takich kryteriach wybór jest tylko jeden.

Widzę że fanatyk przez Ciebie przemawia :P

Gdzie tam fanatyk, ja pythonistą jestem :P. Jeśli język ma posłużyć do rozwoju osobistego to alternatywy nie ma, może Curry albo Clean ewentualnie, po prostu jeżeli opanowywać prawdziwe, bliskie matematyki, FP to w języku, który jest temu naprawdę bliski. Nie ma innego popularnego języka, w którym bardziej wyrafinowane FP byłoby jednocześnie możliwe i pozbawione imperatywnych alternatyw, skoro nie ma alternatyw to nie ma ucieczki od zrozumienia pewnych mechanizmów. Po prostu o naukę chodzi, w przeciwieństwie do Scali czy F# w Haskellu nie da się myśleć imperatywnie (nawet korzystając z monad), przestawisz się albo zginiesz. Owszem, to może zaboleć, jednocześnie nauczy znacznie więcej niż języki "brudno funkcyjne".

Polecam Haskella ze względu na jego walory edukacyjne, w końcu nie wszystko robimy bezpośrednio dla pieniędzy, prawda? Niee? To won, wypełniać zalecenia Wibowita :]

Dziękuję za ciekawe wypowiedz.
@up - jest jakieś IDE do haskella?

OCaml nie jest taki zły, jednak Haskell ma bardziej rozbudowaną bibliotekę standardową. Tu masz moje kody http://4programmers.net/Forum/Off-Topic/172532-matura_z_informatyki?p=747125#id747125 w śród nich jest jeden w OCamlu i jeden w Haskellu. Oprócz OCamla masz jeszcze ML.

@up - jest jakieś IDE do haskella?

Czuję się obrażony że pytanie było skierowane tylko do @up

Istnieje Leksah, które jest o tyle ciekawe że zostało napisane w Haskellu (sam ten fakt powoduje mój podziw że z taką dużą aplikacją sobie poradzili bez efektów ubocznych, no ale widać to sprytni ludzie pisali) - http://leksah.org
Słyszałem o Visual Haskell ale coś cicho o nim czyli prawdopodobnie niewarty polecenia. (edit - poszukałem o nim, ale coś mało popularny, wygląda na nierozwijany i chyba nie działa dla VS innego niż 2005... Tym niemniej - http://research.microsoft.com/apps/pubs/default.aspx?id=67496)
Dalej klasycznie, jak dla każdego języka:
Vim + haskell
Emacs + haskell
Eclipse + haskell

MSM napisał(a)

sam ten fakt powoduje mój podziw że z taką dużą aplikacją sobie poradzili bez efektów ubocznych, no ale widać to sprytni ludzie pisali

Ależ efekty uboczne są, zostały tylko ujęte w monady. Praktycznie dowolny stan da się wyrazić w formie czysto funkcyjnej, kolejne operacje w monadzie tworzą kolejne stany.

winerfresh napisał(a)

Oprócz OCamla masz jeszcze ML

OCaml to jest właśnie ML, jeden z jego dialektów.

winerfresh napisał(a)

Gedit + haskell

Gedit? Niee no, bez przesady, przecież to zwykły notatnik, nie oferuje nawet integracji z GHCi. Poza tym nie "+ haskell" tylko "+ GHC", jest kilka środowisk tego języka, tylko jedno naprawdę warte uwagi. Z edytorów najpopularniejszy jest Emacs, http://www.haskell.org/haskellwiki/Haskell_mode_for_Emacs - opisane co i jak.

Co do Twojego kodu w Haskellu to można mieć pewne zastrzeżenia - nie stosujesz pattern matchingu, nadużywasz pattern guards, efekty uboczne (i to w IO) stosujesz jakby to był jakiś język imperatywny, kod przechodzi dzięki uprzejmości GHC bo main ma niewłaściwy typ.

winerfresh napisał(a)

sklej n | n == 1 = 1
        | n `mod` 2 == 0 = n - 1 + 2 * sklej (n `div` 2)
        | n `mod` 2 /= 0 = n - 1 + sklej ((n-1) `div` 2) + sklej((n+1) `div` 2)

Pattern guard nie stosuje się tam, gdzie sam pattern matching wystarcza, przypadek bazowy:

sklej' 1 = 1

Nie tworzy się przeciwnego guarda, tak jak dla if używa się else, tak tutaj ostatnia klauzula to zwyczajowo otherwise (co jest definiowane po prostu jako otherwise = True). Od czegoś są też wbudowane predykaty. Przypadek ogólny:

sklej' n | even n    = n - 1 + 2 * sklej' (n `div` 2)
         | otherwise = n - 1 + sklej' ((n-1) `div` 2) + sklej' ((n+1) `div` 2)

Dalej można np. wyodrębnić operację sklej $ div (f n) 2 ale to już raczej zwykła zabawa.

winerfresh napisał(a)

main = mapM (print . sklej) [1..10000]

Funkcja main powinna mieć typ IO (), u Ciebie ma IO [()], zastosowałeś niewłaściwą funkcję mapującą, monadyczny map wołany wyłącznie dla efektów ubocznych to mapM_, nie mapM. Dla GHC nie ma to wielkiego znaczenia, wynik main jest nieużywany. Po każdej operacji wywołujesz efekty uboczne dla "świata", operacje "czyste" powinno się od nich oddzielać, jak największa część programu powinna być niezależna. W tym wypadku można efektywnie posłużyć się pojedynczą operacją IO, pojedynczym putStrLn (print = putStrLn . show), dzięki leniwej ewaluacji i buforowaniu możliwe jest zbudowanie całego wyjścia w miarę potrzeb, "czysto":

main0 = putStrLn $ unlines $ map (show . sklej') [0..10000]

Dzięki temu, że pojedyncza operacja IO konsumuje wyjście wedle potrzeb mamy zauważalny przyrost wydajności, u mnie około 15% (na ideone zysk wychodzi zdecydowanie mniejszy). Ważne: wyniki zaczynają pojawiać się od razu, nie po zakończeniu obliczeń, tak działa leniwa ewaluacja.

Zeby nie było nudno, możemy skorzystać z faktu, że lista jest monadą (a String to [Char]), np. w ten sposób:

main1 = putStrLn $ do
         n <- [1..10000]
         show (sklej' n) ++ "\n"

Wygląda nawet "imperatywnie", nie? :] Przyda Ci się trochę praktyki, pisanie w Haskellu to nie tylko zamiana pętli na rekurencję.

Rozwiązanie w C zawiera algorytm liniwy w czasie i przestrzeni, wypełnienie tablicy n-elementowej. Hmmm, tablice w kodzie funkcyjnym nie są zbyt często spotykane, ale gdyby tak zrobić nieskończoną listę? Zrobić jednolinijkowca, który mieści się na standardowym ekranie (80 kolumn) i korzysta z dwóch monad chociaż jest "czysty"? No way?

fill = 1 : (zipWith (+) [1..] (tail >>= zipWith (+) $ replicate 2 =<< fill))

Piękny i czytelny kod, nie trzeba znać zachowania monady (->) a aby domyślić się działania. Złożoność pamięciowa to w najgorszym wypadku O(n), gdzie w C była ona gwarantowana. Lista budowana jest leniwie, tylko tyle, ile aktualnie trzeba, druga połowa listy jest potrzebna do budowy kolejnych elementów, pierwsza może zostać szybko zutylizowana przez GC. Nie możemy efektywnie indeksować listy, możemy jednak zbudować rekurencję wokół niej, wedle potrzeb podwajając elementy zamiast stosować indeks i / 2. Algorytm tablicowy używał pary sąsiednich elementów, tak też i my robimy, sumujemy głowy aktualnej części "podwojonej" listy i jej ogona. Rozpisując:

tail >>= zipWith (+) $ xs

otrzymujemy:

zipWith (+) (tail xs) xs

Ważne dla nas jest złączenie operacji i powielenie pojedynczego argumentu dla dwóch połączonych funkcji. "Trzecia" lista ([1..]) fizycznie nie istnieje, generowane elementy są używane i zapominane, nie są nigdzie zapisywane. No dobrze, to teraz jakoś trzeba to jeszcze odpalić i wypisać:

main2 = putStrLn $ concat [ show x ++ "\n" | x <- take 10000 fill ]

Tym razem z użyciem list comprehension, połączenie concat i (++ "\n") jest równoważne unlines. Ostatnie mainy są "rozwlekłe" ponieważ są nastawione na prezentowanie różnych konstrukcji w języku.

Podobnych efektów nie da się uzyskać bezpośrednio np. w OCamlu. Scala ma streamy, niestety stream można przejść tylko jednokrotnie. To już zadanie dla Wibowita, za kiepsko Scalą władam żeby jakieś obejście na szybko znaleźć. Co do Haskella to ktoś bardziej doświadczony powinien się wypowiedzieć, dla mnie to narzędzie nauki i intelektualna zabawka.

Kody na ideone:

Trochę rozrywki intelektualnej z rana, Kumashiro zdominował jednolinijkowce w Pythonie, mnie też się coś od życia należy, miłego dnia.

Ależ efekty uboczne są, zostały tylko ujęte w monady.

Moje uproszczenie.

Poza tym nie "+ haskell" tylko "+ GHC", jest kilka środowisk tego języka, tylko jedno naprawdę warte uwagi.

Ja używałem (używam?) tylko GHC, ale wiem jeszcze o Hugs (szybsze od GHC, może tylko interpretować bez możliwości generowania plików wykonywalnych) i NHC (nie ma repl-a ale generuje mniejsze i często szybsze pliki wykonywalne niż GHC). Z tego by wynikało że GHC jest tak pośrodku ale może sytuacja się zmieniła od czasu kiedy to czytałem.

PS. Dobra robota z tym jednolinijkowcem

MSM napisał(a)

Ja używałem (używam?) tylko GHC, ale wiem jeszcze o Hugs (szybsze od GHC, może tylko interpretować bez możliwości generowania plików wykonywalnych) i NHC (nie ma repl-a ale generuje mniejsze i często szybsze pliki wykonywalne niż GHC). Z tego by wynikało że GHC jest tak pośrodku ale może sytuacja się zmieniła od czasu kiedy to czytałem.

To chyba z 10 lat temu czytałeś, zdrowo pomieszałeś:

• Hugs od 5 lat nie jest już rozwijany, to był tylko interpterer, momentami może szybszy od GHCi
• NHC nie ma 100% supportu dla Haskella 98 (to stary standard), generuje dosyć wolny kod, jeszcze w czasach świetności Hugsa przegrywał z GHC, ostatnia wersja w ubiegłym roku wyszła
• GHC to kompletny natywny kompilator Haskella, obecnie ma nawet support dla backendu LLVM, robi zaawansowane optymalizacje
• GHC jest rozwijany przez tych samych ludzi, którzy wyznaczają kierunek rozwoju języka
• cały standardowy toolchain, Haskell Platlform etc. opierają się o GHC, większość narzędzi jest jemu dedykowana
• eksperymentalne kompilatory, jak JHC, zazwyczaj nie implementują całego języka, służą wyłącznie testowaniu nowych koncepcji optymalizacji

Hugs może i jest dobry do nauki podstaw - jest prosty, lekki, szybko sobie kompiluje pliki do kodu pośredniego, większość rzeczy z GHC na nim odpalisz. Do poważniejszych zastosowań alternatyw nie ma. Zwyczajnie haskellowcy są przeciwieństwem linuksowców, rozwijany jest jeden "przemysłowy" kompilator + eksperymentalne, nikt się nie rozdrabnia w milion dystrybucji różniących się tylko logiem, ludzie wolą połączyć siły. Większość mniejszych narzędzi padła na rzecz rozwoju GHC.

Mała errata co do wydajności: Haskell w przypadku ogólnym używa zachowawczo typu całkowitego o dowolnie dużym rozmiarze, Integer. Nam (tak jak i większości funkcji) wystarczy minimum 30 bit, czyli typ Int. Ideone potwierdza zaobserwowane u mnie efekty dodania deklaracji typu Int -> Int i [Int]:

Jeszcze jedna ciekawostka: ten zabytkowy GHC na ideone coś nie chce podstawowych optymalizacji wykonywać, kod:

http://ideone.com/8Co05:

sklej' n | even n    = pred $ n + 2 * sklej'  (n `shiftR` 1)
         | otherwise = pred $ n + sklej' (pred n `shiftR` 1) + sklej' (succ n `shiftR` 1)

z 0.12 spadł do 0.08.

Scala ma streamy, niestety stream można przejść tylko jednokrotnie.

Jak to jednokrotnie? Streamy można przechodzić ile się chce.
Niestety, wersji w Scali nie napiszę, bo nie rozumiem kompletnie przykładu w Haskellu.

Parę razy podchodziłem do nauki programowania funkcyjnego, za Haskela się co najmniej 3 razy zabierałem (z marnym skutkiem), podobnie ze Schemem. Po prostu te języki (lub książki z których korzystałem) mnie odrzuciły. Dopiero spodobał mi się Common Lisp (sic). Nie wiem, może mam jakiś pociąg do skomplikowanych języków (C++), ale pewnie chodzi bardziej o wieloparadygmatowość. Teraz ogólnie podobają mi się 3 języki, Python, C++ (0x) oraz Common Lisp. Każdy z nich ma jeden dominujący paradygmat (proceduralny, obiektowy oraz funkcyjny), ale pozwalają na stosowanie innych podejść tam, gdzie jest to bardziej odpowiednie.

Nie lubię jak mi język za bardzo narzuca pewien sposób myślenia (Java, mówię o tobie), albo za bardzo utrudnia pisanie (programowanie obiektowe w C to koszmar, ale przy pewnej wielkości projektu trzeba). Absolutnie nie podoba mi się php, choć może dla tego, że główna moja styczność z tym językiem to dość spory system z takimi kwiatkami jak plik functions.php (gdzie są prawie wszystkie funkcje używane w tej aplikacji), instrukcja switch rozciągająca się na parę tysięcy linijek oraz chyba naturalne dla php mieszanie kodu z SQL, JS oraz html.

@iooi, przynajmniej w 2.7 była leniwa kolekcja, którą można było przejrzeć tylko jednokrotnie, tak jak generatory w Pythonie. W Scali coś takiego może być trudne do uzyskania, tutaj następuje rekurencja wokół listy. W 2.8 doszły nowe leniwe kolekcje, przejrzę manual i spróbuję to jakoś przenieść.

@Zjarek, Common Lisp jest językiem obiektowym, na funkcyjności polega w mniejszym stopniu niż Python.

@Zjarek, Common Lisp jest językiem obiektowym, na funkcyjności polega w mniejszym stopniu niż Python.

Lisp nie jest może czysto funkcyjny, ale opiera się mocno na przetwarzaniu list (LISt Processing) i funkcjach wyższego rzędu przez co zachęca do myślenia 'funkcyjnego'. Jeśli ktoś chce może pisać równie imperatywie jak w C++ czy Javie, ale czy to wada (Nie lubię jak mi język za bardzo narzuca pewien sposób myślenia)?

@msm, programowanie funkcyjne w CL jest bardzo ubogie, kilka podstawowych funkcji (z czego połowa oznaczona jako "nie używać, jeśli ktoś standard odkopie za 50 lat to je wywali") + brak sensownego wsparcia, nawet komponowania funkcji nie ma w standardzie. Operacje na listach też są dosyć ubogie, 3-4 funkcje realizują to samo, różniąc się nazwą. Z założenia powinno się w nim używać głównie makr imperatywnych (loop) i obiektowości. Tutaj CL ssie najbardziej, język obiektowy z nieobiektową biblioteką standardową, lib i wbudowane typy funkcjonują poza OOP, które jest nadbudowane nad podstawowym językiem.

Co do Twojej sygnaturki, już drugi raz mam poprawiam :P Mniej przekombinowane i bardziej WTF-owe:

a << b = a >> putStr b

Monada ma dwa operatory, >>= (bind) i >> definiowany:

a >> b = a >>= \_ -> b

co jest właśnie opakowaniem w kombinator zapominania. BTW, Control.Monad definiuje operatory odwrotne, bez ukrywania << nie unikniesz konfliktu.

@nnn, Real World Haskell jest znacznie lepsze, The Haskell Road to Logic, Maths and Programming zaś pokazuje matematyczne podejście do programowania, indukcję, dowodzenie poprawności kodu funkcyjnego etc.

Czy Ty wszędzie musisz wciskać pieniądze? Nie wszystko w życiu robi się bezpośrednio dla pieniędzy. Clojure jest beznadzieje, LISP odarty z mechaniki LISPu, niespójny i niejednoznaczny. Połączenie najgorszych cech Scheme i Javy, nie umywa się do Scali.

@iooi, dosłowną translacją tego kodu w Haskellu będzie coś w rodzaju:

val fill:Stream[Int] = 1 #:: fill.flatMap{x => List(x, x)}.sliding(2).toStream.zipWithIndex.map{ case (xs, i) => xs.sum + i + 1 }

Co niestety nie zadziała w tej postaci.

Z założenia powinno się w nim używać głównie makr imperatywnych (loop) i obiektowości. Tutaj CL ssie najbardziej, język obiektowy z nieobiektową biblioteką standardową, lib i wbudowane typy funkcjonują poza OOP, które jest nadbudowane nad podstawowym językiem.

Nie znam 'dobrych praktyk' programowania CL więc nic nie wiem o tym żeby zalecały używanie loop, wiem raczej o tym że jest najbardziej kontrowersyjną funk makrem w języku.

Z tym że wbudowane typy funkcjonują poza OOP akurat nie wiem o co Ci chodzi

1 > (class-of 5)
#<BUILT-IN-CLASS FIXNUM>
1 > (class-of "aaa")
#<BUILT-IN-CLASS SIMPLE-BASE-STRING>
1 > (class-of #'class-of)
#<BUILT-IN-CLASS FUNCTION>

Zresztą OOP może i jest nadbudowany nad podstawowym językiem, w końcu CLOS zaczynało jako zbiór makr a do języka zostało dodane później - ja specjalnie tego nie odczułem.

<offtopic>
Do do drugiej części... właśnie pisałem tutaj między innymi żebyś mnie skrytykował za sygnaturkę bo głupio byłoby wysłać PM :]

Monada ma dwa operatory, >>= (bind) i >> definiowany:

Faktycznie jakoś zapomniałem o '>>', jakoś automatycznie monada przypomniała mi '>>='. (edit -> poprawiłem jeśli nie zabronione)

BTW, Control.Monad definiuje operatory odwrotne, bez ukrywania << nie unikniesz konfliktu.

Chyba nie myślisz że zamierzam tego używać w faktycznym kodzie? ;)

Jeszcze jeden problem z tym - putStr służy jak wiadomo do pisania stringów, i z tym sobie radzi nieźle. Gorzej z innymi typami danych, jak np. liczbami. Z drugiej strony mamy show które świetnie sobie radzi z prawie wszystkim co się da konwertować do napisu... Oprócz napisów właśnie które są escapowane (show to nie odpowiednik toString... istnieje, z tego co wiem, zasada że putStr (show xxx) powinno wypisać xxx właśnie co w przypadku napisów nieszczególnie pasuje).
Znasz jakiś zwięzły sposób (nie będę w końcu robił podpisu na pół strony) na wypisanie poprawnie napisów (bezpośrednio) i wszystkiego innego (przez show)? Myślałem o tworzeniu klasy do tego (ale to jest właśnie przesadnie rozwlekłe) i kombinowałem coś z Data.Typeable ale nieszczególnie mi jak na razie wychodzi...
</offtopic>