February 2012 - Beginners

Cabal complains that cabal-dev “indirectly depends on multiple versions of the same package”, even though it (apparently) does not
by James Fisher 16 Feb '12

16 Feb '12

Hi all, I've just asked this on SO as well ( http://stackoverflow.com/questions/9301122/haskell-cabal-package-indirectly…) but to repeat the question: After clearing out all of my cabal installed packages, I ran this following session: $ cabal update Downloading the latest package list from hackage.haskell.org james@bast:~/.cabal/packages$ cabal install cabal-dev Resolving dependencies... Downloading cabal-dev-0.9.1... [1 of 1] Compiling Main ( /tmp/cabal-dev-0.9.124882/cabal-dev-0.9.1/Setup.hs, /tmp/cabal-dev-0.9.124882/cabal-dev-0.9.1/dist/setup/Main.o ) Linking /tmp/cabal-dev-0.9.124882/cabal-dev-0.9.1/dist/setup/setup ... Configuring cabal-dev-0.9.1... Warning: This package indirectly depends on multiple versions of the same package. This is highly likely to cause a compile failure. package containers-0.4.2.1 requires array-0.4.0.0 package Cabal-1.14.0 requires array-0.4.0.0 package text-0.11.1.13 requires array-0.4.0.0 package deepseq-1.3.0.0 requires array-0.4.0.0 package containers-0.4.2.1 requires array-0.4.0.0 package HTTP-4000.2.2 requires array-0.4.0.0 package cabal-dev-0.9.1 requires containers-0.4.2.1 package Cabal-1.14.0 requires containers-0.4.2.1 package template-haskell-2.7.0.0 requires containers-0.4.2.1 Building cabal-dev-0.9.1... Preprocessing executable 'ghc-pkg-6_8-compat' for cabal-dev-0.9.1... <command line>: cannot satisfy -package-id Cabal-1.14.0-4af45d3c8d10dc27db38ae0e7e5a952b: Cabal-1.14.0-4af45d3c8d10dc27db38ae0e7e5a952b is unusable due to missing or recursive dependencies: array-0.4.0.0-46f61f5fd9543ebf309552ef84dccc86 containers-0.4.2.1-98f9aa15f9c08b13673dc9d89385f449 (use -v for more information) cabal: Error: some packages failed to install: cabal-dev-0.9.1 failed during the building phase. The exception was: ExitFailure 1 $ So the reason I can't install cabal-dev is apparently either that - it "indirectly depends on multiple versions of the same package." However, cabal does not name the package that it claims cabal-dev requires multiple versions of. - Cabal-1.14.0 has "missing or recursive dependencies", specifically somehow involving array-0.4.0.0 and containers-0.4.2.1. A graph of the dependencies it lists confirms that neither of these claims are true (or the dependencies it lists are false or incomplete): [image: claimed dependency graph of cabal-dev-0.9.1] *So: what am I missing? Who or what is incorrect: me, cabal, or one or more packages?* I am running: $ cabal --version cabal-install version 0.10.2 using version 1.10.1.0 of the Cabal library $ ghc --version The Glorious Glasgow Haskell Compilation System, version 7.4.1 $ Any help with this would be greatly appreciated. I get errors from cabal fairly often and I usually end up giving up because I don't understand the error. James

4 5

Relation between monads and computations
by Dmitriy Matrosov 16 Feb '12

16 Feb '12

