August 2010 - Beginners

Monadic fixed-point combinator.
by Lyndon Maydwell 11 Aug '10

11 Aug '10

Hi beginners. I've been looking at fixed-point combinators for the purpose of memoization for a few days recently and was wondering if there is a nice way to add monadic actions to an implicitly recursive[1] function. For example: If I have fib defined like so: > fib :: (Integer -> Integer) -> Integer -> Integer > fib f 0 = 0 > fib f 1 = 1 > fib f n = f (n-1) + f (n-2) I can create an inefficient fib' using fix: > fix :: (a -> a) -> a > fix f = f (fix f) > > fib' :: Integer -> Integer > fib' = fix fib Or a memoized fib'' using memoFix and a memoization scheme: > type MFB a b = (a -> b) -> a -> b > memoFix :: MFB a b -> MFB a b -> a -> b > memoFix mem f = let mf = mem (f mf) in mf > > integer :: (Int -> b) -> Int -> b > integer f = (A.listArray (0,200) (L.map f [0..200]) A.!) > > fib'' = memoFix integer fib But would there be a way to add, say, execution tracing using an IO combinator? > ioFix :: (a -> IO a) -> IO a > fix f = print "step" >> f (fix f) I've had a play around with these functions, attempting to lift them into monadic actions, but I really have no idea how to approach this. Thanks for your help! [1] - What do you call the form of a function where recursion is implemented by a fixed point combinator?

2 1

mayBe stuck
by prad 11 Aug '10

11 Aug '10

i'm trying to create my own split function with % as delimiter. so i have eqD = (=='%') and send let s = "zaoeu%aeuasnt%staashaeu%nthdanoe%nthd" putStrLn $ show $ brS (findIndex eqD s) s to a function brS: brS i ss | isNothing i = ss | otherwise = (take i ss) : (brS newIndex newStr) where newIndex = findIndex eqD newStr newStr = drop (i+1) ss but get the following error: Couldn't match expected type `Maybe a' against inferred type `Int' In the first argument of `isNothing', namely `i' In the expression: isNothing i :: mayBe a In a stmt of a pattern guard for the definition of `brS': isNothing i :: mayBe a my understanding is that i need the isNothing because findIndex will return Just Int or Nothing. however, i'm not sure how to resolve what seems to me to be an issue between a Maybe and an Int. -- In friendship, prad ... with you on your journey Towards Freedom http://www.towardsfreedom.com (website) Information, Inspiration, Imagination - truly a site for soaring I's

7 26

Applicative Functors: Rose Trees with an alternate behavior
by Travis Erdman 11 Aug '10

11 Aug '10

> The correct implementation of pure looks like this: > > pure x = Node x (repeat (pure x)) > > (Hooray for lazy infinite data structures!) With this definition the > standard sequenceA works just fine. Ha, I would never have arrived at that solution in a million years on my own, but now that you show me, it makes perfect sense! Following the discussion of ZipLists from http://learnyouahaskell.com/functors-applicative-functors-and-monoids, my initial solution attempt was pure x = Node x (repeat x) but that doesn't even compile. I had suspected that I needed to make the pure tree "go down", but I couldn't see how to do it. OK, some follow-on questions if I may ... sequenceA [Tree a] now returns Tree [a], as indicated. Now, I'd also like sequenceA Tree [a] to return [Tree a]. To do that, I need to make Tree an instance of Traversable and, hence, Foldable. Here's my stab at doing that ... instance Foldable Tree where foldMap f (Node cargo subtrees) = f cargo `mappend` foldMap (foldMap f) subtrees instance Traversable Tree where traverse f (Node cargo subtrees) = Node <$> f cargo <*> traverse (traverse f) subtrees The Foldable code appears to be correct; at least, I can the fold the trees. "Foldable" also allows the toList Tree a to work as expected. Given that, I don't really "get" Traversable, and the code here is just my best guess as to what it should be. But, I think it must not be correct, because sequenceA Tree [a] is not returning what I think it should be returning (ie [Tree a]). Aside from this, what other things can I do with a Traversable Tree? My intuition suggests I might be able to do Scan's on a tree, say calculate a cumulative sums Tree from root to leaves (or vice versa). But I've no idea how to implement that using it's "Traversability". As of now, I have implemented this up-and-down scanning thusly ... treeScanDown :: (a -> b -> a) -> a -> Tree b -> Tree a treeScanDown f x (Node y subtrees) = Node g (fmap (treeScanDown f g) subtrees) where g = f x y treeScanUp :: (a -> [a] -> a) -> Tree a -> Tree a treeScanUp f (Node x []) = Node x [] treeScanUp f (Node x subtrees) = Node (f x (fmap fromNode g)) g where g = fmap (treeScanUp f) subtrees thanks again, travis

