July 2011 - Haskell-Cafe

Re: [Haskell-cafe] Monad for binary tree data structure
by Александр 23 Jul '11

23 Jul '11

Hello, >1) Do you really need a Monad instance for this? Only for training purposes. 2) One possibility is just have it being (Node x _ _) >>= f = f x I've already tried to do so, but i get only 1 element. Look. I have a function fillTree that's fill this binary tree. let a = fillTree 1 Empty a >>= \x -> return (x * 2) I got: Node 2 Empty Empty But i have tree with 100 elements. Thank you. Thank you.

2 1

ANNOUNCE: dbus-core 0.9
by John Millikin 23 Jul '11

23 Jul '11

================================================ D-Bus implementation for Haskell (dbus-core_0.9) ================================================ This is the first significant release to dbus-core in a while, and it contains some significant improvements to both the API and implementation. Users are advised to upgrade, as the 0.8 branch will no longer be receiving improvements or corrections. * Release announcement: https://john-millikin.com/releases/dbus-core/0.9/ * API documentation: http://hackage.haskell.org/package/dbus-core * Source code (literate PDF): https://john-millikin.com/downloads/dbus-core_0.9.pdf * Source code (tarball): https://john-millikin.com/downloads/dbus-core_0.9.tar.gz Changes in release 0.9 ====================== The biggest change in this release is that dbus-client has been merged into dbus-core. The original purpose of dbus-client (as a very high-level, often-updated support library) never materialized, and the split packaging caused issues with dependencies and versioning. The parts of dbus-client that were commonly used were moved into the DBus.Client and DBus.Client.Simple modules. Users are highly encouraged to use these modules in their applications. Other changes and improvements include: * The Array, Dictionary, and Structure types are no longer needed for most users. You can cast containers directly to corresponding standard types, such as Vector and Map. * Smart constructors for magic strings have been renamed so they're easier to read and type; for example, mkBusName is now just busName. * Support for custom transports and authentication mechanisms. * Removed some seldom-used modules, such as MatchRule and NameReservation. Their functionality has been merged into the new client modules. * Performance improvements for marshaling and unmarshaling messages. How to use the new simple client API ==================================== The new API makes calling and exporting methods very easy; take a look at these examples! Getting a list of connected clients ----------------------------------- {-# LANGUAGE OverloadedStrings #-} module Main (main) where import Data.List (sort) import DBus.Client.Simple main :: IO () main = do client <- connectSession -- Request a list of connected clients from the bus bus <- proxy client "org.freedesktop.DBus" "/org/freedesktop/DBus" reply <- call bus "org.freedesktop.DBus" "ListNames" [] -- org.freedesktop.DBus.ListNames returns a single value, which is -- a list of names. let Just names = fromVariant (reply !! 0) -- Print each name on a line, sorted so reserved names are below -- temporary names. mapM_ putStrLn (sort names) Exporting methods ----------------- {-# LANGUAGE OverloadedStrings #-} module Main (main) where import Control.Concurrent (threadDelay) import Control.Monad (forever) import DBus.Client.Simple onEcho :: String -> IO String onEcho str = do putStrLn str return str onDivide :: Double -> Double -> IO Double onDivide x y = if y == 0 then throwError "com.example.DivisionByZero" "Divided by zero" [] else return (x / y) main :: IO () main = do client <- connectSession -- Request a unique name on the bus. If the name is already -- in use, continue without it. requestName client "com.example.ExportExample" [] -- Export an example object at "/divide" export client "/divide" [ method "com.example.Echo" "Echo" onEcho , method "com.example.Math" "Divide" onDivide ] -- Wait forever for method calls forever (threadDelay 50000)

1 0

Simple GADTs, type families and type classes combination with type error.
by Serguey Zefirov 22 Jul '11

22 Jul '11