Hi, everyone! Not so long ago i started to learn haskell, and now i have a question about relation between monads and computations. In fact, i think, that i understand it and write some explanation for myself, but i'm not sure whether my explanation is correct or not, and will be very thankful if someone check it :) Here it is (i don't know category theory and my math knowledge is poor, so if i accidently use some terms from them incorrectly - it was just my understanding). Monads and computations. Generally computation consists of initial value, computation itself and the result. So it can be illustrated as: type a (M b) b data I ------> C <--------- E f ConstrM I :: a f :: a -> M b data M a = ContrM a | ... E :: b Let's see what happens: i take initial value I of type a and map it to some computation C (of type (M b)) using function f. Then, exist such value E of type b, that C = (ConstrM E). This value E will be the result of computation. Now consider two functions: unitM, which maps value into trivial computation (trivial computation is a computation, which result is equal to initial value): type a (M a) a data I ------> C <--------- I unitM ConstrM I :: a unitM :: a -> M a data M a = ContrM a | ... and bindM, which yields result from one computation, then applies some function f to the result, and makes another computation at the end (E is the result of this last computation). type (M a) a (M b) b data C ---------> I -------> C' <---------- E pattern f ConstrM match data C --------------------> C' <---------- E C `bindM` f ConstrM C :: M a I :: a f :: a -> M b C' :: M b data M a = ContrM a | ... E :: b bindM :: M a -> (a -> M b) -> M b Now, using fucntions unitM and bindM there is possibly to convert arbitrary function (k :: a -> b), which makes from initial value of type a value of type b, into terms of general computation (represented by type M). type a (M a) a b (M b) b data I ------> C ---------> I ------> E -------> C' <-------- E unitM pattern k unitM ConstrM match data I ------> C ---------> I -----------------> C' <-------- E unitM pattern f = (unitM . k) ConstrM match data I ------> C ------------------------------> C' <-------- E unitM `bindM` f ConstrM data I --------------------------------------------> C' <-------- E g = (`bindM` f) . unitM ConstrM I :: a unitM :: a -> M a C :: M a k :: a -> b C' :: M b data M a = ConstrM a | ... E :: b f :: a -> M b bindM :: M a -> (a -> M b) -> M b g :: a -> M b On the first picture i take initial value I of type a, and map it to trivial computation C of type (M a) using unitM. Then i yield result of this trivial computation C (which is I, of course), apply function k to this result (value I) and get value E of type b as result. Then i wrap this value E into trivial computation C' using unitM. Result of computation C' is, of course, E. On the intermediate pictures i show reduction steps of the first picture. And finally i get: i take initial value I of type a, and map it using function g into computation C'. The result of computation C' is value E of type b. So, from arbitrary function (k :: a -> b) i can create function g, which maps initial value I of type a into some computation of type (M b). Actual computation (calculation) will still be performed by k, but the result will have type of general computation (M b) instead of b. Monad is a way to implement such general computation, a way to write a program based on general computations, which later may be redefined, instead of particular ones, which redefinition leads to rewrite of large of amount of code. Monad is a triple of type constructor M and functions unitM and bindM (and errorM, probably?). Type constructor represents computation itself, functions unitM and bindM used to wrap your own specific computation (k :: a -> b) on types a and b into monadic notation (general computation notation). First two of monad laws demand, that unitM maps into trivial computation. ..may be continued.. -- Dmitriy Matrosov

2 4

Effective file I/O with bytestrings
by Johannes Engels 10 Feb '12

10 Feb '12

Dear Haskellers, in several books (RWH, LYAH) I have found the statement that file I/O is more effective with bytestrings than with common strings. As I am doing mostly scientific programming and nearly every program of mine uses file I/O, I would like to check this. So I tried to write a small "benchmark": read a double matrix from file and write it to file again. Regarding to reading, the benefit of bytestrings was actually huge, it was about ten times faster than with strings. What refers to writing, however, I failed completely. Most important, I did not find a function which directly converts doubles to bytestrings. So the best I could figure out was the following ugly workaround using Text.Show.ByteString: import qualified Data.ByteString.Lazy as DL import qualified Text.Show.ByteString as BS import Data.Char import Data.List import Data.Array.Unboxed lineendw8 = DL.pack [fromIntegral (ord '\n')] blankw8 = DL.pack [fromIntegral (ord ' ')] showAll :: UArray (Int, Int) Double -> -- matrix Int -> -- number of rows Int -> -- number of columns DL.ByteString showAll mymatrix numrows numcols = foldr f lineendw8 [0..numrows-1] where f = showLine mymatrix numcols showLine :: UArray (Int,Int) Double -> -- matrix Int -> -- number of columns Int -> -- current row DL.ByteString -> -- accumulator DL.ByteString showLine mymatrix numcols row akku = let f col s = DL.append blankw8 $ DL.append (BS.runPut $ BS.showp (mymatrix!(row,col))) s in DL.append lineendw8 $ foldr f akku [0..numcols-1] main :: IO () main = do -- read file into UArray Int, Int) Double ... -- .... -- ... and write it to file again let bs = showAll mymatrix numrows numcols DL.writeFile "writeOut.dat" bs This was more in order to show goodwill than to present a solution, of course. It actually works, but, ugly as it is, it is by no means faster than the corresponding procedure with strings. So my question: what is the canonical way to write doubles to file? I guess this question must have been posed already hundred times before, so I would also appreciate very much a link to former answers ... Best regards Johannes Engels

3 2

Newtype to avoid orphans
by Adrien Haxaire 06 Feb '12

06 Feb '12

Hello, In the library I am writing, I declare a type Vector for Data.Vector Double. I then create a Num instance for it as it doesn't have one yet. GHC tells me that this instance is an orphan. After reading several answers to issues like mine, I want to get rid of these orphans. The advice I saw mostly is to use the newtype keyword. Is there a way to do it nicely, instead of copying most of the API of Data.Vector ? Now, the only thing I can see is do like in this example: import Data.Vector as V newtype VectorD = VectorD (V.Vector Double) map :: (Double -> Double) -> VectorD -> VectorD map f (VectorD v) = VectorD $ V.map f v Is there a better way ? Best regards, Adrien

2 4

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