„Zapamiętywanie” wartości w programowaniu funkcjonalnym

20

Postanowiłem podjąć się nauki programowania funkcjonalnego. Do tej pory to był świetny wybuch, a ja „widziałem światło”. Niestety, tak naprawdę nie znam funkcjonalnego programisty, z którego mógłbym odrzucić pytania. Przedstawiamy Stack Exchange.

Biorę udział w kursie tworzenia aplikacji internetowych, ale mój instruktor nie zna programowania funkcjonalnego. Nie przeszkadza mi, że go używam, i właśnie poprosił mnie, aby pomóc mu zrozumieć, jak to działa, aby mógł lepiej czytać mój kod.

Zdecydowałem, że najlepszym sposobem na to jest zilustrowanie prostej funkcji matematycznej, takiej jak podniesienie wartości do potęgi. Teoretycznie mógłbym to łatwo zrobić za pomocą wstępnie zbudowanej funkcji, ale to by pomogło celowi przykładu.

W każdym razie mam trudności z ustaleniem, jak utrzymać wartość. Ponieważ jest to programowanie funkcjonalne, nie mogę zmienić zmiennej. Gdybym miał to bezwzględnie zakodować, wyglądałoby to tak:

(Poniżej znajduje się cały pseudokod)

f(x,y) {
  int z = x;
  for(int i = 0, i < y; i++){
    x = x * z;
  }
  return x;
}

W programowaniu funkcjonalnym nie byłem pewien. Oto co wymyśliłem:

f(x,y,z){
  if z == 'null',
    f(x,y,x);
  else if y > 1,
    f(x*z,y-1,z);
  else
    return x;
}

Czy to jest poprawne? zW obu przypadkach muszę zachować wartość, ale nie byłem pewien, jak to zrobić w programowaniu funkcji. Teoretycznie sposób, w jaki to zrobiłem, działa, ale nie byłem pewien, czy to było „właściwe”. Czy jest na to lepszy sposób?

Ucenna
źródło
32
Jeśli chcesz, aby twój przykład był traktowany poważnie, rozwiąż praktyczny problem, a nie problem matematyczny. Jest to rodzaj frazesu wśród programistów, że „wszystko FP jest dobre do rozwiązywania problemów matematycznych”, a jeśli twój przykład to Jeszcze Inna Funkcja Matematyczna, to tylko wzmacniasz stereotyp, zamiast uczynić to, co robisz, użytecznym.
Mason Wheeler,
12
Twoja próba jest naprawdę całkiem dobra, biorąc pod uwagę względy świata rzeczywistego. Wszystkie twoje rekurencyjne wywołania są wywołaniami ogona , to znaczy, że funkcja nie robi nic innego po ich wywołaniu. Oznacza to, że kompilator lub interpreter, który go obsługuje może je zoptymalizować, aby funkcja rekurencyjna używała stałej ilości pamięci stosu, a nie ilości proporcjonalnej do y.
8bittree
1
Wielkie dzięki za wsparcie! Nadal jestem w tym bardzo nowy, więc mój pseudokod nie jest idealny. @MasonWheeler Chyba w tym przypadku mój kod nie powinien być traktowany poważnie. Wciąż się uczę, a powodem, dla którego kocham FP, jest to, że to matematyka. Chodzi mi o wyjaśnienie nauczycielowi, dlaczego używam FP. Tak naprawdę nie rozumie, co to jest, więc wydawało się, że to dobry sposób, aby pokazać mu zalety.
Ucenna
5
W jakim języku planujesz napisać kod? Nie próbuj używać stylu, który nie jest odpowiedni dla używanego języka.
Carsten S.
2
Prawdopodobnie przydatne: en.wikipedia.org/wiki/Memoization
Ethan Bolker

Odpowiedzi:

37

Przede wszystkim gratuluję „ujrzenia światła”. Uczyniłeś świat oprogramowania lepszym miejscem, poszerzając swoje horyzonty.

Po drugie, szczerze mówiąc, nie ma mowy, żeby profesor, który nie rozumie programowania funkcjonalnego, nie byłby w stanie powiedzieć nic użytecznego o twoim kodzie, poza banalnymi komentarzami, takimi jak „wcięcie się nie zgadza”. Nie jest to zaskakujące na kursie tworzenia stron internetowych, ponieważ większość tworzenia stron internetowych odbywa się za pomocą HTML / CSS / JavaScript. W zależności od tego, jak bardzo zależy ci na nauce tworzenia stron internetowych, możesz zechcieć nauczyć się narzędzi, których naucza twój profesor (choć może to być bolesne - wiem z doświadczenia).

Aby odpowiedzieć na zadane pytanie: jeśli twój imperatywny kod korzysta z pętli, istnieje prawdopodobieństwo, że kod funkcjonalny będzie rekurencyjny.

