Programeer opdrachtenOpdracht : opdr7a_moshe.txt

Terug naar de inzendingen
Opdracht 7a,Moshe van der Sterren
23-Jan-2010
 Af en toe kom ik hier langs om te kijken of er nog interresante
 programeeropdrachten te vinden zijn, en nu zie ik dat ik een maand te laat ben
 :-(
 
 Ik ben vanavond druk bezig geweest, en ik heb een implementatie van de
 wortelopdracht in Haskell, ookal ben ik veel te laat, ik denk dat het toch wel
 interresant is om het hier te laten zien.
 
 De wiskundige functies die ik gebruik zijn de integer-operators `div` en
 `mod`, en de product functie (vermenigvuldigt alle items in een list met
 elkaar), de `pow` operator heb ik geimplementeerd met de product functie, de
 builtin versie van Haskell is ^
 Ik heb geprobeerd om niet alteveel poespas toe te voegen, de zeef en het
 ontbinden kunnen heel erg geoptimaliseerd worden, maar zo zijn ze mooi
 overzichtelijk.
 Ik heb gekozen voor een iets andere aanpak dan de andere oplossingen, de
 andere oplossing is waarschijnlijk iets korter en onduidelijker (in haskell).
 Wat betreft de input/output handling, het gaat hier om een functionele
 programeertaal, dus is het totaal anders dan bij een imperatieve
 programeertaal.
 1 
*****wortel.hs****
  
 2--
 3-- Run with: runhaskell wortel.hs 
 4-- To install Haskell, try "yum install ghc" or "apt-get install ghc6" or look
 5-- at http://www.haskell.org/ for the available alternate compilers and
 6information.
 7--
 8-- This program calculates a simplified square root of a given number.
 9-- If the number is a perfect square, the square root is printed,
 10-- if the number has no simplified root, "wortel " is printed,
 11-- otherwise, " wortel " is printed, meaning: the square root of
 12-- the number equals 'c * √(r)'.
 13--
 14-- Copyright Môshe van der Sterre
 15--
 16
 17-- import 'group'
 18import List
 19-- import 'getArgs'
 20import System.Environment
 21
 22-- Power operator, define the `pow` operator to do the same as the builtin ^
 23operator
 24pow :: Int -> Int -> Int
 25pow base exponent = product $ replicate exponent base
 26
 27----- First some generic functions: a prime sieve and prime factorization
 28-----
 29
 30-- Sieve of Eratosthenes
 31primes :: [Int]
 32primes = sieve [2..] where sieve (number:numbers) = number : [ next | next <-
 33(sieve numbers), next `mod` number > 0 ]
 34
 35-- Least Prime Factor
 36lpf :: Int -> Int
 37lpf number = head $ dropWhile (not.divides number) primes where divides a n =
 38a `mod` n == 0
 39
 40-- Prime Factors
 41factors :: Int -> [Int]
 42factors 1 = []
 43factors number = let current = lpf number in current : (factors $ number `div`
 44current)
 45
 46----- The problem-specific calculations: factors as a list of powers, '√(n)'
 47to 'a * √(b)' and the final combination -----
 48
 49-- Prime factors as (base, exponent) tuple
 50factorpowers :: Int -> [(Int, Int)]
 51factorpowers number = [ (head g, length g) | g <- (group $ factors number) ]
 52
 53-- Square root of a (base, exponent) tuple, as a tuple (a, b) with √(n) = a *
 54√(b)
 55sqrt_power :: (Int, Int) -> (Int, Int)
 56sqrt_power (base, exponent) | even exponent = (base `pow` (exponent `div` 2),
 571)
 58                            | exponent == 1 = (1, base)
 59                            | otherwise     = (base `pow` (exponent `div` 2),
 60base)
 61
 62-- Final square root, returns (a, b) with √(number) = a * √(b)
 63p_sqrt :: Int -> (Int, Int)
 64p_sqrt number = (product $ fst result, product $ snd result) where result =
 65unzip $ map sqrt_power $ factorpowers number
 66
 67----- The calculations are done, everything below is for input/output handling
 68-----
 69
 70-- Format the output-string
 71formatoutput :: (Int, Int) -> String
 72formatoutput (complp, rootp) | rootp == 1  = (show complp) ++ "\n"
 73                             | complp == 1 = "wortel " ++ (show rootp) ++ "\n"
 74                             | otherwise   = (show complp) ++ " wortel " ++
 75(show rootp) ++ "\n"
 76
 77-- Parse the arguments and call p_sqrt and formatoutput
 78getbusy :: [String] -> String
 79getbusy args = let number = (read (head args)::Int) in formatoutput (p_sqrt
 80number)
 81
 82-- Main function, pass the arguments to getbusy and print the result
 83main :: IO ()
 84main = getArgs >>= putStr.getbusy
 
 
Mijn commentaar
 
 Moshe,
 Haskel is nu niet speciaal een taal die je op een average Linux systeem zou
 verwachten, maar je geeft heel keurig aan hoe je de haskel compiler moet
 instaleren dus dat kan niet echt een probleem worden.
 Ik heb zelf nooit met Haskel te maken gehad maar wat mij direct opvalt is de
 compactheid van de code, en met enige goede wil is de werking van je programma
 goed te volgen (niet in de laatste plaats ook dankzij je commentaar regels)
 Ik had eigenlijk ook nog wel een bijdrage in Lisp verwacht, (Dirk Gerrits, Koning Robot, waar zijn jullie gebleven ?),
 maar Haskel zijn we helemaal nog niet tegengekomen.
 
 Dank je voor het meedoen en ik hoop dat je het forum wat vaker in de gaten
 houdt zodat je volgende opdracht niet mist.