January 2010 - Beginners

Stack Overflow with foldl'
by Cyril Pichard 23 Jan '10

23 Jan '10

Hi, I don't understand why the following code always result in a Stack space overflow error. I'm using foldl' and think the main algorithm is tail recursive. Am I wrong ? I've read the http://www.haskell.org/haskellwiki/Stack_overflow Any help would be greatly appreciated. Thanks module Main where import Data.List -- Data structures data Point = Point { x::Double, y::Double, z::Double } deriving(Eq, Show) data Triangle = Triangle { p1::Point, p2::Point, p3::Point } deriving(Eq, Show) data BBox = BBox { bbmax::Point, bbmin::Point } deriving(Eq,Show) -- Construct a default triangle newTriangle :: Triangle newTriangle = Triangle (Point 1 0 0) (Point 0 1 0) (Point 0 0 1) -- Construct a default BBox newBBox = BBox (Point 0 0 0) (Point 0 0 0) -- Defines min and max for Point instance Ord Point where max a b = Point ( max (x a ) (x b) ) ( max (y a) (y b) ) ( max (z a) (z b) ) min a b = Point ( min (x a ) (x b) ) ( min (y a) (y b) ) ( min (z a) (z b) ) -- Create a list of triangles makeTriangles :: Double -> [Triangle] makeTriangles 0 = [] makeTriangles n = [ Triangle (Point v 0 0) (Point 0 v 0) (Point 0 0 v) | v <- [1..n] ] -- Compute the bounding box of a triangle boundingBox :: Triangle -> BBox boundingBox t = BBox pmax pmin where pmax = max (p3 t) (max (p1 t) (p2 t)) pmin = min (p3 t) (min (p1 t) (p2 t)) -- Compute the bounding box of two bounding boxes bboxAddb :: BBox -> BBox -> BBox bboxAddb (BBox bb1max bb1min) (BBox bb2max bb2min) = BBox (max bb1max bb2max) (min bb1min bb2min) -- Compute the bounding box of a triangle and a bounding box bboxAddt :: BBox -> Triangle -> BBox bboxAddt b t = bboxAddb b (boundingBox t) main = do print $ foldl' bboxAddt newBBox triangles; where triangles = makeTriangles 610000 error returned : Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize' to increase it. ghc version 6.10.3 on MacOsX Snow Leopard

2 1

Re: [Haskell-beginners] Re: testing and the culture of Haskell
by Adrian Adshead 23 Jan '10

23 Jan '10

>All Haskell functions are pure without exception. For example: > >greet :: String -> IO () >greet name = putStrLn $ "Hello, "++name > >This is a pure function from String to IO (). This function (like all >Haskell functions) has no side effects. Its return value of type IO () >merely _represents_ an IO action. The runtime system knows how to act >on this representation. > >This also means that there is no such thing in Haskell as marking a >function as side-effecting. > >This distinction may be subtle, but it's important. > > >Steve Steve, Please could you clarify this for me since you are making exactly the opposite assertion than I have understood. I am confused by you stating "All Haskell functions are pure without exception.". Pure functions have no impact on 'anything'. They take input parameters (which they don't change) and return exactly the same result whenever the same input parameters are given. >greet :: String -> IO () >greet name = putStrLn $ "Hello, "++name This example you gave is not a pure function since it does have the side effect that the screen is changed by outputting the string "Hello, " and the name passed in. As I understand it the IO in the type signature is the programmers indication to the compiler that the function is not guaranteed to be side effect free. add_pure :: Integer -> Integer add_pure x = x + 5 add_impure :: Integer -> IO Integer add_impure x = return (x + 5) add_pure is clearly a pure function. add_impure while it is totally side effect free and therefore fulfills the definition of purity, is impure as far as the compiler is concerned since I (the programmer) have told the compiler that I do not guarantee that the function is pure. Please let me know where I am misunderstanding purity. Many thanks Adrian.

4 3

Backtracking
by legajid 22 Jan '10

22 Jan '10