Why does GHC complains on the code below ? (I'll explain in a second a requirement to do just so) I get errors with ghc 6.12.1 and 7.0.2. --------------------------------------------------------------------------------------------------------------------- {-# LANGUAGE GADTs, TypeFamilies #-} class CPU cpu where type CPUFunc cpu data Expr cpu where EVar :: String -> Expr cpu EFunc :: CPU cpu => CPUFunc cpu -> Expr cpu class CPU cpu => FuncVars cpu where funcVars :: CPUFunc cpu -> [String] exprVars :: FuncVars cpu => Expr cpu -> [String] exprVars (EVar v) = [v] -- an offending line: exprVars (EFunc f) = funcVars f --------------------------------------------------------------------------------------------------------------------- I tried to split creation and analysis constraints. CPU required for creation of expressions, FuncVars required for analysis. It all looks nice but didn't work. (In our real code EVar is slightly more complicated, featuring "Var cpu" argument) It looks like GHC cannot relate parameters "inside" and "outside" of GADT constructor. Not that I hesitate to add a method to a CPU class, but I think it is not the right thing to do. So if I can split my task into two classes, I will feel better.

4 6

Wrong Answer in SPOJ 6044. Minimum Diameter Circle
by mukesh tiwari 22 Jul '11

22 Jul '11

Hello all This is my first post to Haskell-cafe so i am not aware of protocols here and pardon me for my stupidity . I am trying to solve this problem [ https://www.spoj.pl/problems/QCJ4 ] but getting wrong answer . I implemented the algorithm by Pr. Chrystal described here [ http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/… ] . I tested my convex hull code at this site and its accepted for problem [ http://www.spoj.pl/problems/GARDENHU ] so i think its correct but i am not sure if i have implemented Chrystal's algorithm correctly . Could some please tell me if i have implemented the algorithm correctly and if its possible then why i am getting wrong answer for this problem . In case of indentation problem [ http://ideone.com/perhE ] Thank you Mukesh Tiwari import Data.List import qualified Data.Sequence as DS import Text.Printf data Point a = P a a deriving ( Show , Ord , Eq ) data Turn = S | L | R deriving ( Show , Eq , Ord , Enum ) -- straight left right --start of convex hull http://en.wikipedia.org/wiki/Graham_scan compPoint :: ( Num a , Ord a ) => Point a -> Point a -> Ordering compPoint ( P x1 y1 ) ( P x2 y2 ) | compare x1 x2 == EQ = compare y1 y2 | otherwise = compare x1 x2 findMinx :: ( Num a , Ord a ) => [ Point a ] -> [ Point a ] findMinx xs = sortBy ( \x y -> compPoint x y ) xs compAngle ::(Num a , Ord a ) => Point a -> Point a -> Point a -> Ordering compAngle ( P x1 y1 ) ( P x2 y2 ) ( P x0 y0 ) = compare ( ( y1 - y0 ) * ( x2 - x0 ) ) ( ( y2 - y0) * ( x1 - x0 ) ) sortByangle :: ( Num a , Ord a ) => [ Point a ] -> [ Point a ] sortByangle (z:xs) = z : sortBy ( \x y -> compAngle x y z ) xs convexHull ::( Num a , Ord a ) => [ Point a ] -> [ Point a ] convexHull [ P x0 y0 ] = [ P x0 y0 ] convexHull xs = reverse . findHull [y,x] $ ys where (x:y:ys) = sortByangle.findMinx $ xs findTurn :: ( Num a , Ord a , Eq a ) => Point a -> Point a -> Point a - > Turn findTurn ( P x0 y0 ) ( P x1 y1 ) ( P x2 y2 ) | ( y1 - y0 ) * ( x2- x0 ) < ( y2 - y0 ) * ( x1 - x0 ) = L | ( y1 - y0 ) * ( x2- x0 ) == ( y2 - y0 ) * ( x1 - x0 ) = S | otherwise = R findHull :: ( Num a , Ord a ) => [ Point a ] -> [ Point a ] -> [ Point a ] findHull [x] ( z : ys ) = findHull [ z , x ] ys --incase of second point on line from x to z findHull xs [] = xs findHull ( y : x : xs ) ( z:ys ) | findTurn x y z == R = findHull ( x : xs ) ( z:ys ) | findTurn x y z == S = findHull ( x : xs ) ( z:ys ) | otherwise = findHull ( z : y : x : xs ) ys --end of convex hull --start of finding point algorithm http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/… Applet’s Algorithm findAngle :: ( Num a , Ord a , Floating a ) => Point a -> Point a -> Point a -> ( Point a , Point a , Point a , a ) findAngle u@(P x0 y0 ) v@(P x1 y1 ) t@(P x2 y2) | u == t || v == t = ( u , v , t , 10 * pi ) -- two points are same so set the angle more than pi | otherwise = ( u , v, t , ang ) where ang = acos ( ( b + c - a ) / ( 2 * sb * sc ) ) where b = ( x0 - x2 ) ^ 2 + ( y0 - y2 ) ^ 2 c = ( x1 - x2 ) ^ 2 + ( y1 - y2 ) ^ 2 a = ( x0 - x1 ) ^ 2 + ( y0 - y1 ) ^ 2 sb = sqrt b sc = sqrt c findPoints :: ( Num a , Ord a , Floating a ) => Point a -> Point a -> [ Point a ] -> ( Point a , Point a , Point a , a ) findPoints u v xs | 2 * theta >= pi = ( a , b , t , theta ) | and [ 2 * alpha <= pi , 2 * beta <= pi ] = ( a , b , t , theta ) | otherwise = if 2 * alpha > pi then findPoints v t xs else findPoints u t xs where ( a , b , t , theta ) = minimumBy ( \(_,_,_, t1 ) ( _ , _ , _ ,t2 ) - > compare t1 t2 ) . map ( findAngle u v ) $ xs ( _ , _ , _ , alpha ) = findAngle v t u --angle between v u t angle subtended at u by v t ( _ , _ , _ , beta ) = findAngle u t v -- angle between u v t angle subtended at v by u t --end of finding three points algorithm --find the circle through three points http://paulbourke.net/geometry/circlefrom3/ circlePoints :: ( Num a , Ord a , Floating a ) => Point a -> Point a - > Point a -> ( Point a , a ) --( center , radius ) circlePoints u@(P x1 y1 ) v@(P x2 y2 ) t@(P x3 y3 ) | x2 == x1 = circlePoints u t v | x3 == x2 = circlePoints v u t | otherwise = ( P x y , 2 * r ) where m1 = ( y2 - y1 ) / ( x2 - x1 ) m2 = ( y3 - y2 ) / ( x3 - x2 ) x = ( m1 * m2 * ( y1 - y3 ) + m2 * ( x1 + x2 ) - m1 * ( x2 + x3 ) ) / ( 2 * ( m2 - m1 ) ) y = if y2 /= y1 then ( ( x1 + x2 - 2 * x ) / 2 * m1 ) + ( ( y1 + y2 ) / 2.0 ) else ( ( x2 + x3 - 2 * x ) / 2 * m2 ) + ( ( y2 + y3 ) / 2.0 ) r = sqrt $ ( x - x1 ) ^2 + ( y - y1 ) ^ 2 --end of circle through three points --start of SPOJ code format::(Num a , Ord a ) => [[a]] -> [Point a] format xs = map (\[x0 , y0] -> P x0 y0 ) xs readInt ::( Num a , Read a ) => String -> a readInt = read solve :: ( Num a , Ord a , Floating a ) => [ Point a ] -> ( Point a , Point a , Point a , a ) solve [ P x0 y0 ] = ( P x0 y0 , P x0 y0 , P x0 y0 , 0 ) --in case of one point solve [ P x0 y0 , P x1 y1 ] = ( P x0 y0 , P x0 y0 , P x0 y0 , sqrt $ ( x0 - x1 ) ^ 2 + ( y0 - y1 ) ^2 ) -- in case of two points the solve xs = findPoints x y t where t@( x : y : ys ) = convexHull xs final :: ( Num a , Ord a , Floating a ) => ( Point a , Point a , Point a , a ) -> a final ( u , v , t , w ) | w == 0 = 0 | and [ u == v , v == t ] = w | otherwise = r where ( P x y , r ) = circlePoints u v t main = interact $ ( printf "%.2f\n" :: Double -> String ) . final . solve . convexHull . format . map ( map readInt . words ) . tail . lines

1 0

Haskell Parallel Digest 4
by Nicolas Wu 22 Jul '11

22 Jul '11

Parallel Haskell Digest ======================= Edition 4 2011-07-22 http://www.well-typed.com/blog/55 Hello Haskellers! It's time for the fourth edition of the Parallel Haskell Digest, bringing you a summary of the news and discussions of parallelism and concurrency in Haskell. The digest is made possible by the [Parallel GHC Project][0]. News ---------------------------------------------------------------------- * The Monad.Reader: special issue on parallelism and concurrency In the words of [The Monad Reader][6] itself: > Whether you're an established academic or have only just > started learning Haskell, if you have something to say, please > consider writing an article for The Monad.Reader! Issue 19 > will be a special issue focusing on articles related to > parallelism and concurrency, construed broadly. The submission > deadline for Issue 19 will be: Tuesday, August 16. * Threadscope Implementor's Summit The Threadscope implementor's summit was held this month at Microsoft Research, Cambridge. The summit brought together developers who are currently working with Threadscope, whether that be hacking on generating the events that are emitted by GHC for analysis in Threadscope, using the event trace that is produced for detailed profiling information, or working on improving Threadscope itself to provide better tools for parallel profile analysis. The meeting was full of ideas, and covered topics such as: adding extensions to the current eventlog format to enable additional information to be tagged to events; improving the visualisation of information in Threadscope; formalising the transitions of thread states into a finite state machine; and matching up executed code with corresponding source locations. With all this food for thought, we should expect plenty of interesting work in this area. Word of the Month ---------------------------------------------------------------------- In this issue we have two words of the month: *par* and *pseq*. Haskell provides two annotations, `par` and `pseq`, that allow the programmer to give hints to the compiler about where there are opportunities to exploit parallelism. While these annotations are not typically used directly by programmers, it is useful to understand them because they are the underlying mechanism for higher level tools such as "parallel strategies" and the Eval monad. The two combinators have the following signatures: par :: a -> b -> b pseq :: a -> b -> b While their signatures are the same, they are used to annotate different things. The `par` combinator hints to the Haskell implementation that it might be beneficial to evaluate the first argument in parallel. However, since Haskell does not impose an evaluation order, we also need `pseq`, which instructs the compiler to ensure that its first argument is evaluated before the second. Let's take a look at an example inspired by [Parallel Performance Tuning for Haskell][24] by Jones, Marlow, and Singh, which illustrates this nicely. Suppose you're interested in the sum of two expensive computations. To keep things simple, we'll use a naive implementation of `fib` (the point here isn't to have an efficient computation, I'm trying to show an *expensive* one): fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2) For a second expensive computation, we'll calculate the negafibonacci number, which works on negative numbers: negafib :: Int -> Int negafib 0 = 0 negafib (-1) = 1 negafib n = nfib (n+2) - nfib (n+1) The sum of these two can be calculated by the following sequential function: sumfib :: Int -> Int sumfib n = x + y where x = fib n y = negafib (-n) There's obvious room for improvement here when we have two cores: we simply calculate the expensive computations on separate cores. Annotating the code above is a fairly simple process. We first use `par` to annotate the fact that `x` must be calculated in parallel with the rest of the computation. Second, we ensure that `y` gets computed before `x + y` by annotating with `pseq`. The result is as follows: import Control.Parallel (par, pseq) psumfib :: Int -> Int psumfib n = x `par` (y `pseq` x + y) where x = fib n y = negafib (-n) We can write a simple program that outputs the result of running this computation with the following `main` function: main :: IO () main = putStrLn . show . sumfib $ 37 We should hope for the parallel version to work twice as fast, since the two expensive functions should take about the same time to compute. Here's the output of compiling and running the sequential version of the program: $ ghc -rtsopts Main.hs [1 of 1] Compiling Main ( Main.hs, Main.o ) Linking Main ... $ time ./Main real 0m6.113s user 0m6.090s sys 0m0.010s Now replacing `sumfib` with `psumfib` produces the following results: $ ghc -rtsopts -threaded Main.hs [1 of 1] Compiling Main ( Main.hs, Main.o ) Linking Main ... $ time ./Main +RTS -N2 real 0m3.402s user 0m6.660s sys 0m0.040s This is obviously a very trivial example, but the point is that annotations provide a powerful way of expressing parallel algorithms. It's interesting to note that for this simple program, the timings for the parallel version on a single core performs as well as the single core version compiled without threading. While annotations are a simple mechanism for expressing where parallelism might be exploited in a program, beware that there are a number of pitfalls to using this technique: all that glitters is not gold! The main difficulty in using `par` and `pseq` directly is that you really need to have a clear understanding of evaluation order. In particular, unless you understand what laziness is doing to the evaluation order, then you might find that the computations you're sparking off with `par` might not occur when you expected they should. Then there are all the general difficulties that you face with parallel programming, like getting the right granularity of work to do in parallel. Using `par` is quite lightweight so can be used to exploit reasonably fine grained parallelism, but it is certainly not free. Finally, parallel performance suffers when there are too many garbage collections, so keeping this to a minimum by either using more efficient data structures or increasing available memory, becomes an important factor. Nevertheless, it's well worth having a play with `par` and `pseq`. The next step after that is to look at parallel strategies. Strategies is a layer of abstraction on top of `par` and `pseq`. You might like to to read [Seq no more: Better Strategies for Parallel Haskell][1], by Simon Marlow et al. which describes Strategies and the Eval monad. It's all available in the [parallel library][2] on Hackage. More recently, the `Par` monad has also been introduced as yet another way of describing parallel evaluations. These key topics will no doubt feature in a future word of the month, so stay tuned! Parallel GHC Project Update ---------------------------------------------------------------------- The Parallel GHC Project is an MSR-funded project to push the real-world use of parallel Haskell. The aim is to demonstrate that parallel Haskell can be employed successfully in industrial projects. This month we're having a guest column from the team over at Los Alamos National Laboratory, one of the partners involved in the project (you can see the full details in report LA-UR 11-0341). They have been working on writing Monte Carlo physics simulations in Haskell, which has given them high levels of parallelism, along with useful tools for abstraction. So, without further ado, over to Michael Buksas from LANL: Our goal is to build highly efficient Monte Carlo physics simulations using parallel Haskell. We're focusing on SMP performance though some combination of explicit threading and pure parallel annotations. The Monte Carlo approach involves randomly sampling the space of solutions to generate data which contributes to the solution. For these physical problems, our samples are the tracks of particles as they move through space, interacting with a physical material as they go. Data collected from each particle trajectory is then combined into information needed to compute the solution. For example, the detailed information about the particle's interaction with the material is collected into a collective effect on the material properties. To date, we have a code base which includes two approaches to the problem. One is a specific and parallel-tuned application code targeting relativistic neutrino transport in stellar atmospheres. The other is building a more general environment for creating specific applications, such as this one. We recently presented to our colleagues in LANL some preliminary results on the parallel performance of the targeted application code. To give a sense of the approach to parallelization in this code, consider these high-level functions from an earlier serial version: main :: IO () main = do (n, rest) <- parseCL let tally = runMany infMesh simpleMat n writeTally "tally" tally runMany :: Mesh -> Material -> Word32 -> RNG -> Tally runMany msh mat ntot rng = let ps = genParticles ntot msh rng tallies = map (runParticle msh mat) $ ps in foldl' merge emptyTally tallies And consider the following changes for the parallel version: main :: IO () main = do (n,sz) <- parseCL let tally = feed infMesh simpleMat n sz prand writeTally "tally" tally feed :: Mesh -> Material -> Word32 -> Word32 -> RNG -> Tally feed msh mat ntot chunkSz rng | ntot <= chunkSz = runMany msh mat ntot rng | otherwise = t `par` (ts `pseq` (merge t ts)) where t = runMany msh mat chunkSz g1 ts = feed msh mat (ntot - chunkSz) chunkSz g2 (g1,g2) = split g We've wrapped function `runMany` in `feed`, which partitions the collection of generated particles into groups of size `chunkSz`, and issues these particles to `runMany` in parallel. With this simple change, we seeing upwards of 80% utilization of up to 8 cores, for a performance improvement greater than a factor of 6. We believe that performance can be further improved with different strategies for breaking down the work, and looking for additional parallelization opportunities in the collection of results. Our other branch of development is focused on finding useful abstractions and high-level functions to support programming a variety of Monte Carlo problems of this kind. We have identified a few such useful abstractions, and implemented them as type classes and type families. For example, `Space` is a general term for the physical space and imposed symmetries in which we can perform a simulation. We express this as follows: class Space s where type Position s :: * type Direction s :: * stream :: s -> Distance -> s position :: s -> Position s direction :: s -> Direction s make :: Position s -> Direction s -> s and implement specific spaces, such as one with the symmetry of the unit sphere: instance Space Spherical1D where type Position Spherical1D = Radius type Direction Spherical1D = Normalized Vector2 stream (Vector2 x y) (Distance d) = Vector2 (x+d) y position s = Radius $ vmag s direction s = normalize s make (Radius pos) dir = pos *| (normalized_value dir) This allows the specific space data types to be used in a variety of contexts. Using ordinary parametric polymorphism is also effective: -- | Stream a single particle: stream :: (p -> (e,p)) -- ^ Function to produce each step. Comes from a model. -> (e -> Bool) -- ^ Check for terminal events to stop streaming -> p -- ^ Initial particle -> [(e, p)] -- ^ Resulting list of events and particle states. stream stepper continue p = next p where next p = let (e, p') = stepper p in (e, p') : if continue e then next p' else [] The above is our high-level routine function for generating a history from a single particle, recorded as a list of (event, particle) pairs, where the event and particle data types are provided for each problem. Blogs, Papers, and Packages ---------------------------------------------------------------------- * [Fun with parallel monad comprehensions (19 July 2011)][3] This blog post by Thomas Petricek featured in the Monad Reader 18, and covers some of the interesting things that can be achieved with monad comprehensions when viewed from a parallel perspective. Along the way, he deals with examples such as the parallel composition of parsers. * [Parallelizing a nonogram solver (05 July 2011)][4] Jasper Van der Jeugt detailed his implementation of a parallel nonogram solver. Nonograms also go by the name of Paint Sudoku: the aim is to colour in a grid where a list of numbers is given for each row and column and these numbers indicate consecutive runs of filled-in squares in the corresponding row or column. For large puzzles, grids that are 20x20, Jasper reports that on a dual core machine his a parallel algorithm reduces execution by 37.9% compared to its sequential counterpart. * [The IVar monad (29 June)][5] Edward Z. Yang has written a series of posts discussing IVars, which are immutable variables which are a write-once, read-many (these are particularly handy for communicating results from a child process to its parent). Edward's post outlines the difficulties involved in defining a monad for IVars. * [Map reduce as a monad (05 July 2011)][7] Julian Porter wrote an article for The Monad Reader 18 about how MapReduce could be expressed as a monad. The MapReduce framework finds its roots in functional programming, and this is an interesting take on the problem. Mailing list discussions --------------------------------------------------------------------- * [NVIDIA's CUDA and Haskell (5 July 2011)][11] Vasili Galchin was wondering whether or not there had been any efforts to build bridges between NVIDIA's CUDA and Haskell. Don Stewart was quick to respond with a number of links to active work in the area: * [Direct access to CUDA][20] * [CUDA in Haskell][21] * [Direct access to OpenCL][22] * [The accelarate package][23] Trevor McDonell noted that the accelerate package was best accessed from the source repository on github, and that the CUDA bindings hadn't yet been tested or updated for the latest toolkit release. * [Unbelievable parallel speedup (3 June 2011)][12] While reading Simon Marlow's [tutorial][19] on parallel and concurrent programming, John Ramsdell reported some remarkable (slightly superlinear!) performance gains for one of his programs. Thomas Schilling guessed that this was due to the large variance in the figures reported, but went on to describe how it might be possible to obvserve such performance boosts due to reduced local cache misses when using several cores. Without more information about the program in question, it's difficult to do any kind of diagnosis, but nevertheless, it's great to hear about good results from a happy Haskeller! * [Automatic Reference Counting (2 July 2011)][13] After hearing about the new static analysis tools in Clang that does automatic reference counting (ARC), Thomas Davie was wondering if some compiler gurus might be able to comment on the applicability of this kind of analysis to Haskell, as an alternative to garbage collection. This led to an enlightening discussion about reference counting versus garbage collection. * [Haskell on NUMA (16 June 2011)][14] Michael Lesniak was wondering what the state of parallel performance of Haskell on Non-Uniform Memory Access (NUMA) machines was like, since he's having problems and can't find much useful information online. Nobody seems to have answered this one, are there any suggestions? * [Parallel compilation and execution? (26 May 2011)][15] Michael Rice was trying to figure out how to compile and run a simple program that outputs the result of a parallel fibonacci algorithm. After a quick reminder to use `pseq` rather than `seq` to force sequential evaluation, Daniel Fischer suggested that recompilation might be required, and that passing `--fforce-recomp` would be a good way to ensure that this occurred. Michael was also keen to know whether Control.Parallel was comparable to OpenMP. Alex Mason gave a detailed reply and gave an example of parallel mergesort as a means of comparison. * [parMap doesn't work fine (12 May 2011)][16] After just starting out with parallel computations in Haskell, Grigory Sarnitskiy ran into troubles making parMap work with lazy structures. To resolve these issues, Brandon Moore pointed to using `rdeepseq`, and Maciej Piechotka suggested `deepseq`. * [efficient parallel foldMap for lists/sequences (17 June 2011)][17] Sebastian Fischer re-posted his question about efficient parallel `foldMap` for lists to the parallel mailing list. In essence he was seeking an efficient implementation of `foldMap`, where a list is folded into a single value before a map is applied to the result. Johannes Waldmann advised against using ordinary lists, and mentioned that he was using `Data.Vector` instead. Additionally, he recommended switching to a sequential fold once a parallel fold had been used to a certain depth. Christopher Brown further confirmed that it was a good idea to spark off computations when the granularity is high enough to make it worthwhile, and also mentioned that it was best to spark computations that were evaluated to normal form. * [Wanted: parallel Haskell tutorial/talk/demonstration in Leipzig, Germany, October 7 (8 July 2011)][18] Johannes Waldmann is looking for volunteers who might be able to present at their local Haskell Workshop, and welcomes submissions on parallel and distributed computing using Haskell. The submission deadline is 20 August. Stack Overflow ---------------------------------------------------------------------- * [How to write nested loop problem using parallel strategies in Haskell][8] * [How to measure sequential and parallel runtimes of Haskell program][9] * [Poor performance / lockup with STM][10] Help and Feedback ---------------------------------------------------------------------- If you'd like to make an announcement in the next Haskell Parallel Digest, then get in touch with me, Nicolas Wu, at <parallel(a)well-typed.com>. Please feel free to leave any comments and feedback! [0]: http://www.haskell.org/haskellwiki/Parallel_GHC_Project [1]: http://research.microsoft.com/apps/pubs/default.aspx?id=138042 [2]: http://hackage.haskell.org/package/parallel [3]: http://tomasp.net/blog/comprefun.aspx [4]: http://jaspervdj.be/posts/2011-07-05-parallelizing-a-nonogram-solver.html [5]: http://blog.ezyang.com/2011/06/the-iva-monad/ [6]: http://themonadreader.wordpress.com/2011/07/11/call-for-copy-issue-19-speci… [7]: http://themonadreader.files.wordpress.com/2011/07/issue18.pdf [8]: http://stackoverflow.com/questions/6444716/how-to-write-nested-loop-problem… [9]: http://stackoverflow.com/questions/6623316/how-to-measure-sequential-and-pa… [10]: http://stackoverflow.com/questions/6439925/poor-performance-lockup-with-stm [11]: http://www.haskell.org/pipermail/haskell-cafe/2011-July/093751.html [12]: http://www.haskell.org/pipermail/haskell-cafe/2011-June/092661.html [13]: http://www.haskell.org/pipermail/haskell-cafe/2011-July/093689.html [14]: http://www.haskell.org/pipermail/haskell-cafe/2011-June/093231.html [15]: http://www.haskell.org/pipermail/haskell-cafe/2011-May/092389.html [16]: http://www.haskell.org/pipermail/haskell-cafe/2011-May/091843.html [17]: http://groups.google.com/group/parallel-haskell/t/b34d796e6672fd6b [18]: http://groups.google.com/group/parallel-haskell/t/f5f0946d0780b59b [19]: http://community.haskell.org/~simonmar/par-tutorial.pdf [20]: http://hackage.haskell.org/package/cuda [21]: http://hackage.haskell.org/package/language-c-quote [22]: http://hackage.haskell.org/package/OpenCLRaw [23]: http://hackage.haskell.org/package/accelerate [24]: http://community.haskell.org/~simonmar/papers/threadscope.pdf

1 0

Grammar hacker in Haskell
by sharadha Raghunathan 22 Jul '11

22 Jul '11

Hi all, I am new to Haskell, I need to write a grammar hacker in Haskell; that would find the first set of grammar, follow set of grammar, determine if it is in LL or not and generate a LR table. Can someone help me with the same? Any reply would be much appreciated. -- Sharadha Raghunathan

3 3

Introspection
by Patrick Browne 22 Jul '11

22 Jul '11

Is it possible to access type information and perform either of the following in a Haskell program? 1) Find the type/class of a variable e.g. a type predicate: is y of-type A, or is y of-Class A 2) Assert the type of a variable e.g. if y.length > 100 then y is of type big. Regards, Pat This message has been scanned for content and viruses by the DIT Information Services E-Mail Scanning Service, and is believed to be clean. http://www.dit.ie

