December 2012 - Haskell-Cafe

Profiling slow multiplication of elements read from vector
by Richard Janis Beckert 12 Dec '12

12 Dec '12

Hello everybody! For testing purposes, I punched down a small program which... + puts 2^n elements into an unmutable vector (fromList); + generates a random index in the vector (using random-mersenne); + reads the value at the index i and at i+{-2,-1,1,2} and makes product of these values (making sure the indices stay within the boundary of the vector using `mod 2^n'); + makes a new vector with the product replacing the element at the index; + repeats the whole process 10^7 times starting from the random index. Now, after enforcing a minimum of strictness and profiling the program, I find that for some odd reason the program spends most of its time calculating the product of the read numbers! This is completely contrary to what I expected; namely, that it would spend most of the time either a) generating random numbers, b) reading the vector, or c) making a new vector. But it turns out, that reading the vector or indeed making the new one takes only a fraction of the actual time. I have attached the program and the profile to this email. Could it be that profiling assigns the Cost Centres to the wrong parts of the program? Did I overlook something crucial? Most likely the program could be implemented in a smarter way, but it's pretty close to what my actual program looks like and it shows similar behaviour. (My code, additionally, has a Boltzmann-weighed probability condition on whether the new value gets written to the vector or not.) I would be very happy for some input on this, because I am pretty new to Haskell and I don't really know how to do proper profiling. Cheers Janis (This being my first email to this mailing list, I hope I adhere to all rules of conduct out there; please tell me if I should have written this email differently or more concise.)

2 2

Predicates in data types
by Navid Hallajian 12 Dec '12

12 Dec '12

Hello, I'm a beginner in Haskell, so forgive me if this is a basic question, but I'd like to know if it's possible to have a predicate as part of a data type, so that when the data type is created, it can only be done if it satisfies the predicate else a type error is thrown. For instance, a matrix with integer elements could be modelled as [[Int]], given the restrictions that - it must have at least one column and one row (so there must be at least one list), and - every list must have the same length so that when a matrix is created, the type system wont allow it if the predicates aren't met. Thanks, Navid

3 2

Haskell Advent Calendar in Japan
by Kazu Yamamoto 12 Dec '12

12 Dec '12

Hello, This is just for your information. Haskell Advent Calendar is going on in Japanese Haskell Community: http://partake.in/events/45a01d39-af5e-42f1-91c7-e8fcc91db244 One article is evaluated lazily but other articles are in time. :-) --Kazu

1 0

ANN: diagrams-0.6
by Brent Yorgey 11 Dec '12

11 Dec '12

I am pleased to announce the release of version 0.6 of diagrams [1], a full-featured framework and embedded domain-specific language for declarative drawing. Check out the gallery [2] for examples of what it can do! [3,4] [1] http://projects.haskell.org/diagrams [2] http://projects.haskell.org/diagrams/gallery.html [3] http://mathlesstraveled.com/2012/11/05/more-factorization-diagrams/ [4] http://projects.haskell.org/diagrams/gallery/PythagoreanTree.html Highlights of this release include: - Diagrams now comes with a native-Haskell SVG backend [5] by default. If you were holding off on trying diagrams because you couldn't install cairo, you no longer have an excuse! - Proper support for subdiagrams: previous versions of diagrams-core had a mechanism for associating names with a pair of a location and an envelope. Now, names are associated with actual subdiagrams (including their location and envelope, along with all the other information stored by a diagram). This enables cool techniques like constructing a diagram in order to position its subelements and then taking it apart again, or constructing animations via keyframing. - Traces: in addition to an envelope, each diagram now stores a "trace", which is like an embedded raytracer: given any ray (represented by a base point and a vector), the trace computes the closest point of intersection with the diagram along the ray. This is useful for determining points on the boundary of a diagram, e.g. when drawing arrows between diagrams. - The core data structure underlying diagrams has been completely refactored and split out into its own separate package, dual-tree [6]. - Support for GHC 7.6. - Many more new features, bug fixes, and improvements! See the release notes [7] for complete details, and the diagrams wiki [8] for help migrating from 0.5 to 0.6. [5] http://hackage.haskell.org/package/diagrams%2Dsvg [6] http://hackage.haskell.org/package/dual%2Dtree [7] http://projects.haskell.org/diagrams/releases.html Try it out ---------- For the truly impatient: cabal install diagrams Diagrams is supported under GHC 7.0 through 7.6, with the exception that the cairo and gtk backends do not build under GHC 7.0 (but the SVG backend does), and the gtk backend does not build under GHC 7.6. To get started with diagrams, read the quick tutorial [9], which will introduce you to the fundamentals of the framework. For those who are less impatient and want to really dig in and use the power features, read the user manual [10]. [8] http://www.haskell.org/haskellwiki/Diagrams/Migrate0.6 [9] http://projects.haskell.org/diagrams/tutorial/DiagramsTutorial.html [10] http://projects.haskell.org/manual/diagrams-manual.html Get involved ------------ Subscribe to the project mailing list [11], and/or come hang out in the #diagrams IRC channel on freenode.org for help and discussion. Make some diagrams. Fix some bugs [12]. Submit your cool examples for inclusion in the gallery [13] or your cool code for inclusion in the diagrams-contrib [14] package! [11] http://groups.google.com/group/diagrams-discuss [12] http://github.com/diagrams/ [13] http://projects.haskell.org/diagrams/gallery.html [14] http://hackage.haskell.org/package/diagrams%2Dcontrib Happy diagramming! Brought to you by the diagrams team: - Michael Sloan - Ryan Yates - Brent Yorgey with contributions from: - Sam Griffin - Niklas Haas - Peter Hall - Claude Heiland-Allen - Deepak Jois - John Lato - Felipe Lessa - Chris Mears - Ian Ross - Vilhelm Sjöberg - Jim Snavely - Luite Stegeman - Kanchalai Suveepattananont - Michael Thompson - Scott Walck

2 1

C++
by mukesh tiwari 11 Dec '12

11 Dec '12

Hello All I am trying to transform this C++ code in Haskell. In case any one interested this is solution of SPOJ <http://www.spoj.com/problems/DIEHARD/>problem. #include<cstdio> #include<iostream> #include<cstring> using namespace std; int memo[1100][1100] ; int recurse( int h , int a , int cnt , bool flag ) { if ( h <= 0 || a <= 0 ) return cnt ; if ( memo[h][a] ) return memo[h][a] ; if ( flag ) memo[h][a] = recurse ( h + 3 , a + 2 , cnt + 1 , !flag ) ; else memo[h][a] = max ( memo[h][a] , max ( recurse ( h - 5 , a - 10 , cnt + 1 , !flag ) , recurse ( h - 20 , a + 5 , cnt + 1 , !flag ) ) ) ; return memo[h][a]; } int main() { int n , a , b ; scanf( "%d", &n ); for(int i = 0 ; i < n ; i++) { memset ( memo , 0 , sizeof memo ) ; scanf("%d%d", &a , &b ); printf("%d\n" , recurse( a , b , -1 , 1 )); if( i != ( n - 1 ) ) printf("\n"); } } I am stuck with that memo[1100][1100] is global variable so I tried to solve this problem using state monad ( Don't know if its correct approach or not ) but it certainly does not seem correct to me. Till now I came up with code. Could some one please tell me how to solve this kind of problem ( Generally we have a global variable either multi dimensional array or map and we store the best values found so far in the table ). import qualified Data.Map.Strict as SM import Control.Monad.State {-- funsolve_WF :: Int -> Int -> Int -> Int funsolve_WF h a cnt | h <= 0 || a <= 0 = cnt | otherwise = funsolve_Air h a ( cnt + 1 ) funsolve_Air :: Int -> Int -> Int -> Int funsolve_Air h a cnt = max ( funsolve_WF ( h + 3 - 5 ) ( a + 2 - 10 ) cnt' ) ( funsolve_WF ( h + 3 - 20 ) ( a + 2 + 5 ) cnt' ) where cnt' = cnt + 1 --} funSolve :: Int -> Int -> Int -> Bool -> State ( SM.Map ( Int , Int ) Int ) Int funSolve hl am cnt f | hl <= 0 && am <= 0 = return cnt | otherwise = do mp <- get case () of _| SM.member ( hl , am ) mp -> return mp SM.! ( hl , am ) | f -> do --here I have to insert the value return by function funSolve ( hl + 3 ) ( am + 2 ) ( cnt + 1 ) ( not f ) to map whose key is ( hl , am ) let k = evalState ( funSolve ( hl + 3 ) ( am + 2 ) ( cnt + 1 ) ( not f ) ) mp modify ( SM.insert ( hl , am ) k ) | otherwise -> do do let k_1 = evalState ( funSolve ( hl - 5 ) ( am - 10 ) ( cnt + 1 ) ( not f ) ) mp k_2 = evalState ( funSolve ( hl - 20 ) ( am + 5 ) ( cnt + 1 ) ( not f ) ) mp k_3 = mp SM.! ( hl , am ) modify ( SM.insert ( hl , am ) ( maximum [ k_1 , k_2 , k_3 ] ) ) Regards Mukesh Tiwari

3 2

Moscow Haskell Users Group (MskHUG) December meeting.
by Serguey Zefirov 11 Dec '12

11 Dec '12

I would like to announce MskHUG December meeting and invite everyone interested. The meeting will take place December 13th, 20:00 to 23:30 in the nice conference center in centre of Moscow: http://www.nf-conference.ru/ The meeting's agenda is to start more intense discussions. Most probably, there will be a couple of short presentations - I can tell about creating fast Haskell programs to handle large data to start the discussion. I will bring white paper and pencils for everyone to write and draw, there will be projector and screen and also tea, cofee and snacks. If you want to participate, please, email me.

5 4

GHCi + FFI + global C variables
by Nils 11 Dec '12

11 Dec '12

I'm currently working with a C library that needs to use/modify global C variables, for example: igraph_bool_t igraphhaskell_initialized = 0; int igraphhaskell_initialize() { if (igraphhaskell_initialized != 0) { printf("C: Not initializing. igraphhaskell_initialized = %i\n", igraphhaskell_initialized); return 1; } // initialization } If I compile an example programm using this library everything works fine, but if I try to run the same program in GHCi it dies with the message C: Not initializing. igraphhaskell_initialized = -907777 The value (and apparently the adress of the global variable) is completly off, and I have no idea what is causing this or how to solve this issue and make the library GHCi-friendly. Is it possible to run this code in GHCi at all? Also, since it's a foreign library I obviously cannot just change the C code to simply not use any global variables at all. - Nils

5 4

Variable-arity zipWith (re)invented.
by Takayuki Muranushi 11 Dec '12

11 Dec '12

Continued discussion from https://groups.google.com/d/topic/haskell-cafe/-e-xaCEbd-w/discussion https://groups.google.com/d/topic/haskell-cafe/kM_-NvXAcx8/discussion Thank you for all the answeres and thinkings; Here's zipWithN for general Zip functors: [1] . This, together with [2] may constitute a small hackage. A modification from Wren's idea to [1] is the use of fmap instead of repeat. I'm wondering if there are any laws for Zip functors. I first thought that there are similarity between Zips and Applicatives, as [3] states > instance Applicative f => Zip f where > zip = liftA2 (,) However, my intuition is that zipping two arrays should result in an array of size of the same order as two, giving rise to a Zip functor law candidate: zipWith const xs $ zipWith const xs ys == zipWith const xs ys which is violated by the above statement "zip = liftA2 (,)" . [1] https://github.com/nushio3/practice/blob/master/variable-arity/ZipWithN-2.hs [2] https://github.com/nushio3/practice/blob/master/free-objects/zipf-12.hs [3] http://hackage.haskell.org/packages/archive/TypeCompose/0.9.7/doc/html/Data… -- Takayuki MURANUSHI The Hakubi Center for Advanced Research, Kyoto University http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

3 4

mtl: Why there is "Monoid w" constraint in the definition of class MonadWriter?
by Petr P 10 Dec '12

10 Dec '12

The class is defined as > class (Monoid w, Monad m) => MonadWriter w m | m -> w where > ... What is the reason for the Monoid constrait? It seems superfluous to me. I recompiled the whole package without it, with no problems. Of course, the Monoid constraint is necessary for most _instances_, like in > instance (Monoid w, Monad m) => MonadWriter w (Lazy.WriterT w m) where > ... but this is a different thing - it depends on how the particular instance is implemented. I encountered the problem when I needed to define an instance where the monoidal structure is fixed (Last) and I didn't want to expose it to the user. I wanted to spare the user of of having to write Last/getLast everywhere. (I have an instance of MonadWriter independent of WriterT, its 'tell' saves values to a MVar. Functions 'listen' and 'pass' create a new temporary MVar. I can post the detail, if anybody is interested.) Would anything break by removing the constraint? I think the type class would get a bit more general this way. Thanks for help, Petr Pudlak

7 14

cabal configure && cabal build && cabal install
by Albert Y. C. Lai 10 Dec '12

10 Dec '12

Among many programmers, and/or users who manually unpack source tarball before installing, this idiom is very common: cabal configure cabal build cabal install This idiom is an urban legend, i.e., a popular error. "cabal install" re-does the "configure" and the "build" steps, among other things. That it has not caused trouble for you so far is only because: 1. "configure" has been idempotent, so far 2. the 2nd "build" has not caused duplicate work because ghc knows when not to re-compile One day, you will run into a surprise, because you will add some flags to "configure", and then... cabal configure --prefix=/nondefault --enable-shared cabal build cabal install Whee! Your laborously entered flags are lost on deaf ears. You get the default prefix, and you get the default disable-shared. Why? Because "cabal install" re-does the "configure" step, but this time, since you give no flags to "install", you give no flags to the 2nd "configure" either. If you begin with "cabal configure", the correct idiom is: cabal configure [flags] cabal build [cabal haddock, if you want] cabal copy cabal register If you find it too long, why not just begin with: cabal install [flags] [--enable-documentation, if you want]

6 9