Jak ta funkcja jest równoważna z uzyskaniem ostatniego elementu z listy?

Question

Po zakończeniu pierwszego problemu ("Znajdź ostatni element listy") w 99 questions exercises, chciałem zobaczyć, jak moje rozwiązanie w porównaniu z innymi i znalazłem this solution.

myLast' = foldr1 (const id) 

documentation ta wydaje się wskazywać, że foldr1 przyjmuje dwa argumenty, pierwszy jest funkcją, a drugi jest lista. Ta definicja wydaje się jednak przyjmować funkcję jako argument. Czy istnieje domniemana definicja argumentów przekazywanych w ten sposób?

myLast' xs = foldr1 (const id) xs 

Mam spojrzał definicje foldr1, const i id, ale mam trudności ze zrozumieniem, jak te trzy pracują razem, aby powrócić ostatnią pozycję na liście.

Answer 1

Masz całkowitą rację. W Haskell funkcja, która przyjmuje dwa argumenty, może być faktycznie traktowana jako funkcja, która przyjmuje jeden argument i zwraca inną funkcję, która pobiera argument; jest to znane jako currying. Należy pamiętać, że podpis funkcja foldr1 jest:

(a -> a -> a) -> [a] -> a 

Chociaż często myślimy o niej jako „funkcję, która przyjmuje funkcję oraz listę jako argumenty i zwraca wartość”, to naprawdę „funkcję, która przyjmuje funkcję jako argument i zwraca funkcję, która pobiera listę i zwraca wartość ".

Answer 2

Jak wyjaśnia mipadi, funkcja jest wykonywana w trybie curry. To wyjaśnia, w jaki sposób argument listy istnieje, ale może nie wyjaśnia, w jaki sposób działa faktyczny skład.

Bit const id jest trochę trixy. foldr1 spodziewa się uzyskać coś, co ma typ a -> a -> a. Definicje tych funkcji są

const :: x -> y -> x 
const x y = x 

id :: x -> x 
id x = x 

Więc, maglowania, że ​​wszyscy razem, mamy

const id = 
\ y -> id = 
\ y -> \ x -> x = 
\ y x -> x 

w celu słowy const id robi to samo, co flip const; jest to funkcja 2-argumentowa, która wyrzuca pierwszy argument i zwraca drugi. To nie jest aż tak oczywiste, że tak jest; IMHO, flip const będzie bardziej przejrzysty.

foldr1 wywoła tę funkcję ze starą wartością jako pierwszym argumentem, a następny element list jako drugi argument. Ta funkcja zawsze zwraca następny element listy. Ostateczne wyjście z foldr jest ostatnim wynikiem funkcji, która będzie ostatnim elementem całej listy.

Answer 3

Masz rację, że te dwa przykłady można zastąpić nawzajem. Można to traktować jako algebraiczne anulowanie, tak jak w klasie algebry.

f x y = g x y 

mogę anulować y z każdej strony:

f x = g x 

teraz mogę anulować X z każdej strony:

f = g 

przyjrzeć się z wiki page for foldr vs foldl and foldl' aby dowiedzieć się trochę więcej o foldr.

Aby zorientować się, w jaki sposób działa myLast, możemy wykonać suplementację algebraiczną.

myLast' [1, 2, 3] 

== foldr1 (const id) [1, 2, 3] 

Teraz powinniśmy użyć definition of foldr1 w-szczególności: foldr1 f (x:xs) = f x (foldr1 f xs)

== (const id) 1 (foldr1 (const id) [2, 3]) 

const id okazuje się mieć rodzaj sig b -> a -> a która jest taka sama jak flip const i okazuje się, że działa tak samo jak dobrze która jest funkcją, która ignoruje swój pierwszy argument i zwraca drugi. Przykład: (const id) 1 3 == 3* patrz niżej trochę więcej *

== foldr1 (const id) [2, 3] 

== foldr1 (const id) [3] 

== 3 

To ostatni krok nie może być to, czego się spodziewałem, ale jeśli sprawdzeniu definicji foldr1 zawiera:

foldr1 _ [x] = x 

który odpowiada wzór gdy ich jest tylko jeden element na liście i zwraca go.

* Jak działa ?

const zwraca jego pierwszego argumentu i ignoruje to drugi tak

const id 3 == id 

const id 3 4 == id 4 == 4 