(* raises x to the power of y *)
fun pow (x: real) (y: int) : real = 
    if y = 1 then x else x * (pow x (y-1))

Zauważ, że ten algorytm jest mniej więcej identyczny z kodem rozkazującym. W rzeczywistości można uznać powyższą pętlę za cukier syntaktyczny dla iteracyjnych procesów rekurencyjnych.

Na marginesie, w rzeczywistości nie ma potrzeby używania zani kodu imperatywnego, ani funkcjonalnego. Powinieneś napisać swoją funkcję imperatywną tak:

def pow(x, y):
    var ret = 1
    for (i = 0; i < y; i++)
         ret = ret * x
    return ret

zamiast zmieniać znaczenie zmiennej x.

ogrodnik
źródło
Twój rekursywny pownie jest w porządku. W tej chwili pow 3 3zwraca 81zamiast 27. Powinno byćelse x * pow x (y-1).
8
3
Ups, pisanie poprawnego kodu jest trudne :) Naprawiono, a także dodałem adnotacje typu. @Ucenna To ma być SML, ale od jakiegoś czasu go nie używałem, więc mogę mieć nieco niepoprawną składnię. Jest zbyt wiele cholernych sposobów na zadeklarowanie funkcji, nigdy nie pamiętam właściwego słowa kluczowego. Poza zmianami składni kod jest identyczny w JavaScript.
ogrodnik
2
@jwg JavaScript ma pewne aspekty funkcjonalne: funkcje mogą definiować funkcje zagnieżdżone, zwracać funkcje i akceptować funkcje jako parametry; obsługuje zamknięcia o zakresie leksykalnym (choć nie ma zakresu dynamicznego lisp). Dyscyplina programisty musi powstrzymać się od zmiany stanu i mutowania danych.
Kasper van den Berg,
1
@jwg Nie ma uzgodnionej definicji języka „funkcjonalnego” (ani „imperatywnego”, „obiektowego” lub „deklaratywnego”). Staram się powstrzymywać od używania tych warunków, gdy tylko jest to możliwe. Pod słońcem jest zbyt wiele języków, aby można je było podzielić na cztery grupy.
ogrodnik
1
Popularność jest okropną miarą, dlatego za każdym razem, gdy ktoś wspomina, że ​​język lub narzędzie X musi być lepsze, ponieważ jest tak powszechnie używane, wiem, że kontynuowanie sporu byłoby bezcelowe. Bardziej znam rodzinę języków ML niż Haskell. Ale nie jestem też pewien, czy to prawda; zgaduję, że zdecydowana większość programistów nie wypróbowała Haskell w pierwszej kolejności.
ogrodnik
33

To naprawdę tylko dodatek do odpowiedzi ogrodnika, ale chciałbym podkreślić, że istnieje nazwa dla wzorca, który widzisz: składanie.

W programowaniu funkcjonalnym fold jest sposobem na połączenie szeregu wartości, które „zapamiętują” wartość między każdą operacją. Zastanów się nad koniecznością dodania listy liczb:

def sum_all(xs):
  total = 0
  for x in xs:
    total = total + x
  return total

Bierzemy listę wartości xsoraz stanu początkowego z 0(reprezentowaną przez totalw tym przypadku). Następnie dla każdej xIN xs, łączy się tę wartość z obecnego stanu Według niektórych łączące działanie (w tym przypadku dodatkowo) i wykorzystać wynik jako nowego stanu. W istocie sum_all([1, 2, 3])jest równoważne z (3 + (2 + (1 + 0))). Ten wzorzec można wyodrębnić do funkcji wyższego rzędu , która akceptuje funkcje jako argumenty:

def fold(items, initial_state, combiner_func):
  state = initial_state
  for item in items:
    state = combiner_func(item, state)
  return state

def sum_all(xs):
  return fold(xs, 0, lambda x y: x + y)

Ta implementacja foldjest nadal niezbędna, ale można ją również wykonać rekurencyjnie:

def fold_recursive(items, initial_state, combiner_func):
  if not is_empty(items):
    state = combiner_func(initial_state, first_item(items))
    return fold_recursive(rest_items(items), state, combiner_func)
  else:
    return initial_state

Wyrażona jako krotnie, twoja funkcja jest po prostu:

def exponent(base, power):
  return fold(repeat(base, power), 1, lambda x y: x * y))

... gdzie repeat(x, n)zwraca listę nkopiix .

Wiele języków, szczególnie tych ukierunkowanych na programowanie funkcjonalne, oferuje składanie w swojej standardowej bibliotece. Nawet Javascript zapewnia to pod nazwą reduce. Ogólnie rzecz biorąc, jeśli używasz rekurencji do „zapamiętywania” wartości w jakiejś pętli, prawdopodobnie potrzebujesz fold.

