Haskell | ||
![]() | ||
Dato for første versjon | 1990 | |
---|---|---|
Paradigmer | funksjonell | |
Forfatter | Haskell komité | |
Utviklere | Haskell samfunn | |
Skrive | Sterk , statisk | |
Dialekter | Helium, O'Haskell, Mal Haskell, PolyP | |
Påvirket av | Lisp and Scheme , ISWIM , FP , APL , Hope , SISAL , Miranda , ML , Lazy ML , Orwell , Alfl , Id , Ponder | |
Implementeringer | GHC , Klemmer , Yhc | |
Operativsystem | Multiplatform | |
Nettsted | https://www.haskell.org | |
Filutvidelse | hs og lhs | |
Haskell er et funksjonelt programmeringsspråk basert på lambda-calculus og kombinatorisk logikk . Navnet kommer fra matematikeren og logikeren Haskell Curry . Den ble opprettet i 1990 av en komité av språkteoriforskere som er interessert i funksjonelle språk og lat evaluering . Den siste standarden er Haskell 2010 : det er en minimal og bærbar versjon av språket designet for pedagogiske og praktiske formål, av hensyn til interoperabilitet mellom språkimplementeringer og som grunnlag for fremtidige utvidelser. Språket fortsetter å utvikle seg i 2020, hovedsakelig med GHC , og utgjør dermed en de facto standard med mange utvidelser.
Mirandas utgivelse i 1985 utløste en fornyet interesse for dovne evalueringsfunksjonelle språk og førte til en eksplosjon i antall slike eksperimentelle språk, slik at i 1987 var mer enn et dusin tilgjengelig. Miranda var uten tvil den mest populære, men den lukkede proprietære modellen oppmuntret ikke til bidrag og på konferansen Functional Programming Languages and Computer Architecture (FPCA '87) i Portland , Oregon , konkluderte et møte med fremtredende forskere i feltet at det ville være ønskelig å etablere en åpen standard som kan tjene som et felles grunnlag for fremtidig forskning på funksjonelle språk . For dette formålet dannet de en komité hvis oppgave ville være å samle styrkene til datidens prototyper.
Komiteens arbeid fortsatte fra møte til møte og kulminerte i 1990 med definisjonen av Haskell 1.0, etterfulgt av ulike revisjoner for versjon 1.1, 1.2, 1.3 og 1.4.
Haskell 98Haskell 98- rapporten etablerer en varig standard som alle etterfølgende implementeringer er basert på. En revidert versjon vises ijanuar 2003.
Haskell 2010Prosessen med å revidere Haskell-standarden, kalt Haskell '(uttales " Haskell Prime ") begynte i 2006. Opprinnelig utført med sikte på å publisere en ny versjon av Haskell-standarden, anstrengte innsatsen for å bli på plass på en bærekraftig måte og har nå satt seg et mer begrenset mål: å publisere regelmessig (teoretisk en gang i året) en revisjon av 1998-rapporten som inneholder noen nye funksjoner introdusert siden av GHC og utvilsomt akseptert og brukt av samfunnet. Haskell 2010 la dermed til en definisjon av Haskells grensesnittmekanisme med andre språk (FFI: interface for utenlandske funksjoner ) og fjernet "n + k" -mønstrene fra språket (som tillot skriving :) decrement (n+1) = n. Det formaliserte også en mekanisme for å spesifisere hvilken standard man ønsker å respektere i en gitt kildefil, samt eventuelle utvidelser, som bekrefter den ganske modulære naturen til Haskell brukt i praksis.
ForskningsversjonerFra og med 2012 er Haskell trolig det funksjonelle språket som det er forsket på mest forskning på. Flere varianter er utviklet. Parallelliserte versjoner laget ved Laboratory for Computer Science ved Massachusetts Institute of Technology (MIT) og ved University of Glasgow har begge blitt kalt Parallel Haskell. Mer parallelliserte og distribuerte versjoner kalles Distribuert Haskell (tidligere Goffin) og Eden, det er også et forsøk på å bruke Haskell i cloud computing kalt Cloud Haskell. En spekulativ kjøretidsversjon , Eager Haskell og flere objektorienterte versjoner, Haskell ++, O'Haskell og Mondrian har dukket opp. Disse forskjellige forskningsversjonene var ganske ofte basert på GHC og satte ofte sitt preg på denne kompilatoren da eksperimentering viste seg å være vellykket, og inspirerte dermed til den nåværende støtten for tråder og ulike former for kodeparallellisering.
Det mest interessante funksjonene i Haskell er støtte for rekursive funksjoner , typen slutning , forståelse lister , lat evaluering, og uendelig datastrukturer, godt eksempel på noe som er datatypen strømmen . Disse funksjonene, spesielt når de kombineres, gjør det lettere å skrive og bruke funksjoner og manipulere data. Typesystemet, som har vært gjenstand for mye forskning, er også en av de mest uttrykksfulle og en av de mest tilbøyelige til å implementere, på en statisk måte , mange begrensninger som vanligvis blir verifisert ved kjøretid. Haskell utmerker seg også ved bruk av monader for inngang / utgang og for unntakshåndtering, nødvendig av en av de viktigste spesifikasjonene i språket, nemlig at Haskell er et rent funksjonelt språk, noe som betyr at iboende ingen bivirkninger er tillatt , verken innganger / utganger, eller variable oppgaver eller unntak. De fleste funksjonelle språk oppmuntrer denne stilen, men Haskell pålegger den i en hvilken som helst kode som ikke eksplisitt indikerer ved sin type at den innrømmer bivirkninger og som takket være denne mekanismen forhindrer og begrenser farene.
Den klassiske definisjonen av faktorfunksjonen :
fac n = if n > 0 then n * fac(n - 1) else 1Den elegante definisjonen av faktorfunksjonen (som bruker Haskell-funksjonen productog listenotasjonen):
fac n = product [1..n]Det er også mulig å definere en liste over alle faktorene:
facs = 1: zipWith (*) facs [1..]Den forrige verdien er en uendelig liste, noe som er fullt mulig med lat evaluering . Takket være denne listen kan vi implementere facpå denne måten:
fac n = facs !! n( !!er en operatør som returnerer det niende elementet i en liste).
Som facser lat evaluert i fac, fac nforårsaker et kall til at bare de første vilkårene blir evaluert facs. Merk at verdien av hvert element av facsblir evaluert bare en gang.
En naiv implementering av funksjonen som returnerer det niende tallet i Fibonacci-sekvensen :
fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)En funksjon som returnerer den uendelige listen over Fibonacci-tall, også takket være lat evaluering:
fibs = 0 : 1 : (zipWith (+) fibs (tail fibs)) fib n = fibs !! nI motsetning til den naive versjonen, er kompleksiteten i en samtale til fiblineær, og dette takket være memoarisering .
Faktisk, i den forrige versjonen ble verdiene av fib beregnet for hver forespørsel. Dermed fib 4forårsaker en samtale en samtale fib 3og en samtale til den fib 2som kaller seg igjen fib 2, to ganger fib 1og en gang fib 0, etc.
På den annen side, når det gjelder den uendelige listen, fibberegnes hver verdi av bare en gang og lagres deretter i minnet.
Takket være mekanismen for lat evaluering er det også mulig å definere hele (og uendelige) listen over primtall :
primes = remDivs [2..] where remDivs (x:xs) = x: remDivs [n | n <- xs, (mod n x) /= 0]Denne algoritmen er imidlertid veldig ineffektiv, og en implementering av Eratosthenes sil gir mye bedre ytelse.
For å gjøre søket mer effektivt, kan vi bekrefte at tallet hvis primality er testet, ikke kan deles med noen av primtallene mindre enn kvadratroten. En implementering i Haskell kan være:
prem = 2:[a | a <- [3,5..], (all (/= 0) (map (\x -> mod a x) (takeWhile (<= truncate(sqrt (fromIntegral a::Float))) prem))) ]Den raske sorteringsalgoritmen kan skrives i Haskell ved å manipulere lister:
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]Eller
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)På grunn av listekopier og sammenkoblinger kan denne koden være treg, avhengig av kompilatoren. En forbedring er å utføre sammenligningstesten bare en gang:
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)Imidlertid har disse naive implementeringene av rask sort ulempen med å være av en kompleksitet (O (N²)) når det gjelder en sortert liste.
Følgende implementeringer er alle kompatible (eller nesten kompatible) med Haskell 98-standarden, og distribueres under gratis lisenser. Alle Haskell-implementeringer er for øyeblikket gratis programvare .
Fordi ikke-prosessuelt kan Haskell redusere feilsøkingsbehovet betydelig: utsagn (et Haskell-program inkluderer kun utsagn) som uavhengige av hverandre, trenger ikke programmereren å ta seg av noen flomkontroll eller til og med sekvensen eller konteksten av utsagnene; Det kommer derfor ikke som noen overraskelse at prosjekter blir utført i Haskell før de er tilgjengelige på andre språk. De mest kjente eksemplene er: