Definicja długości za pomocą foldr

Question

Próbuję zrozumieć część w uwagach do wykładu z zajęć, które biorę. Definiuje funkcję długości jako:

length = foldr (\_ n -> 1 + n) 0 

Czy ktoś może mi wyjaśnić, jak to działa? Nie mogę otoczyć się tym.

Answer 1

Najpierw, z foldr: (a -> b -> b) -> b -> [a] -> b

Biorąc użycia w kontekście, foldr pobiera 3 argumenty funkcji (które pobiera element listy i b akumulator,.. i zwraca akumulator), wartość początkową akumulatora i listę. foldr zwraca końcowy wynik akumulatora po zastosowaniu funkcji na liście.

chodzi o ten kawałek kodu:

length = foldr (\_ n -> 1 + n) 0 

Jak widać, to brakuje na liście - tak wartość zwracaną po prawej stronie to funkcja, która odbędzie się na liście i produkują Int (ten sam typ co 0). Wpisz: [a] -> Int.

chodzi o to, co prawej stronie oznacza: (\_ n -> 1 + n) 0

\ środki zadeklarować nienazwany funkcję

_ środki ignorować elementu z listy (odpowiadają a w rodzaju foldr). Jak wiesz, foldr przejdzie przez listę i zastosuje funkcję do każdego elementu. Jest to element przekazany do funkcji. Nie używamy go w funkcji length, więc oznaczamy, że należy go zignorować.

n to parametr dla przekazywanego przez Int jako akumulator.

-> środki powrotne

1 + n będzie zwiększać akumulatora. Można sobie wyobrazić, że zwracana wartość jest przekazywana z powrotem do foldr i foldr zapisuje wartość, aby przejść do następnego połączenia z funkcją (\_ n -> 1 + n).

Wartość 0 poza nawiasem jest wartością początkową licznika.

Answer 2

Funkcja foldr jest rozkładana na liście z prawej operatora asocjacyjnej, można łatwo zrozumieć, co funkcja robi, jeśli użyć operatora (+) (Funkcja ma takie samo zachowanie jak sum):

foldr (+) 0 [1,2,3,4,5] = 1+(2+(3+(4+(5+0)))) 

dla funkcji długości, jest równoznaczne z:

foldr (\_ n -> 1 + n) 0 [1,2,3,4,5] = 1+(1+(1+(1+(1+0)))) 

to właśnie foldr dla

Answer 3

Istnieje kilka równoważnych sposobów, aby to zrozumieć.Pierwszy z nich: foldr f z [1, 2, 3, 4, ..., n] oblicza następującą wartość:

f 1 (f 2 (f 3 (f 4 (f ... (f n z))))) 

Więc w twoim przypadku:

length [1,2,3,4] = foldr (\_ n -> 1 + n) 0 [1,2,3,4] 
       = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 ((\_ n -> 1 + n) 4 0))) 
       = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 (1 + 0))) 
       = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 (1 + (1 + 0))) 
       = (\_ n -> 1 + n) 1 (1 + (1 + (1 + 0))) 
       = 1 + (1 + (1 + (1 + 0))) 
       = 1 + (1 + (1 + 1)) 
       = 1 + (1 + 2) 
       = 1 + 3 
       = 4 

Kolejnym jest zacząć od tej funkcji, która kopiuje listę:

listCopy :: [a] -> [a] 
listCopy [] = [] 
listCopy (x:xs) = x : listCopy xs 

Że może wyglądać jak trywialna funkcja, ale foldr jest po prostu tym, ale z wyjątkiem kodowania na pustej liście [] i konstruktora par : po prawej stronie, zamiast tego używamy pewnej arbitralnej stałej i funkcji dostarczonej jako argumenty. Ja czasami lubię nazywać te argumenty fakeCons i fakeNil (cons i nil są nazwy operatora : i [] stała w języku Lisp), ponieważ w pewnym sensie jesteś „kopiowanie” lista, ale przy użyciu fałszywych konstruktorów:

foldr fakeCons fakeNil [] = fakeNil 
foldr fakeCons fakeNil (x:xs) = fakeCons x (subfold xs) 
    where subfold = foldr fakeCons fakeNil 

Więc pod tą interpretacją, czynność length to „kopiowanie” lista, z wyjątkiem, że zamiast pustej liście jest za pomocą 0 i zamiast : to odrzucając elementy i dodając 1 do uruchomionej sumie.

A oto jeszcze jedna trzecia intepretation z foldr f z xs:

1. z jest rozwiązaniem problemu, gdy lista jest pusta.
2. f to funkcja, która przyjmuje dwa argumenty: element listy, a częściowe rozwiązanie: rozwiązanie problemu na liście elementów, które pojawiają się po prawej stronie elementu, który jest przekazywany do f. f następnie tworzy rozwiązanie, które jest "jeden element większy".

Tak więc w przypadku length:

1. Długość pustej listy wynosi 0, więc to dlaczego używasz 0 jako drugi argument do foldr.
2. Jeśli długość xs to n, to długość x:xs to n+1. Oto, co robi twój pierwszy argument na foldr, \_ n -> n + 1: oblicza długość listy, podając jako argumenty pierwszy element listy (który w tym przypadku ignorujemy) i długość reszty listy (n) .

Ten sposób myślenia o foldr jest bardzo potężny i nie należy go lekceważyć. Zasadniczo w funkcji, którą przekazujesz jako pierwszy argument do foldr, możesz założyć, że problem, który próbujesz rozwiązać, został już rozwiązany dla wszystkich list krótszych niż ten, z którym masz do czynienia. Trzeba zatem wykonać całą swoją funkcję argumentu, aby obliczyć odpowiedź dla listy, która jest dłuższa o jeden element.