5 6

Haskell Weekly News: Issue 191
by Daniel Santa Cruz 21 Jul '11

21 Jul '11

Welcome to issue 191 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of July 10 to 16, 2011. [1] http://haskell.org/ You can find the HTML (and mobile) version of the issue at: http://contemplatecode.blogspot.com/2011/07/haskell-weekly-news-issue-191.h… Announcements Brent Yorgey put out a call for articles for the next Monad.Reader, which will be focused on parallelism and concurrency. [2] http://goo.gl/Qh6na Quotes of the Week * PenguinOfDoom: Being enlightened gentlemen, we split all programming languages into two groups, sucks and doesn't-suck and put all of them into the first group. * cmccann: beta reducing the chainsaws can be tricky * kmc: edwardk measures API lifetime in hours * _Ray_: the difference in mathematical/CS knowledge of the average haskeller, and the average PHPer, is likely similar to that of the average PHPer and a banana * quicksilver: [on LYAH] by the time I read it I knew everything it was trying to teach, so I just thought "Yay! Cute caterpillar". * edwardk: shapr is the only person i know of who just decides to drive across the country with a car full of machetes * copumpkin is now known as contrapumpkin. contrapumpkin is now known as yoda. yoda is now known as coyoda. + Eduard_Munteanu: Yonoda + coedwardk: i keep reading coyoda as coyoneda + monochrom: I read it as toyota + Eduard_Munteanu: Mmm, the monad is strong in this one... + monochrom: rumours actually say that it should be toyoda but the japaneses want it easier on americans, so toyota Top Reddit Stories * The Haskell School of Music - new book being written by Paul Hudak Domain: plucky.cs.yale.edu, Score: 66, Comments: 9 On Reddit: [3] http://goo.gl/9Jjrd Original: [4] http://goo.gl/r54xG * Confusion between (.) and ($) operators Domain: self.haskell, Score: 41, Comments: 27 On Reddit: [5] http://goo.gl/eFqRj Original: [6] http://goo.gl/eFqRj * Fitter, happier, more productive UTF-8 decoding Domain: serpentine.com, Score: 35, Comments: 6 On Reddit: [7] http://goo.gl/o2REx Original: [8] http://goo.gl/dKB04 * Static Single Assignment for Functional Programmers Domain: wingolog.org, Score: 30, Comments: On Reddit: [9] http://goo.gl/13sSP Original: [10] http://goo.gl/90MEH * [GSoC] Text/UTF-8: Initial results Domain: jaspervdj.be, Score: 29, Comments: 14 On Reddit: [11] http://goo.gl/nJ4pJ Original: [12] http://goo.gl/uPkBl * Data Driven Programming in haskell - live screencast. What are your tips/suggestions? Domain: entirelysubjective.com, Score: 29, Comments: 17 On Reddit: [13] http://goo.gl/kIiX8 Original: [14] http://goo.gl/28k6p * Ur/Web is hiring: web metaprogramming with class Domain: haskell.org, Score: 28, Comments: 11 On Reddit: [15] http://goo.gl/nWf5S Original: [16] http://goo.gl/l9HhI * Monads in C++. Bartosz Milewski's Programming Cafe Domain: bartoszmilewski.wordpress.com, Score: 23, Comments: 0 On Reddit: [17] http://goo.gl/IJnVa Original: [18] http://goo.gl/Bq4Lq * The Typeable class is changing Domain: haskell.org, Score: 22, Comments: 2 On Reddit: [19] http://goo.gl/x1InO Original: [20] http://goo.gl/E2jVK * Reverse Engineering of Compiled Haskell Domain: self.haskell, Score: 18, Comments: 22 On Reddit: [21] http://goo.gl/GCrfN Original: [22] http://goo.gl/GCrfN Top StackOverflow Questions * Haskell - How to avoid typing the same context over and over again? votes: 18, answers: 3 Read on SO: [23] http://goo.gl/0h1qF * Haskell iteratee: simple worked example of stripping trailing whitespace votes: 14, answers: 1 Read on SO: [24] http://goo.gl/bYujx * Parametrised data type in Scala votes: 12, answers: 2 Read on SO: [25] http://goo.gl/4NyZw * How to organize Haskell modules with instances: stick to data type vs type class? votes: 10, answers: 1 Read on SO: [26] http://goo.gl/Tivoh * On improving Haskell's performance compared to C in fibonacci micro-benchmark votes: 10, answers: 3 Read on SO: [27] http://goo.gl/q5O8Q * Constructing a tuple (or list) from already-existing objects - what is the cost? votes: 9, answers: 2 Read on SO: [28] http://goo.gl/UuKft * Writing A Function Polymorphic In A Type Family votes: 9, answers: 1 Read on SO: [29] http://goo.gl/vPpoH * Haskell Lazy ByteString + read/write progress function votes: 9, answers: 1 Read on SO: [30] http://goo.gl/LfNEN About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz References 1. http://haskell.org/ 2. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18844 3. http://www.reddit.com/r/haskell/comments/in1my/the_haskell_school_of_music_… 4. http://plucky.cs.yale.edu/cs431/reading.htm 5. http://www.reddit.com/r/haskell/comments/ipfok/confusion_between_and_operat… 6. http://www.reddit.com/r/haskell/comments/ipfok/confusion_between_and_operat… 7. http://www.reddit.com/r/haskell/comments/im82t/fitter_happier_more_producti… 8. http://www.serpentine.com/blog/2011/07/11/fitter-happier-more-productive-ut… 9. http://www.reddit.com/r/haskell/comments/ip2de/static_single_assignment_for… 10. http://wingolog.org/archives/2011/07/12/static-single-assignment-for-functi… 11. http://www.reddit.com/r/haskell/comments/ilif5/gsoc_textutf8_initial_result… 12. http://jaspervdj.be/posts/2011-07-10-text-utf8-initial-results.html 13. http://www.reddit.com/r/haskell/comments/insp1/data_driven_programming_in_h… 14. http://entirelysubjective.com/programming/data-driven-programming-haskell-1/ 15. http://www.reddit.com/r/haskell/comments/ips56/urweb_is_hiring_web_metaprog… 16. http://www.haskell.org/pipermail/haskell-cafe/2011-July/093994.html 17. http://www.reddit.com/r/haskell/comments/imzaj/monads_in_c_bartosz_milewski… 18. http://bartoszmilewski.wordpress.com/2011/07/11/monads-in-c/ 19. http://www.reddit.com/r/haskell/comments/imm0j/the_typeable_class_is_changi… 20. http://www.haskell.org/pipermail/haskell-cafe/2011-July/093947.html 21. http://www.reddit.com/r/haskell/comments/iqz0l/reverse_engineering_of_compi… 22. http://www.reddit.com/r/haskell/comments/iqz0l/reverse_engineering_of_compi… 23. http://stackoverflow.com/questions/6706248/haskell-how-to-avoid-typing-the-… 24. http://stackoverflow.com/questions/6643495/haskell-iteratee-simple-worked-e… 25. http://stackoverflow.com/questions/6694269/parametrised-data-type-in-scala 26. http://stackoverflow.com/questions/6641105/how-to-organize-haskell-modules-… 27. http://stackoverflow.com/questions/6716315/on-improving-haskells-performanc… 28. http://stackoverflow.com/questions/6655902/constructing-a-tuple-or-list-fro… 29. http://stackoverflow.com/questions/6663547/writing-a-function-polymorphic-i… 30. http://stackoverflow.com/questions/6668716/haskell-lazy-bytestring-read-wri…