Jacek
źródło
8
Zdecydowanie naucz się rozpoznawać, kiedy problem można rozwiązać za pomocą zakładki lub mapy. W FP prawie wszystkie pętle można wyrazić jako fold lub mapę; więc wyraźna rekurencja zwykle nie jest konieczna.
Carcigenicate 20.09.16
1
W niektórych językach możesz po prostu napisaćfold(repeat(base, power), 1, *)
użytkownik253751
4
Rico Kahler: scanjest zasadniczo miejscem, w foldktórym zamiast po prostu połączyć listę wartości w jedną wartość, jest on łączony, a każda wartość pośrednia jest wyrzucana z powrotem po drodze, tworząc listę wszystkich stanów pośrednich utworzonych przez złożenie zamiast po prostu generować stan końcowy. Jest możliwy do wdrożenia pod względem fold(każda operacja zapętlania jest).
Jack
4
@RicoKahler I, o ile mogę powiedzieć, redukcje i fałdy są tym samym. Haskell używa terminu „fold”, podczas gdy Clojure woli „redukować”. Ich zachowanie wydaje mi się takie samo.
Carcigenicate
2
@Ucenna: Jest to zarówno zmienna, jak i funkcja. W programowaniu funkcjonalnym funkcje są wartościami takimi jak liczby i ciągi znaków - możesz przechowywać je w zmiennych, przekazywać je jako argumenty do innych funkcji, zwracać je z funkcji i ogólnie traktować je jak inne wartości. Więc combiner_funcjest to argument, a sum_alljest przepuszczanie anonimową funkcję (to lambdabit - tworzy wartość funkcji bez nazywania go), który określa, jak ona chce połączyć dwa elementy razem.
Jack
8

To jest dodatkowa odpowiedź, która pomaga wyjaśnić mapy i fałdy. W poniższych przykładach użyję tej listy. Pamiętaj, że ta lista jest niezmienna, więc nigdy się nie zmieni:

var numbers = [1, 2, 3, 4, 5]

Użyję liczb w moich przykładach, ponieważ prowadzą one do łatwego do odczytania kodu. Pamiętaj jednak, że fałdy mogą być używane do wszystkiego, do czego może być używana tradycyjna pętla imperatywna.

mapa pobiera listę coś i funkcję i zwraca listę, która została zmodyfikowana za pomocą funkcji. Każdy element jest przekazywany do funkcji i staje się tym, co funkcja zwraca.

Najłatwiejszym tego przykładem jest dodanie numeru do każdego numeru na liście. Użyję pseudokodu, aby był niezależny od języka:

function add-two(n):
    return n + 2

var numbers2 =
    map(add-two, numbers) 

Jeśli wydrukowałeś numbers2, zobaczysz, [3, 4, 5, 6, 7]która jest pierwsza lista z 2 dodanymi do każdego elementu. Zauważ, że funkcja add-twozostała przekazanamap użyta.

Fold s są podobne, z tym wyjątkiem, że funkcja, którą musisz im nadać, musi przyjąć 2 argumenty. Pierwszym argumentem jest zwykle akumulator (w lewej części, które są najczęściej). Akumulator to dane przekazywane w pętli. Drugi argument to bieżący element listy; podobnie jak powyżej dla mapfunkcji.

function add-together(n1, n2):
    return n1 + n2

var sum =
    fold(add-together, 0, numbers)

Jeśli wydrukowałeś sum , zobaczysz sumę listy liczb: 15.

Oto argumenty do foldzrobienia:

  1. Jest to funkcja, którą dajemy fold. W folderze przejdzie funkcja bieżącego akumulatora i bieżąca pozycja na liście. Cokolwiek zwróci funkcja, stanie się nowym akumulatorem, który zostanie przekazany do funkcji następnym razem. W ten sposób „zapamiętujesz” wartości, gdy zapętlasz styl FP. Dałem mu funkcję, która pobiera 2 liczby i dodaje je.

  2. To jest akumulator początkowy; co akumulator zaczyna, jak przed przetworzeniem jakichkolwiek pozycji na liście. Kiedy sumujesz liczby, jaka jest suma, zanim dodasz jakieś liczby razem? 0, które podałem jako drugi argument.

  3. Wreszcie, podobnie jak w przypadku mapy, przekazujemy również listę liczb do przetworzenia.

Jeśli fałdy nadal nie mają sensu, rozważ to. Kiedy piszesz:

# Notice I passed the plus operator directly this time, 
#  instead of wrapping it in another function. 
fold(+, 0, numbers)

Zasadniczo umieszczasz przekazaną funkcję między każdą pozycją na liście i dodajesz akumulator początkowy do lewej lub prawej (w zależności od tego, czy jest to lewy czy prawy pas), więc:

[1, 2, 3, 4, 5]

