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.