Jaki problem rozwiązują algebraiczne typy danych?

18

Uczciwe ostrzeżenie, jestem nowy w programowaniu funkcjonalnym, więc mogę mieć wiele złych założeń.

Uczyłem się o typach algebraicznych. Wydaje się, że ma je wiele języków funkcjonalnych i są one dość przydatne w połączeniu z dopasowaniem wzorców. Jaki problem rozwiązują? Mogę zaimplementować pozornie (w pewnym sensie) typ algebraiczny w języku C # w następujący sposób:

public abstract class Option { }
public class None : Option { }
public class Some<T> : Option
{
    public T Value { get; set; }
}

var result = GetSomeValue();
if(result is None)
{
}
else
{
}

Ale myślę, że większość zgodziłaby się, że jest to draństwo programowania obiektowego i nigdy nie powinieneś tego robić. Czy więc programowanie funkcjonalne po prostu dodaje czystszą składnię, która sprawia, że ​​ten styl programowania wydaje się mniej obrzydliwy? Czego jeszcze mi brakuje?

ConditionRacer
źródło
6
Programowanie funkcjonalne to inny paradygmat niż programowanie obiektowe.
Basile Starynkevitch
@BasileStarynkevitch Zdaję sobie sprawę, ale istnieją języki takie jak F #, które są trochę z obu. Pytanie dotyczy nie tyle języków funkcjonalnych, co więcej, jakie problemy algebraiczne rozwiązują.
ConditionRacer
7
Co się stanie, gdy zdefiniuję class ThirdOption : Option{}i podam ci miejsce, w new ThirdOption()którym się spodziewałeś Somelub None?
amon
1
Języki @amon, które mają typy sum, ogólnie mają sposoby, aby to zabronić. Na przykład Haskell definiuje data Maybe a = Just a | Nothing(odpowiednik data Option a = Some a | Nonew twoim przykładzie): nie można dodać trzeciego przypadku post-hoc. Chociaż możesz w pewien sposób emulować typy sum w języku C # w sposób pokazany przez Ciebie, nie jest to najładniejsze.
Martijn
1
Myślę, że mniej „jaki problem rozwiązują ADT”, a bardziej „ADT to inny sposób podejścia”.
MathematicalOrchid

Odpowiedzi:

44

Klasy z interfejsami i dziedziczeniem prezentują otwarty świat: każdy może dodać nowy rodzaj danych. Dla danego interfejsu mogą istnieć klasy wdrażające go na całym świecie, w różnych plikach, w różnych projektach, w różnych firmach. Ułatwiają dodawanie przypadków do struktur danych, ale ponieważ implementacje interfejsu są zdecentralizowane, trudno jest dodać nową metodę do interfejsu. Kiedy interfejs jest publiczny, jest zasadniczo zawieszony. Nikt nie zna wszystkich możliwych implementacji.

Algebraiczne typy danych są dualne, są zamknięte . Wszystkie przypadki danych są wymienione w jednym miejscu, a operacje nie tylko mogą wyczerpująco wymieniać warianty, ale są do tego zachęcane . W związku z tym napisanie nowej funkcji działającej na algebraicznym typie danych jest banalne: po prostu napisz tę cholerną funkcję. W zamian dodawanie nowych przypadków jest skomplikowane, ponieważ musisz przejrzeć w zasadzie całą bazę kodu i rozszerzyć każdą match. Podobnie jak w przypadku interfejsów, w standardowej bibliotece Rust dodanie nowego wariantu jest przełomową zmianą (dla typów publicznych).

Są to dwie strony problemu z wyrażeniem . Algebraiczne typy danych są dla nich niepełnym rozwiązaniem, ale tak samo jest z OOP. Obie mają zalety w zależności od liczby przypadków danych, częstotliwości ich zmieniania oraz częstotliwości rozszerzania lub zmieniania operacji. (Dlatego wiele współczesnych języków zapewnia oba lub coś podobnego, albo wybiera bardziej wydajne i bardziej skomplikowane mechanizmy, które próbują objąć oba podejścia.)