Staje się:

0 + 1 + 2 + 3 + 4 + 5
^ Note the initial accumulator being added onto the left (for a left fold).

Co równa się 15.

Użyj a, mapjeśli chcesz zamienić jedną listę na inną, o tej samej długości.

Użyj a, foldgdy chcesz zmienić listę w pojedynczą wartość, na przykład sumując listę liczb.

Jak zauważył @Jorg w komentarzach, „pojedyncza wartość” nie musi być czymś prostym jak liczba; może to być dowolny pojedynczy obiekt, w tym lista lub krotka! Sposób, w jaki faktycznie kliknąłem dla siebie foldery, polegał na zdefiniowaniu mapy w kategoriach fold. Zwróć uwagę, jak akumulator jest listą:

function map(f, list):
    fold(
        function(xs, x): # xs is the list that has been processed so far
            xs.add( f(x) ) # Add returns the list instead of mutating it
        , [] # Before any of the list has been processed, we have an empty list
        , list) 

Szczerze mówiąc, kiedy zrozumiesz każdy, zdasz sobie sprawę, że prawie każdą pętlę można zastąpić fałdem lub mapą.

Carcigenicate
źródło
1
@Ucenna @Ucenna W twoim kodzie jest kilka wad (jak inigdy się nie definiuje), ale myślę, że masz dobry pomysł. Jednym z problemów w twoim przykładzie jest: funkcja ( x), przekazywana jest tylko jeden element listy na raz, a nie cała lista. Przy pierwszym xwywołaniu przekazuje on początkowy akumulator ( y) jako pierwszy argument, a pierwszy element jako drugi argument. Przy następnym uruchomieniu xprzekaże nowy akumulator po lewej stronie (cokolwiek xzwrócił za pierwszym razem), a drugi element listy jako drugi argument.
Carcigenicate 21.09.16
1
@Ucenna Teraz, gdy masz już podstawowy pomysł, spójrz ponownie na implementację Jacka.
Carcigenicate 21.09.16
1
@Ucenna: Różne języki mają różne preferencje co do tego, czy funkcja spasowania przyjmuje akumulator jako pierwszy czy drugi argument, niestety. Jednym z powodów, dla których miło jest używać operacji przemiennej, takiej jak dodawanie, aby uczyć składania.
Jack
3
„Użyj a, foldgdy chcesz zmienić listę w jedną wartość (np. Sumując listę liczb)”. - Chcę tylko zauważyć, że ta „pojedyncza wartość” może być dowolnie złożona… łącznie z listą! W rzeczywistości foldjest to ogólna metoda iteracji, która może zrobić wszystko , co może zrobić iteracja. Np. mapMoże być trywialnie wyrażony jako func map(f, l) = fold((xs, x) => append(xs, f(x)), [], l)tutaj, „pojedyncza wartość” obliczona przez foldto tak naprawdę lista.
Jörg W Mittag
2
… Być może chcesz zrobić z listą, możesz to zrobić fold. I nie musi to być lista, wystarczy każda kolekcja, która może być wyrażona jako pusta / niepusta. Co w zasadzie oznacza, że ​​zrobi to dowolny iterator. (wydaje mi się, że wrzucenie słowa „katamorfizm” byłoby zbyt wiele do wprowadzenia dla początkującego :-D)
Jörg W Mittag
1

Trudno znaleźć dobre problemy, których nie można rozwiązać za pomocą wbudowanej funkcjonalności. A jeśli jest wbudowany, powinien być używany jako przykład dobrego stylu w języku x.

Na przykład w haskell masz już funkcję (^)Preludium.

Lub jeśli chcesz to zrobić bardziej programowo product (replicate y x)

Mówię o tym, że trudno jest pokazać mocne strony stylu / języka, jeśli nie korzystasz z jego funkcji. Jednak może to być dobry krok w kierunku pokazania, jak to działa za kulisami, ale myślę, że powinieneś napisać najlepszy sposób w jakimkolwiek języku, którego używasz, a następnie pomóc osobie stamtąd zrozumieć, co się dzieje w razie potrzeby.

Viktor Mellgren
źródło
1
Aby logicznie połączyć tę odpowiedź z innymi, należy zauważyć, że productjest to po prostu funkcja skrótu foldz mnożeniem jako jej funkcją i 1 jako początkowym argumentem, i replicatejest to funkcja, która generuje iterator (lub listę; jak zauważyłem powyżej dwa są zasadniczo nie do odróżnienia w haskell), co daje daną liczbę identycznych wyników. Teraz powinno być łatwo zrozumieć, jak ta implementacja robi to samo, co odpowiedź @ Jacka powyżej, po prostu używając predefiniowanych specjalnych wersji tych samych funkcji, aby uczynić ją bardziej zwięzłą.
Periata Breatta