Floyds triangel i Haskell
Hej. Jag är inaktiv för det händer mycket i mitt liv. Jag har svårt för att prioritera min tid och hur jag än gör blir det fel. Vänta inte mycket från mitt håll här. Jag jobbar av och till på en bok. Men vänta inte för mycket där heller. Jag behövde bara skriva lite nu.
Haskell är väldigt coolt.
Det dök i IRC upp en uppgift som lät som om den egentligen bara går att lösa ordentligt med Haskell. Den är som beskrivet härnäst.
Be användaren om ett tal $$n$$. Skriv sedan ut $$n$$ grupper med siffror, där varje grupp innehåller en siffra mer än gruppen innan. Med ett konkret exempel för $$n = 5$$ blir det till exempel
[1] [2,3] [4,5,6] [7,8,9,10] [11,12,13,14,15]
Först gruppen innehåller bara en siffra – 1. Nästa grupp innehåller de två påföljande siffrorna, 2 och 3. Gruppen efter det innehåller de tre nästa siffrorna, 4, 5 och 6. Så fortsätter det med så många grupper som användaren ber om.
Denna gruppering av siffror kallas Floyds triangel. Exemplet ovan är Floyds triangel med fem nivåer.
Denna uppgift är än så länge ganska enkel om man löser den på enklaste möjliga sätt: Du behöver bara skriva ut en siffra till skärmen skärmen i taget tills du har skrivit ut lika många som gruppens nummer, och sen börjar du på nästa grupp. Du kan lösa det med två forloopar eller en forloop och en ifsats. Men! Detta var inte hela uppgiften som den var presenterad för mig.
Uppgiften ska också lösas på ett så matematiskt sätt som möjligt.
Även om "matematiskt sätt" är en ganska luddig term så innebär det några få saker, bland annat att
Det ska finnas en funktion som ger Floyds triangel med önskat antal nivåer; det är inte okej att skriva ut varje siffra samtidigt som man plockar fram den, vilket innebär att koden som skriver ut triangeln ska vara skiljd från koden som skapar den,
Det ska inte gå att "misslyckas" med att använda koden – funktionen som genererar triangeln ska inte bero på något som kan göra att den genererar fel, och
Triangeln ska helst vara oändligt stor.
Det sista innebär i praktiken att man ska ha en variabel eller motsvarande som innehåller hela triangeln, och sen kan man hämta ut så mycket av den som man vill. Hela triangeln är naturligtvis triangeln som den ser ut när $$n$$ är oändligt stort, vilket gör uppgiften lite intressant. Men vi kommer till det. Här är lösningen, härligt kort, så dissekerar vi den alldeles strax!
module Main where import Data.List (unfoldr) floydTriangle = unfoldr (Just . nextFloyd) (1,1) where nextFloyd (number, quantity) = (take quantity [number..], (number+quantity, quantity+1)) main = do putStr "Depth? " depth <- fmap read getLine let finiteTriangle = take depth floydTriangle mapM_ (putStrLn . show) finiteTriangle
Vi börjar i toppen. De två första raderna är så uppenbara så jag vill ha de ur vägen.
module Main where import Data.List (unfoldr)
Dessa två rader deklarerar att det är ett program (module Main where) samt laddar in en funktion ur standardbiblioteket för listhantering (import Data.List (unfoldr).) Vi använder bara en funktion ur listbiblioteket (unfoldr), så det kändes lika bra att ladda in bara den. Nu tänkte jag hoppa över en variabel, och går direkt på main-funktionen!
main = do putStr "Depth? " depth <- fmap read getLine let finiteTriangle = take depth floydTriangle mapM_ (putStrLn . show) finiteTriangle
Mainfunktionen består i princip av tre delar:
Be användaren om antalet grupper ur Floyds triangel den vill ha,
Plocka ut det antalet grupper ur den oändligt stora triangeln, och
Skriv ut dem till användaren, en rad per grupp.
Den första raden, putStr "Depth? " skriver bara ut frågan om depth för användaren. Efter det läser vi in en rad text från användaren (getLine), konverterar den till ett nummer (fmap read) och sen sparar den i variabeln depth. Det intressanta är att fmap read skulle kunna konvertera till vad som helst. Varför konverterar den till ett nummer? Den kollar,
Vad används depth till? Aha, den används som argument till en funktion som tar ett nummer som argument – alltså måste depth vara ett nummer. Okej! Jag konverterar till ett nummer!
Haskells typsystem är väldigt flexibelt på så sätt. Trots att vi inte har angett en enda typ i hela programmet så kan den ändå lista ut vad alla typer ska vara, och den konverterar saker rätt beroende på vad de har för typ. Kompilatorn vet precis vilken typ en Floyd-triangel har (lista av listor av nummer.) Den vet precis vilken typ som den måste få för att kunna skriva ut något på skärmen (sträng) och den sorterar ut allt sånt innan programmet ens har kört. Är det något fel får vi veta det direkt!
När vi har läst in från användaren hur mycket triangel den vill ha så plockar vi ut så mycket triangel ur vår floydTriangle-variabel. Vi vet inte ännu hur variabeln skapas, men vi kan tänka på den som att den innehåller hela, oändligt stora Floyds triangel. Vi förutsätter det.
let finiteTriangle = take depth floydTriangle
Detta skapar variabeln finiteTriangle (icke-oändlig triangel) och sätter den att vara lika med de första depth lagrena av floydTriangle, som ju vara hela, stora, oändliga Floyds triangel. Nu kommer finiteTriangle vara en icke-oändlig lista av listor av nummer.
mapM_ (putStrLn . show) finiteTriangle
Den sista raden i main-funktionen konverterar varje lista inuti finiteTriangle (med mapM_) till en sträng (med show) och skriver ut den på en egen rad (med putStrLn.)
Du kanske undrar om det går att skriva ut den oändliga triangeln, istället för att ta en slice av den. Ja, det går, men det är ganska värdelöst med ett program som sprutar ut siffror i all oändlighet (faktiskt!), så vi väljer att avgränsa den till något värde. Om vi behöver mer av triangeln senare är det ju bara att be om ett större värde – hela den oändliga triangeln finns ju lagrad i floydTriangle.
Nu till den största magin, när vi skapar variabeln floydTriangle!
floydTriangle = unfoldr (Just . nextFloyd) (1,1) where nextFloyd (number, quantity) = (take quantity [number..], (number+quantity, quantity+1))
Floyds triangel följer ett unfold-mönster. De flesta saker man gör inom programmering följer något mönster, och ett av mönstrena är att generera en lista baserat på någon funktion och ett ursprungsvärde. Om man har ett ursprungsvärde, någon funktion, och vill göra en lista med värden, då är det ett unfold-mönster man ska implementera. Lyckligtvis finns det redan en funktion unfoldr i Haskells standardbibliotek för att jobba med listor, så vi använder den färdiga funktionen.
Och Floyds triangel kräver ju egentligen bara en unfold: man startar med numret 1 och gruppen 1, och man kan uppfinna en funktion för att generera nästa grupp. I Haskell-kod blir det
unfoldr (Just . nextFloyd) (1,1)
Funktionen unfoldr implementerar unfold-mönstret. Vi skickar med som ursprungsvärde (1,1), och funktionen för att ta fram nästa grupp är nextFloyd. (Vi skickar varje grupp genom Just-funktionen också, egentligen bara för att unfoldr vill värdena på ett speciellt format.)
När vi har insett att det är en unfold vi är ute efter, så blir det intressanta funktionen nextFloyd: den tar ett argument som består av två delar,
och den ska generera ett resultat med två delar,
en kombination av startsiffra och gruppnummer för nästa grupp.
Funktionen ser ut som följer.
nextFloyd (number, quantity) = (take quantity [number..], (number+quantity, quantity+1))
number är startsiffran för denna grupp, och quantity är gruppnumret, eller, om man vill, antalet tal som ska vara med i den här gruppen. Kom ihåg att antalet tal i varje grupp är lika med gruppnumret.
Svaret består av två delar, varav den första delen är gruppen man får med det startnumret och gruppnumret som skickas som argument.
[number..] kommer att generera en oändligt lång lista av nummer, som startar med number. Till exempel [7..] kommer att generera listan som börjar med 7, fortsätter med 8, sen 9, sen 10, sen 11, sen 12 och så vidare. Vi plockar ur (take) gruppnumret antal tal (quantity) ur den oändliga listan, och kvar har vi en lista som börjar med number och innehåller quantity tal. Precis det vi ville!
Andra delen av svaret är delen som talar om för oss var nästa grupp startar och hur många tal den ska innehålla.
(number+quantity, quantity+1)
Denna kod returnerar startnumret för nästa grupp (number+quantity) och gruppnumret för nästa grupp (quantity+1). Sammanställt kommer funktionen returnera en grupp och villkoren för nästa grupp. Om vi matar in (7,4) kommer den att ge tillbaks dels [7,8,9,10] (den fjärde gruppen) samt (11,5) (villkoren för nästa grupp.) Om vi stoppar in villkoren för nästa grupp ((11,5)) i funktionen igen kommer vi få ut nästa grupp ([11,12,13,14,15]), samt villkoren för gruppen efter det ((16,6)). Funktionen i sin helhet är ganska enkel:
nextFloyd (number, quantity) = (take quantity [number..], (number+quantity, quantity+1))
Denna funktion, som ger en grupp och villkoren för nästa grupp, är precis vad vi behöver i unfold-mönstret. Det är så unfold-mönstret fungerar. Man har en funktion som ger ett svar och villkoren för nästa svar, och så matar man in villkoren i funktionen igen, får nya villkor och matar in dem igen. Ad infinitum.
Hela programmet sammanställt är
module Main where import Data.List (unfoldr) floydTriangle = unfoldr (Just . nextFloyd) (1,1) where nextFloyd (number, quantity) = (take quantity [number..], (number+quantity, quantity+1)) main = do putStr "Depth? " depth <- fmap read getLine let finiteTriangle = take depth floydTriangle mapM_ (putStrLn . show) finiteTriangle
och nu har vi ett lite bättre grepp om hur det fungerar. Det är dessutom matematiskt enligt kraven som ställdes i början. Triangelvariabeln innehåller till och med en oändlig triangel, för vår nextFloyd-funktion kan man ju använda på sig själv gång på gång på gång. Det är därför det är "viktigt" att vi plockar ut bara lite av den oändliga triangeln, för annars blir det väldigt mycket triangel väldigt snabbt.
Det finns ett annat sätt att implementera triangeln på, men som inte är lika snyggt enligt mig, eftersom det inte reflekterar problemets natur tydligt. Det ger dock något kortare kod. Det är följande.
floydAlternative = map group [0..] where group n = take (n+1) [(n*n + n + 2) div 2..]
group är en funktion som tar ett argument – ett gruppnummer. Med det gruppnumret genererar group den efterfrågade gruppen. (Obs! Här är grupp nummer 0 den första gruppen, till skillnad från i förra implementationen.) Exempelvis kommer group 3 ge [7,8,9,10] medan group 1 ger [2,3].
Men om man har en funktion som ger en grupp om man ger den ett gruppnummer, så behöver man ju bara använda den funktionen på alla gruppnummer för att få en färdig Floyds triangel. Det åstadkoms av map group [0..] som använder group på alla tal med start 0 och returnerar resultatet.
Denna kod är kortare och använder simplare koncept, men funktionen för att räkna ut en grupp baserat på dess nummer är inte alls lika snygg och lätt att förstå enligt mig, eftersom den kräver lite matematisk analys av hur grupperna kan räknas ut.
Oavsett vilken approach man föredrar så får man av Haskell väldigt kraftfulla verktyg för att göra som man vill. En variabel som innehåller en oändlig triangel skulle kräva väldigt mycket onödig extrakod i andra språk. Att generera triangeln före man skriver ut den skulle vara svårt att hålla reda på i språk utan automagisk minneshantering, och riskerar att göras på ett ineffektivt sätt även i språk med minneshantering.