Konstrukcje imperatywne w programowaniu funkcyjnym

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
???

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:)

0

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

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?

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... :)

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

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ść. :)

0

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

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"?

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.

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ą).

0
koszalek-opalek napisał(a):

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

Ale @Wibowit pokazał, że monady to nic innego jak zbiór trzech funkcji przestrzegające określonych praw i to, że nie zgadza się na obrazowanie monad za pomocą burrito. Ciebie poprosiłem o rozwinięcie tematu "opakowanie, które może naśladować czynności" oraz "tablice realizowane przez monady są jak najbardziej na porządku dziennym" bo po prostu nie do końca rozumiem te dwa zdania.

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