źródło
Czy pojawia się błąd kompilatora, jeśli nie uda się zaktualizować dopasowania, czy jest to możliwe tylko w czasie wykonywania?
Ian
6
@Ian Większość funkcjonalnych języków jest wpisywana statycznie i sprawdza kompletność dopasowania wzorca. Jeśli jednak istnieje wzorzec „złap wszystko”, kompilator jest szczęśliwy, nawet jeśli funkcja musiałaby poradzić sobie z nowym przypadkiem, aby wykonać swoją pracę. Ponadto musisz ponownie skompilować cały zależny kod, nie możesz skompilować tylko jednej biblioteki i ponownie połączyć go z już utworzoną aplikacją.
Ponadto statyczne sprawdzanie, czy wzór jest wyczerpujący, jest ogólnie drogie. W najlepszym wypadku rozwiązuje problem SAT, aw najgorszym język pozwala na dowolne predykaty, co czyni to nierozstrzygalnym.
usr
@usr Brak języka Jestem świadomy prób znalezienia idealnego rozwiązania, albo kompilator rozumie, że jest wyczerpujący, albo jesteś zmuszony do dodania całościowego przypadku awarii i nagrania. Nie znam jednak związku z SAT, czy masz link do obniżki? Niezależnie od tego, w przypadku rzeczywistego kodu napisanego w prawdziwych programach sprawdzanie wyczerpania jest kroplą w parze.
Wyobraź sobie, że pasujesz na N booleanach. Następnie dodajesz klauzule dopasowania, takie jak (a, b, _, d, ...). Sprawa typu catch-all to wtedy! Klauzula 1 i&! Klauzula 2 i& .... To dla mnie wygląda na SAT.
usr
12

Czy więc programowanie funkcjonalne po prostu dodaje czystszą składnię, która sprawia, że ​​ten styl programowania wydaje się mniej obrzydliwy?

To może uproszczenie, ale tak.

Czego jeszcze mi brakuje?

Wyjaśnijmy, jakie są typy danych algebraicznych (podsumowując ten drobny link z Learn you as Haskell):

  • Typ sumy, który mówi „ta wartość może być A lub B”.
  • Typ produktu, który mówi „ta wartość to zarówno A, jak i B”.

twój przykład naprawdę działa tylko z pierwszym.

Być może brakuje ci dwóch podstawowych operacji, a języki funkcyjne pozwalają zbudować wszystko inne. C # ma na sobie struktury, klasy, wyliczenia, generyczne i stosy reguł rządzących tym, jak te rzeczy się zachowują.

W połączeniu z pewną składnią, która może pomóc, języki funkcjonalne mogą rozkładać operacje do tych dwóch ścieżek, zapewniając czyste, proste i eleganckie podejście do typów.

Jaki problem rozwiązują algebraiczne typy danych?

Rozwiązują ten sam problem, co każdy inny system typów: „jakie wartości można tutaj zastosować zgodnie z prawem?” - po prostu mają inne podejście do tego.

Telastyn
źródło
4
Twoje ostatnie zdanie jest jak powiedzenie komuś, że „statki rozwiązują ten sam problem co samoloty: transport - po prostu podchodzą do niego inaczej”. Jest to całkowicie poprawne stwierdzenie, a także całkiem bezużyteczne.
Mehrdad
@mehrdad - Myślę, że to trochę przesadzam.
Telastyn
1
Bez wątpienia dobrze rozumiesz algebraiczne typy danych, ale Twoja wypunktowana lista („Typ sumy to ...” i „Typ produktu to ...”) wygląda bardziej jak opis typów złączy i skrzyżowań, które nie są zupełnie to samo, co suma i rodzaje produktów.
pyon
6

Może cię zaskoczyć informacja, że ​​dopasowanie wzorca nie jest uważane za najbardziej idiomatyczny sposób pracy z Opcjami. Więcej informacji na ten temat można znaleźć w dokumentacji Opcji Scali . Nie jestem pewien, dlaczego tak wiele samouczków FP zachęca do takiego używania.

W większości brakuje Ci całej gamy funkcji, które ułatwiają pracę z Opcjami. Rozważ główny przykład z dokumentów Scali:

val name: Option[String] = request getParameter "name"
val upper = name map { _.trim } filter { _.length != 0 } map { _.toUpperCase }
println(upper getOrElse "")

Zauważ, jak mapi filterpozwól na łączenie operacji na Opcjach, bez konieczności sprawdzania w każdym punkcie, czy masz, Noneczy nie. Następnie na końcu służy getOrElsedo określenia wartości domyślnej. W żadnym momencie nie robisz czegoś „obrzydliwego”, takiego jak sprawdzanie typów. Wszelkie nieuniknione sprawdzanie typu odbywa się wewnętrznie w bibliotece. Haskell ma własny zestaw funkcji analitycznych, nie wspominając o dużym zestawie funkcji, które będą działać na dowolnej monadzie lub funktorze.

Inne typy danych algebraicznych mają swoje idiomatyczne sposoby pracy z nimi, a dopasowanie wzorca jest niskie na biegunie totemu w większości przypadków. Podobnie podczas tworzenia własnych typów oczekuje się, że zapewnią podobne funkcje do pracy z nimi.

Karl Bielefeldt
źródło