„Zapamiętywanie” wartości w programowaniu funkcjonalnym

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?

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.

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.

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

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.