Początki w programowaniu funkcyjnym

Odpowiedz Nowy wątek
2011-08-10 20:48
0

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.

Pozostało 580 znaków

2011-08-10 20:54
0

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.


Pozostało 580 znaków

2011-08-10 21:41
0
<spam> A ja polecam Scalę. Jest wieloparadygmatowa, możesz np napisać program w imperatywnym stylu, a potem go stopniowo przerabiać na styl funkcyjny. Wg mnie jest łatwiejsza do nauczenia niż Haskell (OCamla nie znam), jeżeli masz doświadczenie w językach imperatywnych. No i Haskell nie jest obiektowy. Scala jest generalnie zauważalnie szybsza od OCamla czy Haskella (tzn sugerując się: http://shootout.alioth.debian[...]ing-languages-are-fastest.php ) oraz w pełni współpracuje z Javą, a więc będziesz miał dostęp do ton bibliotek do Javy oraz będziesz mógł użyć Scali w istniejących Javowych projektach. </spam>

(Znaczniki dla odstraszenia upierdliwców)


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-08-10 21:53
ofidyfil
1

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.

Pozostało 580 znaków

2011-08-10 22:11
msm
0

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ś.

edytowany 2x, ostatnio: msm, 2011-08-10 22:14

Pozostało 580 znaków

2011-08-10 22:51
ofidyfil
0
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 :]

Pozostało 580 znaków

2011-08-10 23:04
0

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

Pozostało 580 znaków

2011-08-10 23:20
0

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.


edytowany 1x, ostatnio: hauleth, 2011-08-10 23:21

Pozostało 580 znaków

2011-08-10 23:39
msm
0

@Up - jest jakieś IDE do haskella?

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

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

edytowany 5x, ostatnio: msm, 2011-08-10 23:43
Gedit + haskell - hauleth 2011-08-11 00:30

Pozostało 580 znaków

2011-08-11 07:34
ofidyfil
1
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:
link
opis czas pamięć
http://ideone.com/rgT1Q oryginalny kod 0.45s 3596 kB
http://ideone.com/CBuKQ z poprawkami 0.42s 3596 kB
http://ideone.com/9jUmx nieskończona lista 0.01s 4616 kB

Zużycie pamięci trochę wzrosło, ale to GC, prealokuje większe bloki, w dwóch pierwszych kodach program mógł się obejść całkowicie bez alokacji. Z drugiej strony czas wykonywania jakby się skrócił :]

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

Dzięki. Haskella się jeszcze uczę i bardzo mi ten post pomoże w nauce. - hauleth 2011-09-03 23:40
A mam jeszcze pytanie. Jak działa operator =<<? - hauleth 2011-09-04 16:14

Pozostało 580 znaków

2011-08-11 11:33
msm
0

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 user image

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0