- Beginners - Haskell.org

Is foldr slow?
by Zhi-Qiang Lei 06 Feb '12

06 Feb '12

Hi, When I refactor my Segmented Seive of Eratosthenes, I'm puzzled by the performance of "foldr". Here is my original code. I realized that "sieveWith"(Integral a => ([a], [a]) -> ([a], [a]), it takes a tuple with sieving primes and prime candidates, and remove all multiplies of sieving primes in candidates, at last return a tuple with blank sieving primes and a pure primes list) in "primesFromTo" is not much readable and can be replaced by "foldr". But when I did, I find it would take about 5 seconds to sieve primes between 999900000 and 1000000000, whereas the original one just takes 1.6 seconds. The "sieveWith" function is the only place I change. I also have tried foldr', which does not much help. Is foldr slow? Or did I make any mistake? Thanks. === Origin (./main < data1.txt 1.45s user 0.11s system 99% cpu 1.562 total) === {-# OPTIONS_GHC -O2 #-} import Data.List import System.IO minus (x:xs) (y:ys) = case (compare x y) of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs intSqrt :: Integral a => a -> a intSqrt = floor . sqrt . fromIntegral primesTo :: Integral a => a -> [a] primesTo x = 2 : sieve [3, 5 .. x] where sieve ns@(n : rs) | n <= intSqrt x = n : sieve (rs `minus` [n * n, n * (n + 2) .. x]) | otherwise = ns sieve [] = [] candidatesBetween :: Integral a => a -> a -> [a] candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y] primesFromTo :: Integral a => a -> a -> [a] primesFromTo x y | x < 2 = primesTo y | otherwise = snd . sieveWith $ (primes, candidates) where primes = tail . primesTo . intSqrt $ y candidates = candidatesBetween x y sieveWith (a : as, bs'@(b : bs)) = sieveWith (as, bs' `minus` multiplies a b) where sieveWith ([], bs) = ([], bs) multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y] primesFromTo' [x, y] = primesFromTo x y main :: IO () main = do count <- fmap read getLine inputLines <- fmap (take count . lines) getContents let answers = map (primesFromTo' . map read . words) inputLines putStr . unlines . map (unlines . map show) $ answers === Origin === === New (./main < data1.txt 4.76s user 0.15s system 99% cpu 4.917 total) === {-# OPTIONS_GHC -O2 #-} import Data.List import System.IO minus (x:xs) (y:ys) = case (compare x y) of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs intSqrt :: Integral a => a -> a intSqrt = floor . sqrt . fromIntegral primesTo :: Integral a => a -> [a] primesTo x = 2 : sieve [3, 5 .. x] where sieve ns@(n : rs) | n <= intSqrt x = n : sieve (rs `minus` [n * n, n * (n + 2) .. x]) | otherwise = ns sieve [] = [] candidatesBetween :: Integral a => a -> a -> [a] candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y] primesFromTo :: Integral a => a -> a -> [a] primesFromTo x y | x < 2 = primesTo y | otherwise = sieveWith primes candidates where primes = tail . primesTo . intSqrt $ y candidates = candidatesBetween x y -- sieve a list of candidates with sieving primes -- foldr version: ./main < data1.txt 4.76s user 0.15s system 99% cpu 4.917 total sieveWith ps'@(p : ps) cs'@(c : cs) = foldr (\a b -> b `minus` (multiplies a c)) cs' ps' sieveWith [] cs = cs multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y] primesFromTo' [x, y] = primesFromTo x y main :: IO () main = do count <- fmap read getLine inputLines <- fmap (take count . lines) getContents let answers = map (primesFromTo' . map read . words) inputLines putStr . unlines . map (unlines . map show) $ answers === New === Best regards, Zhi-Qiang Lei zhiqiang.lei(a)gmail.com

3 4

First program
by ARJANEN Loïc Jean David 06 Feb '12

06 Feb '12

Hello, I am learning Haskell, and as a first program have made a JSON-RPC client library (code accessible here: https://patch-tag.com/r/Azel/hs-json-rpc/home) I would like to know if I have done great errors, be that errors of style or of library use. Thanking you for your time. Best regards, ARJANEN Loïc

3 2

numerical integration over lists
by Thomas Engel 05 Feb '12

05 Feb '12

Hello, I have two list (one with x values, the other with y values) What I want to do is a numercial integration according the following formula: Result x2 = Result x1 + ((y(x1) + y(x2))/2) * (x2 -x1) and put the result in another list. below my first try: integriereListe::(a)->(a)->(a) integriereListe [][] = [0.0] integriereListe (x:xs) (y:ys) = ((y - y2) /2) * (x2 -x) where x2 = head xs y2 = head ys but I got the failure Couldn't match type `[t0]' with `[[t0]]' In the pattern: y : ys In an equation for `integriereListe': integriereListe (x : xs) (y : ys) = ((y - y2) / 2) * (x2 - x) where x2 = head xs y2 = head ys another problem is how get the result x1 (see above) any hints are welcome. Thomas

4 8

yet another monad question
by Ovidiu Deac 05 Feb '12

05 Feb '12

I have the following code which works fine: type File = (String, String) --name and content readDir :: String -> IO [File] readDir dir = findRegularFiles dir >>= readFiles where findRegularFiles = find always (fileType ==? RegularFile) readFiles paths = mapM readFile paths >>= return.zip paths ...and I would like to write the function readDir like this: readDir :: String -> IO [File] readDir = findRegularFiles >>= readFiles where ... ...but I get the error: grep.hs:46:32: Couldn't match expected type `IO [FilePath]' with actual type `[FilePath]' Expected type: IO [FilePath] -> String -> IO [File] Actual type: [FilePath] -> IO [File] In the second argument of `(>>=)', namely `readFiles' In the expression: findRegularFiles >>= readFiles Can somebody please explain it? It's not a big deal. I can keep the old version which works fine. My only problem is that I thought I understood the monads better but apparently I don't :)

4 4

Performance of Prime Generator
by Zhi-Qiang Lei 05 Feb '12

05 Feb '12

Hi, I have bungled the Prime Generator on SPOJ for many times. Although the program is faster and faster on my machine, but it keeps "time limited exceeded" on SPOJ (6 seconds limit). Now my approach is for every number in the range, check if it is prime by checking if can be divided by all the primes smaller than or equal its square root. For the numbers between 999900000 and 1000000000, it take 0.64 seconds on my laptop. Could anyone give me some hints to enhance it? Thanks. === Test Data === 1 999900000 1000000000 === Test Data === === Code === {-# OPTIONS_GHC -O2 -fno-cse #-} import System.IO data Wheel a = Wheel a [a] roll :: Integral a => Wheel a -> [a] roll (Wheel n rs) = [n*k+r | k <- [0..], r <- rs] nextSize :: Integral a => Wheel a -> a -> Wheel a nextSize (Wheel n rs) p = Wheel (p*n) [r' | k <- [0..(p-1)], r <- rs, let r' = n*k+r, r' `mod` p /= 0] mkWheel :: Integral a => [a] -> Wheel a mkWheel ds = foldl nextSize (Wheel 1 [1]) ds primes :: Integral a => [a] primes = small ++ large where 1:p:candidates = roll $ mkWheel small small = [2,3,5,7] large = p : filter isPrime candidates isPrime n = all (not . divides n) $ takeWhile (\p -> p*p <= n) large divides :: Integral a => a -> a -> Bool divides n p = n `mod` p == 0 sqrt' :: Integral a => a -> a sqrt' = floor . sqrt . fromIntegral primesFromTo :: [Int] -> [Int] primesFromTo [x, y] = filter isPrime [x..y] isPrime :: Integral a => a -> Bool isPrime 1 = False isPrime 2 = True isPrime n = all (not . divides n) $ takeWhile (<= sqrt' n) primes main :: IO () main = do count <- fmap read getLine inputLines <- fmap (take count . lines) getContents let answers = map (primesFromTo . map read . words) inputLines putStr . unlines . map (unlines . map show) $ answers === Code === Best regards, Zhi-Qiang Lei zhiqiang.lei(a)gmail.com

5 12

Re: [Haskell-beginners] nested guards (Stephen Tetley)
by Thomas Engel 04 Feb '12

04 Feb '12

> > http://www.haskell.org/haskellwiki/Case > > > > That link shows how to write a select function that offers functionality > > similar to a switch statement in C. ?Then you could use guards for the > > top-level switching and the select function for the second level. > > Yikes - that idiom is rather horrible, vis packing cases into a list > so they can be consumed by a function. > > To solve the problem, I'd seek a more "mathy" description of the > algorithm i.e. one that doesn't use conditionals so heavily and work > from that rather than translate existing code. > Hi Stephen, I have solved the problem. I have made four functions instead of one. > > > Thanks > > Thomas >

1 0

How memorize intermediate computation value[my brain is so hurt]?
by anyzhen 04 Feb '12

04 Feb '12

there have a lot of situation we need memorize intermediate computation value. and use in further. like this, compute nth fib question. So,how memorize it? i have an ugly solution.it used HashTable for memorization. fib n table | n==1 =1 | n==2 =1 | otherwise = case lookup table of Just v ->(v,table) Nothing ->let (v,table') = fib (n-1) table in let ( v',table'')= v + fib(n-2) table' in (v',table'') i am an beginner come from imperative programming language. so fib memorize version program hurt my brain ... particular in Nothing branches. so do you have some good idea

4 3

nested guards
by Thomas Engel 03 Feb '12

03 Feb '12

Hello, I'm new to haskell. I want to write a function for a s-curve acceleration in haskell. A solution in VBA is already working. Are there nested guards in haskell available or how can I rewrite this function? The function should calculate the acceleration for a given distance, max acceleration, velocity, jerk at time since start acc_skurve::Float->Float->Float->Float->Float->Float acc_skurve str acc v jerk taktuell | str <= str2jerk |taktuell <= (0.5 * str / jerk)**(1/3::Float) = jerk * taktuell |taktuell <= (4 * str / jerk)**(1/3::Float) = jerk**(2/3::Float) * 2**(2/3::Float) * str**(1/3::Float) - jerk * taktuell |taktuell <= (27/2 * str / jerk)**(1/3::Float) = - jerk * taktuell + 2**(2/3::Float) * str**(1/3::Float) * jerk**(2/3::Float) |taktuell <= (32 * str / jerk)**(1/3::Float) = -2 * 2**(2/3::Float) * str**(1/3::Float) * jerk**(2/3::Float) + jerk * taktuell | str > str2jerk && str < str2acc |taktuell <= acc / jerk = jerk * taktuell |taktuell <= - acc / 2 / jerk + sqrt(acc^3 + 4 * str * jerk^2) / (2 * jerk * sqrt(acc)) = acc |taktuell <= acc / 2 / jerk + sqrt(acc^3 + 4 * str * jerk^2) / (2 * jerk * sqrt(acc)) = acc / 2 - jerk * taktuell + sqrt(acc^3 + 4 * str * jerk^2) / (2 * sqrt(acc)) |taktuell <= 3 * acc / 2 / jerk + sqrt(acc^3 + 4 * str * jerk^2) / (2 * jerk * sqrt(acc)) = acc / 2 - jerk * taktuell + sqrt(acc^3 + 4 * str * jerk^2) / (2 * sqrt(acc)) |taktuell <= sqrt(acc^3 + 4 * str * jerk^2) / (sqrt(acc * jerk)) = - acc |taktuell <= acc / jerk + sqrt(acc^3 + 4 * str * jerk^2) / (sqrt(acc * jerk)) = - acc + jerk * taktuell - sqrt(acc^3 + 4 * str * jerk^2) / sqrt(acc) | str >= str2acc |taktuell <= acc / jerk = jerk * taktuell |taktuell <= v / acc = acc |taktuell <= acc / jerk + v / acc = acc - jerk * taktuell + v * jerk / acc |taktuell <= str / v = 0 |taktuell <= str / v + acc / jerk = jerk * str / v - jerk * taktuell |taktuell <= str / v + v / acc = - acc |taktuell <= str / v + acc / jerk + v / acc = -(str / v + acc / jerk + v / acc - taktuell) * jerk where str2jerk = 2 * acc^2 / jerk^2 str2acc = acc^2 * v + v^2 * jerk / (jerk * acc) best regards Thomas

3 2

(no subject)
by Thomas Engel 03 Feb '12

03 Feb '12

1 0

unchecked exceptions as side effects
by Ovidiu Deac 02 Feb '12

02 Feb '12

In this video Erik Meijer talks about side effects: https://www.youtube.com/watch?v=UuamC0T3hv8&t=6m and unchecked exceptions as side effects. I tried to read the paper "Unchecked Exceptions can be Strictly More Powerful than Call/CC" but I got lost pretty quick. Can somebody explain the matter nicely? Thanks, ovidiu

1 0