Konstrukcje imperatywne w programowaniu funkcyjnym

Odpowiedz Nowy wątek
2018-12-10 21:24
0

Tak jak w temacie :)

Czy jest ktoś w stanie pomóc mi odpowiedzieć na to pytanie ??

Czy są to np:

Referencje
‎Tablice
Pętle
???

Co Masz na myśli, pisząc "Konstrukcje imperatywne", Mógłbyś podać przykład? - lion137 2018-12-10 21:43
właśnie sam o to pytam. Zetknąłem się z takim stwierdzeniem. Jestem bardzo ciekawy co się za tym kryje. - natsukiss 2018-12-10 21:44
może chodzi o coś w stylu "do notation" w Haskellu? - LukeJL 2018-12-10 22:36

Pozostało 580 znaków

2018-12-10 22:36
2

Sam też jestem ciekawy:), bo modele imperatywny i funkcyjny są diametralnie różne. Jedyne co mi przychodzi na myśl, to tzw. model deklaratywny, gdzie fragmety kodu zmienające "state" (imperatywne), są lokalne i nie naruszają paradygmatu [funkcyjnego]. Np.:

# pure(?) function to sum array
fun sum(xs):
    s = 0
    while ! empty(xs):
        s += xs[0]
        xs = rest(xs)
    return s

Gdzie xs to lista liczb, a rest to reszta (rest([1, 2, 3]) = [2, 3])
To samo można napisać czysto "funkcyjnie":

fun sum(xs):
    if empty(xs):
        return 0
    else:
        return xs[0] + sum(rest(xs))

To samo czy to samo?:) Oczywiście ta funkcja nie jest za bardzo użyteczna, bo rekurencja rozwali nam stos; więc można użyć TCO (Tail Call Optimization):

fun sum(xs):
    fun helper(ys, acc, n):
        if n == 0:
            return acc
        else:
            return helper(rest(ys), ys[0] + acc, n - 1)
    return helper(xs, 0, len(xs)) # len(coll) = length of a collection coll

Korzystamy z tego, że w językach funkcyjnych funkcje są First Class Citizens - czyli możemy sobie, np., definiować funkcję w funkcji. Jak w języku TCO is on, to kompilator zamieni ostatni kod na pierwszy:)


Pozostało 580 znaków

2018-12-10 22:44
0

Nie wiadomo o co chodzi. Potrzebny jest kontekst.
Zetknąłem się z takim stwierdzeniem. Gdzie?


Bardzo lubie Singletony, dlatego robię po kilka instancji każdego.
Uczelnia - egzamin dyplomowy 2 stopnia ;) - natsukiss 2018-12-10 22:45
Czyli zupełnie nie wiadomo co poeta miał na myśli :/ - jarekr000000 2018-12-10 22:47

Pozostało 580 znaków

2018-12-11 16:38
0

W programowaniu czysto funkcyjnym (Haskell :)) wszystkie konstrukcje są nieimperatywne, ale mogą na takie wyglądać. Do implementacji konstrukcji naśladujących imperatywne używa się tam monad (choć to nie jedyne, to jednak chyba najwygodniejsze narzędzie). Pętle są właściwie niepotrzebne w programowaniu funkcyjnym (rekurencja -- szczególnie ogonowa -- daje radę), ale tablice realizowane przez monady są jak najbardziej na porządku dziennym. Co natomiast rozumiesz przez referencje?

To ja pytam co to za konstrukcje... próbowałem "strzelać". I chce aby ktoś mnie wyprowadził z błędu lub utwierdził w moim przekonaniu. Co do monad to spotkałem się już z tym że jest to konstrukcja imperatywna w programowaniu funkcyjnym, to fakt :D - natsukiss 2018-12-11 16:41

Pozostało 580 znaków

2018-12-11 16:46
1

@natsukiss:

To ja pytam co to za konstrukcje... próbowałem "strzelać". I chce aby ktoś mnie wyprowadził z błędu lub utwierdził w moim przekonaniu. Co do monad to spotkałem się już z tym że jest to konstrukcja imperatywna w programowaniu funkcyjnym, to fakt :D

Na temat w postach, nie w komentarzach. :)