Answer 4

Tak, twoja intuicja o funkcje nie wymagające wszystkie swoje argumenty jest na miejscu. A gdy jedna funkcja przyjmuje inną funkcję jako parametr, aby w wyniku tego zwrócić inną funkcję, nazywa się ją "currying". Patrz: http://en.wikipedia.org/wiki/Currying.

(Na marginesie, to faktycznie odkrył (lub odnaleziony) przez Haskell Curry, która jest jak nasz Haskell zawdzięcza swoją nazwę.)

Jeśli pomysł zmiękczania wciąż potrzebuje czasu, aby zatopić w , to może pomóc: W rzeczywistości są dwie funkcje zdefiniowane w Prelude o nazwie curry i uncurry. Prowadzą one następujące typy:

Prelude> :t curry 
curry :: ((a, b) -> c) -> a -> b -> c 
Prelude> :t uncurry 
uncurry :: (a -> b -> c) -> (a, b) -> c 

uncurry wybija 2 argumentu curry funkcja (lub funkcji, które ma funkcję jeden argument zwracającej funkcji jednego argumentu) i wytwarza uncurrried funkcji lub funkcja, która przyjmuje wszystkie argumenty za jednym razem(jako krotka.)

curry, jak może sugerować nazwą i jej rodzaju, idzie w drugą stronę, tak że ma curry funkcyjny (funkcję, która pobiera wszystkie argumenty na raz) i wywołuje funkcję, która przyjmuje jeden argument i zwraca funkcję, która przyjmuje drugi argument.

Większość języków programowania pracuje domyślnie w sposób nieskrywany, podajesz wszystkie argumenty i uzyskujesz wynik, podczas gdy Haskell jest domyślnie ustawiony.

teraz na przykład uncurry, możemy podjąć prostą funkcję, (+):

Prelude> :t (+) 
(+) :: Num a => a -> a -> a 
Prelude> (+) 1 2 
3 
Prelude> :t (+) 
(+) :: Num a => a -> a -> a 
Prelude> :t uncurry (+) 
uncurry (+) :: Num c => (c, c) -> c 
Prelude> uncurry (+) (1,2) 
3 

I moglibyśmy to zrobić także z const jeśli chcemy:

Prelude> :t const 
const :: a -> b -> a 
Prelude> const 1 2 
1 
Prelude> :t uncurry const 
uncurry const :: (c, b) -> c 
Prelude> uncurry const (1,2) 
1 

Ale mając Niespokojna wersja const jest po prostu niezbyt przydatna, ponieważ nie ma sensu posiadanie funkcji, która pobiera dwa argumenty i zawsze zwraca pierwszą, jeśli trzeba określić wszystkie argumenty z góry.

const jest przydatna właśnie dlatego, że jest curry i może być podana w miejscu, gdzie potrzebna jest funkcja, która pobiera dwa argumenty i po prostu zwraca pierwszą.

Podobnie jak w foldr1, na przykład:

Prelude> :t foldr1 
foldr1 :: (a -> a -> a) -> [a] -> a 

Jeśli pierwszy argument jest curry funkcją dwóch argumentów. A ponieważ wartość zwracana funkcji może mieć funkcję, może to być również tak z const:

Prelude> :t const id 
const id :: b -> a -> a 

const id prostu przyjmuje argument dowolnego typu b i zwraca funkcję id.

Więc jeśli możemy zastosować const id krok po kroku:

Prelude> :t const id 1 
const id 1 :: a -> a 

const id 1 lub const id anyOtherValueHere prostu zwraca funkcję id. które mogą być używane tak lubił:

Prelude> :t const id "Giraffe" 100 
const id "Giraffe" 100 :: Num a => a 
Prelude> const id "Giraffe" 100 
100 
Prelude> :t const id (\a b -> undefined) 100 
const id (\a b -> undefined) 100 :: Num a => a 
Prelude> const id (\a b -> undefined) 100 
100 

Więc const naprawdę ignoruje swój drugi argument. Bezpośrednio powyżej, jest jak stosowanie id 100.

So, foldr1 (const id) prostu pobiera listę i utrzymuje stosowania id do każdego zestawu dwóch elementów i zachowaniu drugi (bo const id zwraca wartość id na drugiego argumentu przekazanego in), dopóki nie mamy ostatniego elementu.