Hi, i'm writing a Sudoku solver -a very new idea ;) - , using brute force. The challenge for me is to keep track of all tries and go back and forward. My general idea is : make a list of all cells with value 0 For each of these cells, try values 1 to 9. If a value matches (that is not used in cells on the same line, column or square) then proceed the same way with the next empty cell. If a value doesn't match, get back to the preceding cell and take the next value available : here is my problem, i don't know how to go back. The calcul function, invoked once, creates the list of empty cells, then calls calcul' Calcul' creates the list of possible values, then calls calcul'' with the list. Calcul'' tries to apply each possible value.If ok, it then calls calcul' for the remaining empty cells list. If not, calls itself with the next value for the cell. The calls for different cells are stacked. In case of backtrack, i must re_call calcul'' with the preceding cell number, going on with its list of values, at the point it was stopped. How to write this ? Thanks for your help. Didier

2 1

QuickCheck 2 entering infinite loop
by Dominic Mulligan 22 Jan '10

22 Jan '10

Dear all, I'm trying to work out how to use QuickCheck 2 (installed via apt-get from the Ubuntu repositories) and in the process keep managing to get the quickCheck function (called under GHCi 6.10.4) to enter what appears to be an infinite loop. Evidently, I'm doing something wrong ... Here's the problem: I have a module for types, and it exports a datatype called "Type". I make this an instance of Arbitrary, like so: instance (Eq a, Arbitrary a) => Arbitrary (Type a) where arbitrary = oneof [ liftM tyVar arbitrary, liftM2 tyCon arbitrary arbitrary] Here, tyVar and tyCon are two functions injecting into Types. I then write two silly properties to test whether this works. The first property: prop_InjectTypeVarFreeVar var = (freeTypeVars . tyVar) var == [tyVar var] Works fine. A call to quickCheck gives me the familiar "100 tests passed" message. The second property: prop_InjectTypeConFreeVars args = (freeTypeVars . (tyCon "Fun")) args == (concatMap freeTypeVars args) Sends quickCheck into an infinite loop of some sort. It manages to get through 5-6 tests before GHCi is brought to its knees. Before I go crazy, can anybody explain what I'm doing wrong? Many thanks in advance, Dominic

2 1

Brainfuck interpreter stack overflow
by Edgar Klerks 22 Jan '10

22 Jan '10

Hi Stephen, It parses the source fine, but with complicated programs with lots of loops -like calculating fibonacci- it fails after a while with a stack overflow. However it does produce correct output until that point. I am running it under ghci now, maybe I should try to compile it. I didn't know, I used an old version of parsec. I am using this one: http://hackage.haskell.org/packages/archive/parsec/3.0.0/doc/html/Text-Pars… Is that version ok? Thanks for your help, Edgar

2 3

testing and the culture of Haskell
by Michael Easter 22 Jan '10

22 Jan '10

Folks, A friend asked me about Test-Driven Development (TDD) within the FP community. I realize the FP community is larger than a Haskell mailing list, but I wanted to get a sense from this camp. I'm a fan of Haskell but I can't say that I know the culture yet. That said, I'm writing as *a fan* and not a critic. These are genuine, earnest questions. Q: Is TDD advocated the Haskell community? Is it controversial? Is it even on the radar? Q: If TDD is not advocated: why? Is there something about the Zen of Haskell development that is an impedance mismatch with TDD? Q: Note that TDD and "writing tests" are different things. With respect to "writing tests", I know that HUnit exists and that RWH has a chapter on quality assurance. Given that, I'd like to know: how widely is HUnit used? If you were to start a new Haskell project, would you include HUnit (a) immediately (b) eventually (c) maybe (d) another adjective ? sincerely Michael Easter -- ---------------------- Michael Easter http://codetojoy.blogspot.com -> Putting the thrill back in blog http://twitter.com/patentlyfalse -> Satirical tech headlines (and nothing but) http://youtube.com/ocitv -> Fun people doing serious software engineering

10 15