Monada nie jest konstrukcją imperatywną w programowaniu funkcyjnym. Będę się upierał przy tym, że w językach czysto funkcyjnych (jak właśnie Haskell), nie ma konstrukcji imperatywnych, lecz tylko takie, które funkcyjnie implementują to, co my widzimy jako konstrukcje imperatywne. Monada jest takim matematycznym opakowaniem (nie jedynym możliwym, zresztą, ale najwygodniejszym), które może naśladować czynności -- ale sama konstrukcja jest jak najbardziej funkcyjna.

Oczywiście, dla niektórych będzie to różnica jedynie kosmetyczna... :)

edytowany 1x, ostatnio: koszalek-opalek, 2018-12-11 16:46

Pozostało 580 znaków

2018-12-11 17:09
0

Dziwne zatem, że uczelnia podaje takie pytanie na egzaminie dyplomowym drugiego stopnia :D

Pojutrze z ciekawości aż sam pójdę do Profesora aby "dokształcić" się w tej dziedzinie :D

Pozostało 580 znaków

2018-12-11 17:10
0
natsukiss napisał(a):

Dziwne zatem, że uczelnia podaje takie pytanie na egzaminie dyplomowym drugiego stopnia :D

Pojutrze z ciekawości aż sam pójdę do Profesora aby "dokształcić" się w tej dziedzinie :D

Eee, nie dziwne. Skrót myślowy, a mi chodziło o ścisłość. :)

Pozostało 580 znaków

2018-12-11 17:14
0

To w takim razie jesteś w 100 procentach w stanie zdefiniować strukturę imperatywną?

edytowany 1x, ostatnio: natsukiss, 2018-12-11 17:14

Pozostało 580 znaków

2018-12-11 19:24
0
koszalek-opalek napisał(a):

Monada nie jest konstrukcją imperatywną w programowaniu funkcyjnym. Będę się upierał przy tym, że w językach czysto funkcyjnych (jak właśnie Haskell), nie ma konstrukcji imperatywnych, lecz tylko takie, które funkcyjnie implementują to, co my widzimy jako konstrukcje imperatywne. Monada jest takim matematycznym opakowaniem (nie jedynym możliwym, zresztą, ale najwygodniejszym), które może naśladować czynności -- ale sama konstrukcja jest jak najbardziej funkcyjna.

Rozwiniesz troszkę co rozumiesz poprzez "opakowanie, które może naśladować czynności" oraz " tablice realizowane przez monady są jak najbardziej na porządku dziennym"?

Pozostało 580 znaków

2018-12-11 20:08
2

Monada jest takim matematycznym opakowaniem (nie jedynym możliwym, zresztą, ale najwygodniejszym), które może naśladować czynności

Monada to połączenie generycznego typu M[_] z implementacją 3 metod dla niego:

  • pure/point/ etc do opakowania dowolnej wartości w monadę, czyli pure: A => M[A]
  • map do mapowania typu wewnątrz monady, czyli map: M[A] => M[B]
  • flatten do spłaszczania warstw, czyli flatten: M[M[A]] => M[A]
    Alternatywnie zamiast flatten może być (i zwykle jest) flatMap/ bind/ etc które to jest równoważne map + flatten. Między pure, map i flatMap muszą zachodzić pewne prawa, by typ wraz z tymi metodami tworzyły monadę. Google: monad laws

Monada nie ma żadnego obrazowego wytłumaczenia. Nie jest żadnym kontekstem, opakowaniem, itd Monada to po prostu typ + 3 metody, które spełniają określone prawa. Tylko tyle, albo i aż tyle. Dzięki tym prawom można budować mnóstwo kolejnych funkcji opartych na tych metodach, także spełniających konkretne prawa.

Oprócz tych 3 metod oczywiście monada powinna mieć jakieś kolejne, by była użyteczna. Np kolekcje w Scali/ Haskellu/ etc są monadami, ale oprócz map, flatMap i pure mają np metody do wyciągania elementu z kolekcji. Monada typu Parser ma metodę do parsowania łańcucha znaków i wypluwania np drzewka AST. I tak dalej...