2 1

Why does this work in a program, but cause a seg fault in ghci?
by Kurt Häusler 11 Aug '10

11 Aug '10

Hi, I am going through the OpenGL tutorial 1 (http://www.haskell.org/haskellwiki/OpenGLTutorial1) The first example program in chapter 2 works if I compile it and run it, but I don't understand all of it so I am playing with bits of it in ghci. Look what happens: GHCi, version 6.10.4: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> let myPoints = map (\k -> (sin(2*pi*k/12),cos(2*pi*k/12),0.0)) [1..12] Prelude> myPoints [(0.49999999999999994,0.8660254037844387,0.0),(0.8660254037844386,0.5000000000000001,0.0),(1.0,6.123233995736766e-17,0.0),(0.8660254037844388,-Segmentation fault Any ideas? Thanks

4 4

Using Debug.Trace
by Patrick LeBoutillier 10 Aug '10

10 Aug '10

Hi all, I'm writing a parser for a binary format, and I'm trying to debug it since I have a bug and the code is getting lost in the bits and bytes. Basically my main is like this: import Data.Binary.Get import Debug.Trace import qualified Data.ByteString.Lazy as L main = do bytes <- L.readFile "song.gp4" let (version, bytes') = getVersion bytes putStrLn version let stuff = runGet (getDocument version) bytes' putStrLn $ show stuff return () The getVersion and getDocument functions use the Data.Binary.Get monad to decode the byte string into various objects. I tried sprinkling "trace" calls a bit everywhere and I realize they don't always get called at the expected time. Most of them are only called when I reach the "putStrLn $ show stuff" statement. Unfortunately that doesn't help me because I get a *** Exception: too few bytes. Failed reading at byte position 35939 before that. Is this happening because I'm using lazy IO to read the file? Is there a way to force the evaluation of these "trace" calls? Are there any other ways to debug this kind of stuff in Haskell? Thanks a lot, Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

3 3

Applicative Functors: Rose Trees with an alternate behavior
by Travis Erdman 10 Aug '10

10 Aug '10

The rose trees implemented in Data.Tree behave in the same way as the applicative style on lists (ie all possible combinations/permutations). I need a different behavior: one-to-one application. So, using the Data.Tree code, if I start with this tree: *Main Data.Traversable> putStrLn $ drawTree (fmap show temp2) 1 | +- 2 | `- 3 and then try this: *Main Data.Traversable> putStrLn $ drawTree (fmap show $ sequenceA [temp2,temp2]) [1,1] | +- [1,2] | +- [1,3] | +- [2,1] | | | +- [2,2] | | | `- [2,3] | `- [3,1] | +- [3,2] | `- [3,3] It gives all the combinations/permutations. I need this: *Main Data.Traversable> putStrLn $ drawTree (fmap show $ seqA [temp2,temp2]) [1,1] | +- [2,2] | `- [3,3] But then only way I could get that result was to (re-)write my own sequenceA function (called it seqA), which I suspect shouldn't be necessary. If I use the built-in sequenceA, I get (only) this: *Main Data.Traversable> putStrLn $ drawTree (fmap show $ sequenceA [temp2,temp2]) [1,1] Here's my code: data Tree a = Node {fromNode :: !a, fromNodeForest :: !(Forest a)} deriving (Show, Eq) type Forest a = [Tree a] zipWithForest = zipWith emptyForest = [] instance Functor Tree where fmap f (Node x subtrees) = Node (f x) (fmap (fmap f) subtrees) instance Applicative Tree where pure x = Node x emptyForest (<*>) (Node f tfs) (Node cargo subtrees) = Node (f cargo) (zipWithForest (<*>) tfs subtrees) seqA :: (Applicative f) => [f a] -> f [a] seqA (x:xs) = foldr (liftA2 (:)) (fmap (const []) x) (x:xs) I think I've got something wrong in how I've defined the Applicative Functor methods, and "cheating" by writing a custom sequenceA function to work around the deficiency. What is the proper fix? thanks again, travis

2 1

Fwd: [Haskell-beginners] Optimization Problem
by 200901104＠daiict.ac.in 09 Aug '10

09 Aug '10

You were right. I have changed the code to distance' :: Point → Point → Double distance' (x1, y1) (x2, y2) = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) inDisc :: Disc → Point → Bool inDisc (Disc r p1 _) p2 = (distance' p1 p2) ≤ r*r There was not any performance improvement by changing ** to ^. Why is * faster that **2 or ^2? Note: The change reduced run time to 1.24 sec. ----- Original Message ----- From: "Brent Yorgey" <byorgey(a)seas.upenn.edu> To: beginners(a)haskell.org Sent: Monday, August 9, 2010 3:14:43 PM Subject: Re: [Haskell-beginners] Optimization Problem I don't know all that much about profiling/optimization. But one simple thing occurs to me -- does it help to change inDisc to inDisc (Disc r p1 _) p2 = (distsqr p1 p2) <= r*r distsqr :: Point -> Point -> Double distsqr (x1, y1) (x2, y2) = (x1 - x2)^2 + (y1 - y2)^2 Then you avoid using sqrt. Also there's no need to use ** since you are taking a positive integral power. (^2) will optimize to just a single multiplication, whereas I have no idea what (**2) does, it's probably much slower. You could even store the square of the radius in Disc, then you also avoid having to compute r*r every time. -Brent On Mon, Aug 09, 2010 at 01:16:54PM +0530, 200901104(a)daiict.ac.in wrote: > Optimization Problem > > I am trying to make an algorithm which solves Smallest circle problem( http ://en. wikipedia .org/ wiki /Smallest_circle_problem). > My code takes ~3.2 sec to solve ~500 data sets of 2000 points apiece. I need it to be done in less than 1 sec. > After profiling it seems that ~1.76 (55%) sec goes to the inDisc function and ~1 (32%) sec goes into gcnts . So I am trying > to optimize these parts of the code. > > -- is the point p2 is inside disc? > inDisc :: Disc -> Point -> Bool > inDisc (Disc r p1 _) p2 = (distance p1 p2) <= r > > -- gives the double values in one line > gcnts :: IO [Double] > gcnts = do > line <- getLine > return (map read (words line)) > > And data and point are > > -- (x, y) > type Point = (Double, Double) > > - radius, center, know points in the disc > data Disc = Disc Double Point [Point] > deriving (Show) > > The relevant profiler part: > COST CENTRE MODULE %time % alloc > > inDisc Main 55.0 0.0 > gcnts Main 32.5 58.1 > > individual inherited > COST CENTRE MODULE no. entries %time % alloc %time % alloc > inDisc Main 247 1237577 35.6 0.0 35.6 0.0 > inDisc Main 244 527216 11.9 0.0 11.9 0.0 > inDisc Main 241 214076 7.5 0.0 7.5 0.0 > gcnts Main 235 8043 31.3 58.1 31.3 58.1 > gcnts Main 233 10 1.3 0.0 1.3 0.0 > gcnts Main 231 1 0.0 0.0 0.0 0.0 > > I have attached my code and profiler output. > > BSRK Aditya . > import Data.List > > type Point = (Double, Double) > data Disc = Disc Double Point [Point] > deriving (Show) > > getRad :: Disc -> Double > getRad (Disc r _ _) = r > > getPoints :: Disc -> [Point] > getPoints (Disc _ _ ps) = ps > > getCen :: Disc -> Point > getCen (Disc _ p _) = p > > midpoint :: Point -> Point -> Point > midpoint (x1, y1) (x2, y2) = ((x1+x2)/2, (y1+y2)/2) > > distance :: Point -> Point -> Double > distance (x1, y1) (x2, y2) = sqrt((x1 - x2)**2 + (y1 - y2)**2) > > inDisc :: Disc -> Point -> Bool > inDisc (Disc r p1 _) p2 = (distance p1 p2) <= r > > appendPoint :: Disc -> Point -> Disc > appendPoint (Disc r p ps) p2 = (Disc r p (p2:ps)) > > circumCenter :: Point -> Point -> Point -> Point > circumCenter (ax, ay) (bx, by) (cx, cy) > = (((ay**2+ax**2)*(by-cy)+(by**2+bx**2)*(cy-ay)+(cy**2+cx**2)*(ay-by))/d, > ((ay**2+ax**2)*(cx-bx)+(by**2+bx**2)*(ax-cx)+(cy**2+cx**2)*(bx-ax))/d) > where d = 2*(ax*(by-cy)+bx*(cy-ay)+cx*(ay-by)) > > mround x = (fromIntegral (round (100*x)))/100 > -- the real code > minDisc :: [Point] -> Disc > minDisc (p1:p2:[]) = Disc ((distance p1 p2)/2) (midpoint p1 p2) (p1:p2:[]) > minDisc (p1:p2:ps) = foldl' helper (minDisc (p2:p1:[])) ps > where helper d p > | (inDisc d p) = (appendPoint d p) > | otherwise = (minDiscwp (getPoints d) p) > minDisc _ = Disc 0 (0, 0) [] > > minDiscwp :: [Point] -> Point -> Disc > minDiscwp ps q = foldl' (helper q) (minDisc ((head ps):q:[])) (tail ps) > where helper q d p > | (inDisc d p) = (appendPoint d p) > | otherwise = (minDiscwp2 (init (getPoints d)) p q) > > minDiscwp2 :: [Point] -> Point -> Point -> Disc > minDiscwp2 ps q1 q2 = foldl' (helper q1 q2) (minDisc (q1:q2:[])) ps > where helper q1 q2 d p > | (inDisc d p) = (appendPoint d p) > | otherwise = Disc (distance cr p) cr (p:(getPoints d)) > where cr = circumCenter q1 q2 p > --IO > > solver :: Double -> [(Double, Double, Double, Double)] -> Double > solver t lst = mround(getRad (minDisc (map (h1 t) lst))) > where h1 t (ix, iy, vx, vy) = (ix+vx*t, iy+vy*t) > > gcnts :: IO [Double] > gcnts = do > line <- getLine > return (map read (words line)) > > ecase :: Double -> IO () > ecase cnt > | cnt == 0 = do return () > | otherwise = do (n:t:[]) <- gcnts > pts <- gvecs n > execute 1 (t + 1) pts > ecase (cnt - 1) > > gvecs :: Double -> IO [(Double, Double, Double, Double)] > gvecs n > | n == 0 = do return ([]) > | otherwise = do (ix:iy:vx:vy:[]) <- gcnts > nex <- gvecs (n-1) > return ((ix, iy, vx, vy):nex) > > execute :: Double -> Double -> [(Double, Double, Double, Double)] -> IO () > execute ct tt lsts > | ct == tt = do return () > | otherwise = do putStrLn (show (solver ct lsts)) > execute (ct + 1) tt lsts > > main :: IO () > main = do > (t:[]) <- gcnts > ecase t > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners _______________________________________________ Beginners mailing list Beginners(a)haskell.org http://www.haskell.org/mailman/listinfo/beginners

3 3

FastCGI error
by Wayne R 09 Aug '10

09 Aug '10

I'm trying to use Network.FastCGI with Apache2, but running into an error. I'd like to believe that the web server is configured correctly, because I can successfully view the following, compiled to <web root>/fastcgi/test.fcgi: #include <fcgi_stdio.h> int main(void){ int count = 0; while(FCGI_Accept()>=0){ printf("Content-Type: text/html\r\n"); printf("\r\n"); printf("Hello, World: %d", count++); } return 0; } Now I compile Fcgi.hs to <web root>/fastcgi/test2.fcgi: import Control.Concurrent import Network.FastCGI action :: CGI CGIResult action = do setHeader "Content-type" "text/plain" tid <- liftIO myThreadId output $ unlines [ "I am a FastCGI process!" , "Hear me roar!" , "" , show tid ] main = runFastCGIConcurrent' forkIO 10 action When I view localhost/fastcgi/test.fcgi, I get the hello world page, but attempting to view test2.fcgi shows an 'Internal Server Error" in firefox. The apache error log says: [Sun Aug 08 07:44:17 2010] [notice] Apache/2.2.14 (Ubuntu) mod_fastcgi/2.4.6 mod_lisp2/1.3.1 PHP/5.3.2-1ubuntu4.2 with Suhosin-Patch mod_ssl/2.2.14 OpenSSL/0.9.8k configured -- resuming normal operations [Mon Aug 09 11:11:23 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test.fcgi" started (pid 20354) [Mon Aug 09 11:11:27 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20360) [Mon Aug 09 11:11:31 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20365) [Mon Aug 09 11:11:34 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20371) [Mon Aug 09 11:11:37 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20375) [Mon Aug 09 11:11:40 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20379) [Mon Aug 09 11:11:43 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20383) [Mon Aug 09 11:11:46 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20387) [Mon Aug 09 11:11:49 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20391) [Mon Aug 09 11:11:52 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20395) [Mon Aug 09 11:11:55 2010] [warn] FastCGI: scheduled the start of the last (dynamic) server "/var/www/fastcgi/test2.fcgi" process: reached dynamicMaxClassProcs (10) [Mon Aug 09 11:11:55 2010] [warn] FastCGI: (dynamic) server "/var/www/fastcgi/test2.fcgi" started (pid 20399) [Mon Aug 09 11:12:01 2010] [error] [client 127.0.0.1] FastCGI: comm with (dynamic) server "/var/www/fastcgi/test2.fcgi" aborted: (first read) idle timeout (30 sec) [Mon Aug 09 11:12:01 2010] [error] [client 127.0.0.1] FastCGI: incomplete headers (0 bytes) received from server "/var/www/fastcgi/test2.fcgi" I've tried Fcgi.hs with two different sample FastCGI programs with the same results. Any suggestions? Wayne

1 0

Please take the State of Haskell, 2010 survey
by Johan Tibell 09 Aug '10

09 Aug '10

Hi all, I've put together a quick, 9-question State of Haskell, 2010 survey: http://blog.johantibell.com/2010/08/state-of-haskell-2010-survey.html The survey will hopefully give us some insight into how people use Haskell and perhaps also some ideas on how Haskell tools and libraries could be improved. P.S. Please direct replies to this email to haskell-cafe(a)haskell.org. Cheers, Johan

1 1

Optimization Problem
by 200901104＠daiict.ac.in 09 Aug '10

09 Aug '10

Optimization Problem I am trying to make an algorithm which solves Smallest circle problem( http ://en. wikipedia .org/ wiki /Smallest_circle_problem). My code takes ~3.2 sec to solve ~500 data sets of 2000 points apiece. I need it to be done in less than 1 sec. After profiling it seems that ~1.76 (55%) sec goes to the inDisc function and ~1 (32%) sec goes into gcnts . So I am trying to optimize these parts of the code. -- is the point p2 is inside disc? inDisc :: Disc -> Point -> Bool inDisc (Disc r p1 _) p2 = (distance p1 p2) <= r -- gives the double values in one line gcnts :: IO [Double] gcnts = do line <- getLine return (map read (words line)) And data and point are -- (x, y) type Point = (Double, Double) - radius, center, know points in the disc data Disc = Disc Double Point [Point] deriving (Show) The relevant profiler part: COST CENTRE MODULE %time % alloc inDisc Main 55.0 0.0 gcnts Main 32.5 58.1 individual inherited COST CENTRE MODULE no. entries %time % alloc %time % alloc inDisc Main 247 1237577 35.6 0.0 35.6 0.0 inDisc Main 244 527216 11.9 0.0 11.9 0.0 inDisc Main 241 214076 7.5 0.0 7.5 0.0 gcnts Main 235 8043 31.3 58.1 31.3 58.1 gcnts Main 233 10 1.3 0.0 1.3 0.0 gcnts Main 231 1 0.0 0.0 0.0 0.0 I have attached my code and profiler output. BSRK Aditya .

2 2