problems using bytestrings
by Joe Van Dyk 22 Jan '10

22 Jan '10

Hello, I wrote a function that finds anagrams in a file. It worked great. Until I tried to use Bytestrings to get better performance. Here's the code: (http://github.com/joevandyk/haskell/blob/aa61a58e6a027dda60a32ae64ec99f92d0…) import qualified Data.Map as Map import Data.Ord import Data.List import qualified Data.ByteString.Char8 as BS -- what's the type here? I get an infinite type error anagrams :: Ord a => [a] -> [a] anagrams words = sorted_anagrams where sorted_anagrams = sortBy (flip $ comparing length) get_anagrams get_anagrams = Map.elems $ foldl' insert_word Map.empty words insert_word map word = Map.insertWith' (++) (sort word) [word] map main = do -- original code, worked fine: -- input <- getContents -- print $ take 3 $ anagrams $ lines input -- new code with bytestring has errors input <- BS.getContents print $ take 3 $ anagrams $ BS.lines input There are two errors. One: anagram.hs:7:0: Occurs check: cannot construct the infinite type: a = [a] When generalising the type(s) for `anagrams' That happens when I add the type to the anagrams method. If I don't have a type specified, then I get this error: anagram.hs:21:30: Couldn't match expected type `[a]' against inferred type `BS.ByteString' Expected type: [[a]] Inferred type: [BS.ByteString] In the second argument of `($)', namely `BS.lines input' In the second argument of `($)', namely `anagrams $ BS.lines input' I'm lost here. Help! -- Joe Van Dyk http://fixieconsulting.com

2 4

Function nesting
by Zbigniew Stanasiuk 22 Jan '10

22 Jan '10

Hi all, I've just started learning Haskell and I have no idea how to nest function in following structure: Mod(5*Mod(4*Mod(3*Mod(2*Mod(1, m), m), m), m), m) ... etc. Could someone help me. Regards, Zbig

4 6

Brainfuck interpreter stack overflow
by Edgar Klerks 21 Jan '10

21 Jan '10

Hello, I just started using haskell and found it many uses for it (mainly for scripting purposes at the moment). Now, I have written a brainfuck parser and interpreter in haskell, but it produces a stack overflow if the program runs too long and I don't understand why. I thought I made the interpreter loop tail recursive, which I understood is the most common cause of a stack overflow. Can someone help my find my fault? I somehow miss something. I added the program as attachment. Thanks for your help. With kind regards, Edgar Klerks

3 4

Cannot rebuild GHC 6.12.1 due to Cabal type conflict
by James Britt 21 Jan '10

21 Jan '10

Hey all. I wanted to rebuild GHC 6.12.1 from source (a downloaded tarball). After the initial install I went and updated Cabal (from a tarball grabbed from Hackage). When I now try to do a rebuild of GHC, I get this error compiler/main/Packages.lhs:233:63: Couldn't match expected type `InstalledPackageInfo_ String' against inferred type `Cabal-1.8.0.2:Distribution.InstalledPackageInfo.InstalledPackageInfo_ m' Expected type: [InstalledPackageInfo_ String] Inferred type: [Cabal-1.8.0.2:Distribution.InstalledPackageInfo.InstalledPackageInfo_ m] In the second argument of `map', namely `conf' In the first argument of `return', namely `(map installedPackageInfoToPackageConfig conf)' make[1]: *** [compiler/stage1/build/Packages.o] Error 1 make[1]: *** Waiting for unfinished jobs.... make: *** [all] Error 2 (also here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=16380#a16380) I'm running the build like this: make distclean sh boot ./configure --enable-shared make -j 2 but (I'm guessing) it's looking at the already-installed Cabal libs and not liking what it's getting. Any ideas on how to get past this? Thanks, James Britt -- www.jamesbritt.com - Playing with Better Toys www.ruby-doc.org - Ruby Help & Documentation www.rubystuff.com - The Ruby Store for Ruby Stuff www.neurogami.com - Smart application development

1 0