Monada IO natomiast to szczególny typ monady. Służy do odłożenia w czasie efektów ubocznych aż do momentu zinterpretowania monady IO w interpreterze. W Haskellu zwyczajowo interpreter jest wbudowany, a metoda wejściowa main ma zwracać typ IO. Każdy efekt uboczny jest opakowany w typ IO, więc nie można bezpośrednio go odpalić, a tylko składać monady IO za pomocą wbudowanych w nią kombinatorów (czyli pure, map, flatMap + wiele innych).

Główną różnicą między monadą IO, a typowym programowaniem imperatywnym jest to, że w przypadku monad IO to wywołująca metoda ma kontrolę na tym czy, kiedy i w jaki sposób efekty uboczne zostaną wykonane (a nie metoda wywoływana) - takie inversion of control, tylko na zupełnie innym poziomie. Mogę np:

  • stworzyć 5 monad IO (tzn instancji typu IO), a potem zwrócić tylko jedną z nich - w takim wypadku 4 z nich nie będą miały szansy w ogóle się wykonać
  • z metody wewnętrznej zwrócić monadę IO bez podawania timeoutów, stopnia zrównoleglenia, etc a dopiero w metodzie wyżej skorzystać z metod na typie IO, np IO.async, IO.timeout, IO.pause, IO.resume, które sterują procesem interpretowania monady IO

Główną wadą monady IO jest narzut pamięciowy i obliczeniowy, tym większy im mniejsze operacje chcemy robić za pomocą monad IO.

Jeśli chodzi o połączenie imperatywności i funkcyjności to możliwe jest stworzenie funkcji, które używają np mutowalnych struktur danych wewnątrz, ale nie modyfikują parametrów ani nie korzystają w żaden sposób z globalnego mutowalnego stanu. Załóżmy, że mamy funkcję sort, która ma na wejściu i na wyjściu kolekcję elementów, ale kolekcja wejściowa jest zawsze niezmieniana. Tylko w środku metody sort mamy użytą zwykłą mutowalną tablicę, zmienne itd po to by przyspieszyć sortowanie, ale z zewnątrz efektów ubocznych nie da się zaobserwować. W takim przypadku funkcję sort można traktować jako czystą funkcyjnie (z perspektywy kodu jedynie wywołującego funkcję sort, a nie analizującego jej). Takich lokalnych imperatywnych optymalizacji jest pełno w standardowej Scalowej implementacji funkcyjnych kolekcji.


"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.
edytowany 5x, ostatnio: Wibowit, 2018-12-11 20:51

Pozostało 580 znaków

2018-12-12 10:02
0

Miałem się rozwinąć, ale @Wibowit już pięknie to opisał. :)

Jedno tylko uzupełnienie/uwaga.

Wibowit napisał(a):

Jeśli chodzi o połączenie imperatywności i funkcyjności to możliwe jest stworzenie funkcji, które używają np mutowalnych struktur danych wewnątrz, ale nie modyfikują parametrów ani nie korzystają w żaden sposób z globalnego mutowalnego stanu. Załóżmy, że mamy funkcję sort, która ma na wejściu i na wyjściu kolekcję elementów, ale kolekcja wejściowa jest zawsze niezmieniana. Tylko w środku metody sort mamy użytą zwykłą mutowalną tablicę, zmienne itd po to by przyspieszyć sortowanie, ale z zewnątrz efektów ubocznych nie da się zaobserwować. W takim przypadku funkcję sort można traktować jako czystą funkcyjnie (z perspektywy kodu jedynie wywołującego funkcję sort, a nie analizującego jej). Takich lokalnych imperatywnych optymalizacji jest pełno w standardowej Scalowej implementacji funkcyjnych kolekcji.

Wszystkie nasze komputery na najniższym poziomie są imperatywne i kropka. Więc wszystkie funkcyjne elementy języków (i całe języki funkcyjne) są implementowane (schodząc na poziom najniższy) imperatywnie, tak jak tu @Wibowit pisze. Ale nie sądzę, by można było to nazwać połączeniem imperatywności i funkcyjności, bo na zewnątrz, dla użytkownika przykładowej funkcji sort mamy czystą funkcyjność (czyli przezroczystość referencyjną).

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