Haskell | ||
Data pierwszej wersji | 1990 | |
---|---|---|
Paradygmaty | funkcjonalny | |
Autor | Komitet Haskella | |
Deweloperzy | Społeczność Haskella | |
Pisanie na maszynie | Mocny , statyczny | |
Dialekty | Hel, O'Haskell, Szablon Haskell, PolyP | |
Wpływem | Lisp i Schemat , ISWIM , FP , APL , Hope , SISAL , Miranda , ML , Lazy ML , Orwell , Alfl , Id , Ponder | |
Realizacje | GHC , Uściski , Yhc | |
System operacyjny | Wieloplatformowy | |
Stronie internetowej | https://www.haskell.org | |
Rozszerzenie pliku | hs i lhs | |
Haskell to funkcjonalny język programowania oparty na rachunku lambda i logice kombinatorycznej . Jego nazwa pochodzi od matematyka i logika Haskella Curry'ego . Został stworzony w 1990 roku przez komitet badaczy teorii języka zainteresowanych językami funkcjonalnymi i leniwą oceną . Najnowszym standardem jest Haskell 2010 : jest to minimalna i przenośna wersja języka zaprojektowana do celów edukacyjnych i praktycznych, ze względu na interoperacyjność między implementacjami języka oraz jako podstawa dla przyszłych rozszerzeń. Język nadal ewoluuje w 2020 roku, głównie z GHC , stanowiąc tym samym de facto standard z wieloma rozszerzeniami.
Mirandy uwolnienie w 1985 roku wywołał ponowne zainteresowanie w ewaluacji leniwy języków funkcyjnych i doprowadził do eksplozji liczby tych językach doświadczalnych, tak że przez 1987 więcej niż tuzin były dostępne. Miranda był zdecydowanie najbardziej popularne, ale jego zamknięta zastrzeżony wzór nie zachęcają składek i na Programowanie funkcyjne Języki i Computer Architecture (FPCA '87) konferencji w Portland , Oregon , spotkanie wybitnych naukowców w dziedzinie stwierdziła, że byłoby pożądane byłoby ustanowienie otwartego standardu, który mógłby służyć jako wspólna podstawa dla przyszłych badań nad językami funkcjonalnymi . W tym celu utworzyli komitet, którego zadaniem miało być połączenie sił ówczesnych prototypów.
Prace komitetu trwały od spotkań do spotkań i zakończyły się w 1990 roku definicją Haskella 1.0, po której nastąpiły różne poprawki dla wersji 1.1, 1.2, 1.3 i 1.4.
Haskella 98Raport Haskella 98 ustanawia trwały standard, na którym opierają się wszystkie kolejne implementacje. Zmieniona wersja pojawia się wstyczeń 2003.
Haskella 2010Proces rewizji standardu Haskell, nazwanego Haskell '(czyt. " Haskell Prime ") rozpoczął się w 2006 roku. Początkowo podjęty w celu opublikowania nowej wersji standardu Haskella, starano się wprowadzić w zrównoważony sposób i postawił sobie teraz bardziej ograniczony cel: regularne publikowanie (teoretycznie raz w roku) rewizji raportu z 1998 roku, uwzględniającego pewne nowe funkcje wprowadzone od tego czasu przez GHC i bezsprzecznie akceptowane i wykorzystywane przez społeczność. Haskell 2010 dodał więc definicję mechanizmu interfejsu Haskella z innymi językami (FFI: interfejs funkcji obcych ) i usunął wzorce „n+k” z języka (co pozwalało na pisanie:) decrement (n+1) = n. Sformalizował również mechanizm określania, jaki standard chcemy respektować w danym pliku źródłowym, a także wszelkie rozszerzenia, potwierdzając dość modułową naturę Haskella stosowanego w praktyce.
Wersje badawczeOd 2012 r. Haskell jest prawdopodobnie językiem funkcjonalnym, nad którym podjęto najwięcej badań. Opracowano kilka wariantów. Wersje zrównoleglone wykonane w Laboratorium Informatyki w Massachusetts Institute of Technology (MIT) oraz na Uniwersytecie w Glasgow zostały nazwane Parallel Haskell. Bardziej zrównoleglone i rozproszone wersje nazywają się Distributed Haskell (dawniej Goffin) i Eden, istnieje również próba wykorzystania Haskella w chmurze obliczeniowej o nazwie Cloud Haskell. Pojawiła się spekulacyjna wersja środowiska uruchomieniowego Eager Haskell oraz kilka wersji obiektowych Haskell ++, O'Haskell i Mondrian. Te różne wersje badawcze były dość często oparte na GHC i często pozostawiały ślad na tym kompilatorze, gdy eksperymenty okazały się skuteczne, inspirując w ten sposób obecne wsparcie dla wątków i różnych form zrównoleglania kodu.
Najciekawsze cechy Haskella to obsługa funkcji rekurencyjnych , wnioskowanie o typie , listy ze zrozumieniem , leniwa ocena i nieskończone struktury danych , czego najlepszym przykładem jest typ danych stream . Te cechy, zwłaszcza w połączeniu, ułatwiają pisanie i używanie funkcji oraz manipulowanie danymi. System typów, który był przedmiotem wielu badań, jest również jednym z najbardziej wyrazistych i jednym z najłatwiejszych do implementacji, w sposób statyczny , wielu ograniczeń, które są zwykle weryfikowane w czasie wykonywania. Haskell wyróżnia się również wykorzystaniem monad do obsługi wejścia/wyjścia oraz obsługi wyjątków, wymuszonych jedną z najważniejszych cech charakterystycznych języka, a mianowicie tym, że Haskell jest językiem czysto funkcjonalnym, co oznacza, że z natury nie są dozwolone żadne skutki uboczne , ani wejścia/wyjścia, ani przypisania zmiennych, ani wyjątki. Większość języków funkcjonalnych zachęca do tego stylu, ale Haskell narzuca go w każdym kodzie, który nie wskazuje jednoznacznie swoim typem, że dopuszcza skutki uboczne i który dzięki temu mechanizmowi zapobiega i ogranicza jego niebezpieczeństwa.
Klasyczna definicja funkcji silni :
fac n = if n > 0 then n * fac(n - 1) else 1Elegancka definicja funkcji silni (która wykorzystuje funkcję Haskella producti notację listową):
fac n = product [1..n]Możliwe jest również zdefiniowanie listy wszystkich silni:
facs = 1: zipWith (*) facs [1..]Poprzednia wartość jest nieskończoną listą, co jest całkiem możliwe przy leniwej ocenie . Dzięki tej liście możemy zrealizować facw ten sposób:
fac n = facs !! n( !!jest operatorem zwracającym n-ty element listy).
Jak facsjest leniwie oceniane w fac, wywołanie to fac npowoduje, że oceniane jest tylko pierwsze n warunków facs. Zauważ, że wartość każdego elementu facsjest oceniana tylko raz.
Naiwna implementacja funkcji zwracającej n-tą liczbę ciągu Fibonacciego :
fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)Funkcja zwracająca nieskończoną listę liczb Fibonacciego, również dzięki leniwej ocenie:
fibs = 0 : 1 : (zipWith (+) fibs (tail fibs)) fib n = fibs !! nW przeciwieństwie do wersji naiwnej złożoność wywołania fibjest liniowa, a to dzięki memoisation .
Rzeczywiście, w poprzedniej wersji wartości fib były obliczane dla każdego żądania. W ten sposób wywołanie fib 4powoduje wywołanie fib 3i fib 2ponowne wywołanie tego wywołania fib 2, dwa razy fib 1i jeden raz fib 0, itd.
Z kolei w przypadku listy nieskończonej każda wartość fibjest obliczana tylko raz, a następnie zapisywana w pamięci.
Dzięki mechanizmowi leniwego obliczania możliwe jest również zdefiniowanie całej (i nieskończonej) listy liczb pierwszych :
primes = remDivs [2..] where remDivs (x:xs) = x: remDivs [n | n <- xs, (mod n x) /= 0]Algorytm ten jest jednak bardzo nieefektywny, a zastosowanie sita Eratostenesa pozwala na znacznie lepszą wydajność.
Aby wyszukiwanie było bardziej wydajne, możemy sprawdzić, czy liczba, której pierwszorzędność jest testowana, nie jest podzielna przez żadną z liczb pierwszych mniejszych od jej pierwiastka kwadratowego. Implementacja w Haskell może być:
prem = 2:[a | a <- [3,5..], (all (/= 0) (map (\x -> mod a x) (takeWhile (<= truncate(sqrt (fromIntegral a::Float))) prem))) ]Algorytm szybkiego sortowania można napisać w Haskell, manipulując listami:
qsort [] = [] qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x where elts_lt_x = [y | y <- xs, y < x] elts_greq_x = [y | y <- xs, y >= x]Lub
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)Ze względu na kopie list i konkatenacje ten kod może być powolny, w zależności od kompilatora. Udoskonalenie polega na wykonaniu testu porównawczego tylko raz:
qSort :: (Ord a) => [a] -> [a] qSort [] = [] qSort (mid:xs) = qSort inf ++eg++ qSort sup where (inf, eg, sup) = sep xs ([],[mid],[]) where sep [] tuple = tuple sep (y:ys) (i,e,s) | (y < mid) = sep ys (y:i,e,s) | (y == mid) = sep ys (i,y:e,s) | otherwise = sep ys (i,e,y:s)Jednak te naiwne implementacje szybkiego sortowania mają tę wadę, że są złożonością (O (N²)) w przypadku posortowanej listy.
Wszystkie poniższe implementacje są kompatybilne (lub prawie kompatybilne) ze standardem Haskell 98 i są rozpowszechniane na wolnych licencjach. Wszystkie implementacje Haskella są obecnie wolnym oprogramowaniem .
Ponieważ nie jest to procedura proceduralna, Haskell może znacznie ograniczyć potrzeby debugowania: instrukcje (program Haskella zawiera tylko instrukcje) są od siebie niezależne, programista nie musi zajmować się żadną kontrolą zalania, ani nawet kolejnością lub kontekstem instrukcji; Nic więc dziwnego, że projekty są realizowane w Haskell, zanim będą dostępne w innych językach. Najbardziej znane przykłady to: