- Haskell-Cafe - Haskell.org

Large, numerical calculations in Haskell
by Emil Hedevang 12 Dec '12

12 Dec '12

Hi Haskell Cafe, I need to perform very large numerical computations requiring tens of GB of memory. The computations consist essentially of generation of random numbers and discrete convolutions of large arrays of random numbers with somewhat smaller kernel arrays. Should I use Haskell and call some C libraries when necessary? Should I just write everything in C? Or should I use e.g. Chapel (chapel.cray.com)? To be more specific, a very large array X is filled with random numbers drawn independently from some distribution. Then, the discrete convolution Y = K * X of X with a somewhat smaller kernel array K is calculated. Typical sizes of X and K could be 1000 x 1000 x 1000 and 100 x 100 x 100, respectively. The storage of X alone requires 8 GB of memory. Luckily I have recently been blessed with a well-equipped workstation with 128 GB RAM and two 8-core Xeon E5-2650 running at 2.0 GHz. I see immediate opportunities for parallelism. Firstly, parallel random number generators could be employed to populate the array X (e.g. SPRNG). Secondly, since the size of the kernel K is much smaller than the size of the array X, the discrete convolution can split into several smaller convolutions (see e.g. Kim and Strintzis (1980)). Finally, the discrete convolutions can be computed efficiently using Fourier methods (using e.g. FFTW). It seems fairly straightforward to implement it all in C, perhaps with some OpenMP pragmas scattered around in the code, since the heavy numerics would be performed in preexisting libraries (SPRNG and FFTW), I would like to use Haskell, since I like Haskell and find it tremendously fascinating, but I will not use it for the sake of just using it. I am willing to pay a small price in terms of performance, say, twice the run time, if I in turn will get more convenience and less suffering while coding. Therefore, would you claim it to be feasible to use Haskell? I suppose it very much depends on the quality of the Haskell FFI bindings to parallel random number generators and fast Fourier transforms. Unfortunately, I find it difficult to assess these qualities. Best regards, Emil Hedevang

3 3

How is default method signatures supposed to be used together with Generics
by Johan Tibell 12 Dec '12

12 Dec '12

Hi, I noticed that you're not required to export the types mentioned in the default method signature. For example, you could have: default hashWithSalt :: (Generic a, GHashable (Rep a)) => Int -> a -> Int hashWithSalt salt = ghashWithSalt salt . from and not export the GHashable class. However, if users try to define an instance of Hashable but forget to derive Generic: data Foo a = Foo a String deriving (Eq) -- Oops, forgot Generic here instance (Hashable a) => Hashable (Foo a) they get a pretty bad error message: Test.hs:10:10: Could not deduce (Generic (Foo a), Data.Hashable.Class.GHashable (GHC.Generics.Rep (Foo a))) arising from a use of `Data.Hashable.Class.$gdmhashWithSalt' from the context (Hashable a) bound by the instance declaration at Test.hs:10:10-41 Possible fix: add (Generic (Foo a), Data.Hashable.Class.GHashable (GHC.Generics.Rep (Foo a))) to the context of the instance declaration or add instance declarations for (Generic (Foo a), Data.Hashable.Class.GHashable (GHC.Generics.Rep (Foo a))) In the expression: (Data.Hashable.Class.$gdmhashWithSalt) In an equation for `hashWithSalt': hashWithSalt = (Data.Hashable.Class.$gdmhashWithSalt) In the instance declaration for `Hashable (Foo a)' Exporting GHashable would help a little bit in that users would at least know what this GHashable class that the error talks about is. What's best practice? -- Johan

3 4

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 12 Dec '12

12 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