1 0

Network.CGI strangeness
by Alexander Solla 21 Jul '11

21 Jul '11

Hi Everybody, I'm having some strange issues with Network.CGI's pathInfo action, or else some other strangeness with pattern matching. My "mainCGI" CGI action is: mainCGI :: CGI CGIResult mainCGI = pathInfo >>= outputSlotTHtml . packagesPage outputSlotTHtml is irrelevant to my problem. packagesPage generates a SlotT IO Html -- Slot semantics are essentially irrelevant to my problem. But packagesPage calls a function called pathCrossRef which is having some problems: packagesPage :: WebPath -> SlotT IO Html packagesPage wp = do infos <- getPackageInfos . pathCrossRef $ wp ... pathCrossRef :: String -> String pathCrossRef "/working/" = "/development/code/haskell/working/" pathCrossRef _ = "/development/code/haskell/packages/" The intention is that when the cgi program is called with "/working/" as an argument, the pathCrossRef should point at "/development/.../working/", and when called with "/packages/" (or anything else) as an argument, pathCrossRef should point to "/development/.../packages/". But it is not working! When I visit http://localhost/working/, I end up using the "packages" cross ref. I have even printed the cgi argument to the Apache log, and the argument is "/working/". If I get rid of the wildcard pattern, I get a "missing pattern" error when I visit http://localhost/working/. Can anybody help? Thanks, Alex

1 0

ANN: boomerang and web-routes-boomerang
by Jeremy Shaw 21 Jul '11

21 Jul '11

Hello, I am pleased to announce the release of two new libraries: boomerang and web-routes-boomerang. boomerang is a library for general purpose, invertible parsing and pretty printing. It provides combinators which allow you to specify a grammar once and automatically extract a parser and pretty-printer from it. This library was refactored, with permission, from the Zwaluw library created by Sjoerd Visscher and Martijn van Steenbergen. hackage: http://hackage.haskell.org/package/boomerang quick intro: http://hackage.haskell.org/packages/archive/boomerang/1.0.0/doc/html/Text-B… web-route-boomerang provides glue code for using boomerang with web-routes. web-routes is a framework-independent, type-safe, url routing library. hackage: http://hackage.haskell.org/package/web-routes-boomerang tutorial: http://happstack.com/docs/crashcourse/WebRoutes.html#web-routes-boomerang - jeremy p.s. boomerang is similar in purpose to the inveritble-syntax library: http://hackage.haskell.org/package/invertible-syntax The libraries take different approaches and are both worth considering.

2 3