Naar wat gespeeld the hebben met de repl tool van Haskell, is het tijd om in een IDE te gaan werken. Omdat ik voor veel dingen Visual Studio Code gebruik (waaronder het schrijven van deze blog), ga ik Haskell projecten ook in Visual Studio Code maken. Hiervoor gebruik ik de plugin Haskero.
Omdat ik veel gezien heb van lijsten en om te kijken hoe recursion werk, ga ik vandaag een merge sort implementatie maken in Haskell.
Haskell applicaties gebruiken een .hs extentie voor hun source files. Deze source files kunnen simpele functies, maar ook hele applicaties bevatten. Wat opvalt, is dat de repl tool van Haskell maar een subset van de taal bevat. Zo is het in de repl tool bijvoorbeeld mogelijk om meerdere keren een waarde aan dezelfde variabele toe te kennen. Dit is verboden wanneer dit in een source file gebruikt wordt. De reden hiervoor is dat Haskell geen instanties kent. Dit lijkt op het eerste oogopslag een restrictie, maar dit zorgt er aan de andere kant voor dat functies puur blijven en makkelijk te testen zijn. Ook zal dit concurrency bevorderen, aangezien er geen shared state is. Andere verschillen tussen de repl tool en source files zullen later in deze blog ongetwijfeld aan bod komen.
Om deze source files vervolgens te runnen kan ik het command runghc xyz.hs gebruiken, waarbij xyz.hs de betreffende file is. Dit zorgt ervoor dat de main functie aangeroepen wordt. Ook is het mogelijk om een haskell file in de repl omgeving van haskell te laden: ghci xyz.hs. Vervolgens kunnen de ge-exposed functies gebruikt worden.
Een haskell applicatie bestaat uit modules. Een module geeft aan in welke namespace de code zit. Modules kunnen weer op andere plekken gebruikt worden. Voor iedere module kan er gekozen worden welke functies bereikbaar zijn van buitenaf. Een module definitie ziet er als volgt uit module Foo(doBar) where, waarbij Foo de modulenaam is en doBar de functie de ge-exposed wordt.
Het importeren van andere modules gebeurt door import Foo(doBar). Dit importeerd de functie doBar uit de module Foo. Ook kan het geschreven worden als import Foo. Dit importeert alle functies uit de module Foo.
Voor de merge sort implementatie ben ik begonnen met het aanmaken van een .hs file met hierin de MergeSort module. Om te testen of dit werkt heb ik een sort functie gemaakt die simpelweg een lijst teruggeeft.
module MergeSort(sort) where
sort :: [Int] -> [Int]
sort items =
items
Omdat de sort functie zichzelf steeds aanroept tot het lijstje leeg is of 1 element bevat, heb ik hier base cases voor toegevoegd. Wanneer de lijst leeg is, geef ik een lege lijst terug en wanneer er 1 item in de lijst zit, geef ik een lijst met dit item terug.
sort :: [Int] -> [Int]
sort [] = []
sort [singleItem] = [singleItem]
sort items =
items
Vervolgens hebben we een functie nodig die de lijst op kan delen in een linker en een rechter kant. Hiervoor heb ik de split functie gedefinieerd. Deze geeft een tuple terug met hierin de linker -en rechterhelft. De split functie maakt gebruik van de take functie. Deze functie pakt een x-aantal elementen uit de gegeven lijst. De drop functie verwijdert een x-aantal functies. Hoeveel elementen er gedropt moeten worden, wordt bepaald door de lengte van de lijst (lenght) te delen door 2 met behulp van de div functie.
split :: [Int] -> ([Int], [Int])
split items =
( take (div (length items) 2) items
, drop (div (length items) 2) items
)
Nu we kunnen splitten, moeten we ook kunnen mergen. De merge functie heb ik recursief gedefinieerd. Hierbij heb ik gebruik gemaakt van guards, pattern matching en de : operator om steeds het eerste element uit de linker en rechter lijst te halen.
merge :: [Int] -> [Int] -> [Int]
merge [] right = right
merge left [] = left
merge (lFirst:lRest) (rFirst:rRest)
| lFirst <= rFirst = lFirst:(merge lRest (rFirst:rRest))
| otherwise = rFirst:(merge (lFirst:lRest) rRest)
Nu we alle functies hebben, wordt het tijd om alles aan de sort functie te knopen. Ook is dit een goed moment om de merge sort functie generiek te maken met behulp van het type Ord. Ord is het basistype voor alle orderbare datatypes (zoals String, Int, etc.).
De totale uitwerking ziet er als volgt uit:
module MergeSort(sort) where
sort :: Ord a => [a] -> [a]
sort [] = []
sort [singleItem] = [singleItem]
sort items =
let
(left, right) =
split items
in
merge (sort left) (sort right)
merge :: Ord a => [a] -> [a] -> [a]
merge [] right = right
merge left [] = left
merge (lFirst : lRest) (rFirst : rRest)
| lFirst <= rFirst = lFirst : (merge lRest (rFirst : rRest))
| otherwise = rFirst : (merge (lFirst : lRest) rRest)
split :: Ord a => [a] -> ([a], [a])
split items =
( take (div (length items) 2) items
, drop (div (length items) 2) items
)
Het command ghc xyz.hs wordt gebruikt om een haskell file te compileren. Hierbij wordt een xyz.hi en een xyz.o file gegenereerd.
.hi files bevatten interface informatie voor de betreffende module. Deze interface informatie wordt gebruikt voor andere modules die de module xyz importeren. Op deze manier weten deze modules wat de modulenaam is en welke functies deze module bevat..o files bevatten de gecompileerde module zelf.