Wyjaśnienie kombinatorów dla człowieka pracy

93

Co to jest kombinator?

Czy jest to „funkcja lub definicja bez wolnych zmiennych” (zgodnie z definicją w SO)?

A co powiesz na to: według Johna Hughesa w jego dobrze znanym artykule na temat strzałek „kombinator to funkcja, która buduje fragmenty programu z fragmentów programu” , co jest korzystne, ponieważ „… programista używający kombinatorów konstruuje wiele z pożądanych program automatycznie, zamiast pisać każdy szczegół ręcznie ”. Mówi dalej mapi podaje filterdwa typowe przykłady takich kombinatorów.

Niektóre kombinatory pasujące do pierwszej definicji:

Niektóre kombinatory pasujące do drugiej definicji:

  • mapa
  • filtr
  • zwiń / zmniejsz (prawdopodobnie)
  • dowolne z >> =, komponuj, fmap ?????

Nie interesuje mnie pierwsza definicja - nie pomogłyby mi w napisaniu prawdziwego programu (+1, jeśli przekonasz mnie, że się mylę). Proszę, pomóż mi zrozumieć drugą definicję . Myślę, że mapowanie, filtrowanie i redukowanie są przydatne: pozwalają mi programować na wyższym poziomie - mniej błędów, krótszy i bardziej przejrzysty kod. Oto kilka moich szczegółowych pytań dotyczących kombinatorów:

  1. Czy jest więcej przykładów kombinatorów, takich jak mapa, filtr?
  2. Jakie kombinatory często implementują języki programowania?
  3. W jaki sposób kombinatory mogą pomóc mi zaprojektować lepsze API?
  4. Jak zaprojektować skuteczne kombinatory?
  5. Jakie kombinatory są podobne do w języku niefunkcjonalnym (powiedzmy, Java) lub czego te języki używają zamiast kombinatorów?

Aktualizacja

Dzięki @CA McCann mam teraz nieco lepsze zrozumienie kombinatorów. Ale jedno pytanie wciąż jest dla mnie sporne:

Jaka jest różnica między programem funkcjonalnym napisanym z użyciem kombinatorów a programem napisanym bez dużego użycia kombinatorów?

Podejrzewam, że odpowiedź jest taka, że ​​wersja z dużą ilością kombinatorów jest krótsza, bardziej przejrzysta, bardziej ogólna, ale w miarę możliwości doceniłbym bardziej dogłębną dyskusję.

Szukam również więcej przykładów i wyjaśnień złożonych kombinatorów (tj. Bardziej złożonych niż fold) w popularnych językach programowania.

Matt Fenwick
źródło
4
Rozważam mapowanie / filtrowanie / zwijanie funkcji wyższego rzędu i używam ich cały czas. Nadal nie mam pojęcia, co to jest kombinator.
1
@pst - Zgodziłbym się 5 dni temu, ale teraz nie mogę kłócić się z Johnem Hughesem
Matt Fenwick

Odpowiedzi:

93

Nie interesuje mnie pierwsza definicja - nie pomogłyby mi w napisaniu prawdziwego programu (+1, jeśli przekonasz mnie, że się mylę). Proszę, pomóż mi zrozumieć drugą definicję. Myślę, że mapowanie, filtrowanie i redukowanie są przydatne: pozwalają mi programować na wyższym poziomie - mniej błędów, krótszy i bardziej przejrzysty kod.

Te dwie definicje to w zasadzie to samo. Pierwsza opiera się na formalnej definicji, a podane przykłady to prymitywne kombinatory - najmniejsze możliwe elementy składowe. Mogą pomóc ci napisać prawdziwy program, o ile za ich pomocą możesz zbudować bardziej wyrafinowane kombinatory. Pomyśl o kombinatorach, takich jak S i K, jako o języku maszynowym hipotetycznego „komputera kombinacyjnego”. Rzeczywiste komputery oczywiście nie działają w ten sposób, więc w praktyce zwykle będziesz mieć operacje wyższego poziomu zaimplementowane za kulisami w inny sposób, ale podstawa koncepcyjna jest nadal użytecznym narzędziem do zrozumienia znaczenia tych wyższego poziomu operacje.

Druga definicja, którą podajesz, jest bardziej nieformalna i dotyczy korzystania z bardziej wyrafinowanych kombinatorów w postaci funkcji wyższego rzędu, które łączą inne funkcje na różne sposoby. Zauważ, że jeśli podstawowymi blokami budulcowymi są prymitywne kombinatory powyżej, wszystko zbudowane z nich jest funkcją wyższego rzędu, a także kombinatorem. Jednak w języku, w którym istnieją inne prymitywy, istnieje rozróżnienie między rzeczami, które są lub nie są funkcjami. W takim przypadku kombinator jest zwykle definiowany jako funkcja, która manipuluje innymi funkcjami w sposób ogólny, zamiast operować na jakichkolwiek innych funkcjach. funkcjonować rzeczy bezpośrednio.

Czy jest więcej przykładów kombinatorów, takich jak mapa, filtr?

Zbyt wiele, by je wymienić! Oba przekształcają funkcję opisującą zachowanie na pojedynczej wartości w funkcję opisującą zachowanie w całej kolekcji. Możesz również mieć funkcje, które przekształcają tylko inne funkcje, takie jak tworzenie ich od końca do końca lub dzielenie i ponowne łączenie argumentów. Możesz mieć kombinatory, które przekształcają operacje jednoetapowe w operacje rekurencyjne, które tworzą lub zużywają kolekcje. Albo naprawdę wiele innych rzeczy.

Jakie kombinatory często implementują języki programowania?

To będzie się znacznie różnić. Istnieje stosunkowo niewiele całkowicie ogólnych kombinatorów - głównie prymitywnych wymienionych powyżej - więc w większości przypadków kombinatory będą miały pewną świadomość używanych struktur danych (nawet jeśli te struktury danych i tak są zbudowane z innych kombinatorów), w których W przypadku, gdy zazwyczaj istnieje kilka „w pełni ogólnych” kombinatorów, a następnie różne wyspecjalizowane formy, które ktoś zdecydował się dostarczyć. Istnieje absurdalna liczba przypadków, w których (odpowiednio uogólnione wersje) mapowania, składania i rozwijania wystarczą, aby zrobić prawie wszystko, co chcesz.

W jaki sposób kombinatory mogą pomóc mi zaprojektować lepsze API?

Dokładnie tak, jak powiedziałeś, myśląc w kategoriach operacji wysokiego poziomu i sposobu, w jaki te współdziałają, a nie szczegółów niskiego poziomu.

Pomyśl o popularności pętli w stylu „for each” nad kolekcjami, które pozwalają abstrahować od szczegółów wyliczania kolekcji. W większości przypadków są to tylko operacje mapowania / zwijania, a tworząc kombinator (zamiast wbudowanej składni), możesz zrobić takie rzeczy, jak wziąć dwie istniejące pętle i bezpośrednio połączyć je na wiele sposobów - zagnieżdżać jedną w drugiej, rób jedno po drugim i tak dalej - po prostu stosując kombinator, zamiast żonglować całą masą kodu.

Jak zaprojektować skuteczne kombinatory?

Najpierw zastanów się, jakie operacje mają sens na danych używanych przez program. Następnie zastanów się, jak te operacje można sensownie łączyć na ogólne sposoby, a także jak można je podzielić na mniejsze części, które są ze sobą połączone. Najważniejsze to pracować z transformacjami i operacjami , a nie z działaniami bezpośrednimi . Kiedy masz funkcję, która po prostu wykonuje jakąś skomplikowaną funkcjonalność w nieprzejrzysty sposób i wypluwa tylko jakiś wstępnie przetrawiony wynik, niewiele możesz z tym zrobić. Ostateczne wyniki pozostaw kodowi, który używa kombinatorów - chcesz rzeczy, które prowadzą z punktu A do punktu B, a nie rzeczy, które mają być początkiem lub końcem procesu.

Jakie kombinatory są podobne do w języku niefunkcjonalnym (powiedzmy, Java) lub czego te języki używają zamiast kombinatorów?

Ahahahaha. Zabawne, o co powinieneś zapytać, ponieważ obiekty są przede wszystkim rzeczami wyższego rzędu - mają pewne dane, ale niosą też ze sobą wiele operacji, a sporo z tego, co składa się na dobry projekt OOP, sprowadza się do tego, że „obiekty powinny zwykle działają jak kombinatory, a nie struktury danych ”.

Prawdopodobnie najlepszą odpowiedzią tutaj jest to, że zamiast rzeczy podobnych do kombinatorów, używają klas z dużą ilością metod pobierających i ustawiających lub pól publicznych oraz logiki, która polega głównie na wykonywaniu nieprzezroczystej, predefiniowanej akcji.

CA McCann
źródło
Świetna odpowiedź! Zobaczmy, czy to rozumiem - kombinatory nie są czymś wyjątkowym, a raczej integralną częścią budowania systemu oprogramowania, który można konserwować? Wciąż próbuję przetrawić oświadczenie Hughesa „fragmenty programu” w kontekście twojego postu.
Matt Fenwick,
@Matt Fenwick: Jestem prawie pewien, że używa on po prostu „fragmentów programu” na oznaczenie tego rodzaju transformacji / operacji, o których mówię, szczególnie jeśli mowa o „strzałkach”, które jeszcze mocniej podkreślają to podejście. Nie powiedziałbym również, że chodzi o budowanie systemów, które można konserwować , a dokładniej o budowaniu systemów, które są wysoce modułowe i oddzielone w określony sposób, z korzyściami, jakie się z tym wiążą.
CA McCann
Czy znasz jakieś dobre źródła do czytania na temat praktycznego wykorzystania kombinatorów? Wielkie dzięki!
Matt Fenwick
@Matt Fenwick: Nie mam nic szczególnego na głowie, przepraszam. Jednak wydaje się to być naturalnym podejściem do programów napisanych w bardzo funkcjonalnym stylu, więc wystarczy spędzić trochę czasu z językami, które silnie do tego zachęcają (np. Haskell lub Clojure) i przyjrzeć się, jak czysty i idiomatyczny kod jest napisany w tym języku , to całkiem niezły sposób na wyczucie stylu.
CA McCann