September 2013 - Haskell-Cafe

Proposal: Partitionable goes somewhere + containers instances
by Ryan Newton 30 Sep '13

30 Sep '13

<subject change> On Sun, Sep 29, 2013 at 3:31 AM, Mike Izbicki <mike(a)izbicki.me> wrote: > I've got a Partitionable class that I've been using for this purpose: > > https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/Cons… > Mike -- Neat, that's a cool library! Edward -- ideally, where in the standard libraries should the Partitionable comonoid go? Btw, I'm not sure what the ideal return type for comappend is, given that it needs to be able to "bottom out". Mike, our partition function's list return type seems more reasonable. Or maybe something simple would be this: *class Partitionable t where* * partition :: t -> Maybe (t,t)* That is, at some point its not worth splitting and returns Nothing, and you'd better be able to deal with the 't' directly. So what I really want is for the *containers package to please get some kind of Partitionable instances! * Johan & others, I would be happy to provide a patch if the class can be agreed on. This is important because currently the balanced tree structure of Data.Set/Map is an *amazing and beneficial property* that is *not* exposed at all through the API. For example, it would be great to have a parallel traverse_ for Maps and Sets in the Par monad. The particular impetus is that our new and enhanced Par monad makes extensive use of Maps and Sets, both the pure, balanced ones, and lockfree/inplace ones based on concurrent skip lists: http://www.cs.indiana.edu/~rrnewton/haddock/lvish/ Alternatively, it would be ok if there were a "Data.Map.Internal" module that exposed the Bin/Tip, but I assume people would rather have a clean Partitionable instance... Best, -Ryan On Sun, Sep 29, 2013 at 3:31 AM, Mike Izbicki <mike(a)izbicki.me> wrote: > I've got a Partitionable class that I've been using for this purpose: > > > https://github.com/mikeizbicki/ConstraintKinds/blob/master/src/Control/Cons… > > The function called "parallel" in the HLearn library will automatically > parallelize any homomorphism from a Partionable to a Monoid. I > specifically use that to parallelize machine learning algorithms. > > I have two thoughts for better abstractions: > > 1) This Partitionable class is essentially a comonoid. By reversing the > arrows of mappend, we get: > > comappend :: a -> (a,a) > > By itself, this works well if the number of processors you have is a power > of two, but it needs some more fanciness to get things balanced properly > for other numbers of processors. I bet there's another algebraic structure > that would capture these other cases, but I'm not sure what it is. > > 2) I'm working with parallelizing tree structures right now (kd-trees, > cover trees, oct-trees, etc.). The real problem is not splitting the > number of data points equally (this is easy), but splitting the amount of > work equally. Some points take longer to process than others, and this > cannot be determined in advance. Therefore, an equal split of the data > points can result in one processor getting 25% of the work load, and the > second processor getting 75%. Some sort of lazy Partitionable class that > was aware of processor loads and didn't split data points until they were > needed would be ideal for this scenario. > > On Sat, Sep 28, 2013 at 6:46 PM, adam vogt <vogt.adam(a)gmail.com> wrote: > >> On Sat, Sep 28, 2013 at 1:09 PM, Ryan Newton <rrnewton(a)gmail.com> wrote: >> > Hi all, >> > >> > We all know and love Data.Foldable and are familiar with left folds and >> > right folds. But what you want in a parallel program is a balanced fold >> > over a tree. Fortunately, many of our datatypes (Sets, Maps) actually >> ARE >> > balanced trees. Hmm, but how do we expose that? >> >> Hi Ryan, >> >> At least for Data.Map, the Foldable instance seems to have a >> reasonably balanced fold called fold (or foldMap): >> >> > fold t = go t >> > where go (Bin _ _ v l r) = go l `mappend` (v `mappend` go r) >> >> This doesn't seem to be guaranteed though. For example ghc's derived >> instance writes the foldr only, so fold would be right-associated for >> a: >> >> > data T a = B (T a) (T a) | L a deriving (Foldable) >> >> Regards, >> Adam >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > >

6 9

What class for splittable data / balanced-fold?
by Ryan Newton 30 Sep '13

30 Sep '13

Hi all, We all know and love Data.Foldable and are familiar with left folds and right folds. But what you want in a parallel program is a balanced fold over a tree. Fortunately, many of our datatypes (Sets, Maps) actually ARE balanced trees. Hmm, but how do we expose that? It seems like it would be nice to have a* standard class t*hat allows you to split a datatype into roughly even halves, until you get down to the leaves. This goes along with Guy Steele's argument that we should use "append lists" as primitive rather than "cons-lists", and it's why we added append-lists within the monad-par library<http://hackage.haskell.org/package/monad-par-extras-0.3.3/docs/Control-Mona…> . Does this class exist already? A random google search brought up this module by the name Data.Splittable<http://hackage.haskell.org/package/unfoldable-0.2.0/docs/Data-Splittable.ht…>, but it's not quite the right thing. Thanks, -Ryan

4 6

Vacancy Assistant Professor Software Technology Utrecht University (1, 0 fte)
by Johan Jeuring 30 Sep '13

30 Sep '13

Assistant Professor Software Technology Utrecht University (1,0 fte) Job description The division Software Systems of the Department of Information and Computing Sciences is looking for an Assistant Professor for the bachelor programmes Computing Science and Information Science and the master programmes of the department, and for research in the area of software technology. You are expected to develop an independent line of research within the field of software technology in cooperation with the other members of the division Software Systems. The tasks include: performing scientific research in the field of software systems, in particular software technology; supervising PhD students and acquiring research funding; developing and teaching courses within the bachelor and master programmes of the department; supervising internships and theses; organizational activities within the division, department or faculty. Qualifications We are looking for candidates with a PhD with expertise and experience in scientific education and research in computer science. Expertise in the fields of software technology, programming languages and typing systems, advanced programming methods, or compilers is required. Experience in academic education within a university setting is desired. You have published on the aforementioned areas in national and international conferences and / or journals. Well-developed teaching skills and command of English in speaking and writing are a requirement. Candidates who prefer part-time employment are also invited to apply by specifying the desired part-time ratio. Offer We offer a position in a dynamic environment. The position is for at most five years. The total size of the position is 100%, but part-time is possible. The salary depends on education and experience and ranges between € 2,919 (scale 10) and € ,5070 (scale 12) gross per month for a full-time appointment. Additionally, excellent secondary benefits are provided, such as 8% holiday allowance and 8.3% end of year bonus. We also offer a pension scheme, partially paid parental leave and flexible working conditions. For more information see the terms of employment. The department provides the candidate the necessary support for the arrangements of the education and research line. About the organisation Utrecht University has great ambitions for its teaching quality and study success rates. This also applies to its clear research profiles which are centred around four themes: Sustainability, Life Sciences, Youth & Identity, and Institutions. Utrecht University plays a prominent role in our society and contributes to finding the answers to topical and future societal issues. The Faculty of Science at Utrecht University comprises six departments: Biology, Pharmacy, Information and Computer Sciences, Chemistry, Mathematics and Physics and Astronomy. It has 3500 students and nearly 2000 employees, and is internationally known for its quality in research. The academic programs of the Faculty reflect developments in society and science of today. The Department of Information and Computer Science is nationally and internationally renowned for its fundamental research in computer science and information science. Its research is positioned around game technology, one of the four research themes of the Faculty of Science. The research of the department is grouped into four divisions: Software Systems, Artificial Intelligence, Virtual Worlds and Interaction Technology. The Department offers bachelor programmes in computer science and information science, and four English-language research master-programmes including Computing Science. High enrollment figures and good student ratings make the education very successful. Part of the research of the division Software Systems focuses on how programming languages, methods, and tools can be adapted to support program construction. More specifically, the research covers the following areas: programming languages and compiler construction-tools program analysis interaction analysis, error diagnosis advanced programming methods: generic programming, dependently-typed programming program testing and verification The division aims to design better programming languages and methods; to implement tools and languages that help programmers work more effectively; and to develop products and systems demonstrating the feasibility (and/or validity) of the ideas. An important application area studied in the department and the division is (serious) games. The division mainly contributes to the education in the bachelor programs information science and computer science, and to the master program Computing Science. Additional information For more information please contact Prof.dr. Johan Jeuring +31.30.253.4115 or +31.6.400.100.53, email:J.T.Jeuring@uu.nl. Apply Your application must contain a letter of motivation, your CV with publication list, teaching and research statement, and contact details of at least two references. You can respond via the application button below. The application deadline is 21/10/2013 Assistant Professor Software Technology (1,0 fte)

1 0

New Functional Programming Job Opportunities
by Functional Jobs 30 Sep '13

30 Sep '13

Here are some functional programming job opportunities that were posted recently: Senior Scala Developer for Green Building Software at Sefaira http://functionaljobs.com/jobs/8649-senior-scala-developer-for-green-buildi… Cheers, Sean Murphy FunctionalJobs.com

1 0

FFI: how to handle external dll crashes
by Miro Karpis 29 Sep '13

29 Sep '13

Please, can you help me with following: I have an external dll that I'm importing in my haskell program. In some particular cases the dll crashes. Simplified: first I need to send to dll with MethodA some parameters and then call MethodB to do some calculations on those parameters. If I didn't give enough parameters then MethodB will crash the whole dll and my Haskell application. Is there a way to handle this? Unfortunately there are no exceptions thrown from the dll. In ghci I'm getting following message: ERROR in InitNumericalSystem::initializeSystem. JuncLabel. I have tried to use "catchAny but that didn't help. c_run is my external dll method which takes 4 input parameters: catchAny :: IO a -> (SomeException -> IO a) -> IO a catchAny = Control.Exception.catch main :: IO () main = do let timeTot = []::[CDouble] timeNow = []::[CDouble] runType = 2::CInt timeTotPtr <- newArray timeTot timeNowPtr <- newArray timeNow result <- (catchAny $ c_run timeTotPtr runType timeNowPtr 0) $ \e -> do putStrLn $ "Got an exception: " ++ show e putStrLn "Returning dummy value of -1" return (-1) free timeTotPtr free timeNowPtr print result I have tried also with withAsync, and no luck tryAny :: IO a -> IO (Either SomeException a) tryAny action = withAsync action waitCatch catchAny :: IO a -> (SomeException -> IO a) -> IO a catchAny action onE = tryAny action >>= either onE return try2 :: IO () try2 = do let timeTot = []::[CDouble] timeNow = []::[CDouble] runType = 2::CInt timeTotPtr <- newArray timeTot timeNowPtr <- newArray timeNow putStrLn $ "c_run going to call c_run.." result <- catchAny (c_run timeTotPtr runType timeNowPtr 0) (const $ return (-1)) free timeTotPtr free timeNowPtr putStrLn $ "Result: " ++ show result Is there a way how I can handle this? cheers, m.

3 5

Richard Bird and the fast nub function
by Henning Thielemann 29 Sep '13

29 Sep '13

In Richard Bird's "Functional Pearls in Algorithm Design" there is chapter 10 "Removing duplicates" which is about a fast and sorting variant of 'nub'. After reading the introduction of the chapter I answered mentally "Set.toAscList . Set.fromList - next chapter please". However after the introduction eight pages follow that develop an efficient algorithm for the problem. I suspected there might be the additional difficulty of not using the standard Set type, however on page 70 the common Set API is "imported". In the final remarks of the chapter Bird writes: "A nagging doubt remains that there might be a much simpler solution to such a simply stated problem. But so far I have not been able to find one." Now I am lost. Can someone tell me, how the task differs from what "Set.toAscList . Set.fromList" does?

3 2

[ANN] New OpenCV Bindings
by Arjun Comar 29 Sep '13

29 Sep '13

Hi all, I've been hard at work on a new set of OpenCV bindings that will hopefully solve a lot of the shortcomings with previous attempts. An automatic header parser has been used to generate a full set of Haskell bindings for the C++ API, and I'm now working to create a pleasant Haskell API. The plan is to expose major functionality through pipes for two reasons: 1) OpenCV is not very referentially transparent, and so you're stuck in IO for anything non-trivial. Lazy IO is potentially problematic, and so immediate incorporation of a proper streaming library is probably best. 2) Computer vision algorithms are frequently expressed in terms of pipelines of functionality, and a pipes approach can provide a very natural API for expressing these algorithms. At this stage, I could very much use input from anyone who's interested in these bindings. I've got the basics of a library forming, but there's a ton to do and help in the form of pull requests are very very welcome. I could also use feedback on what's been done so far (especially criticisms) as well as feature requests. The current plan is to develop the pipes API for the core functionality. The plan is to provide the major functionality from core, highgui, imgproc, features2d, contrib, ml, flann, video, and objdetect as quickly as I can before trying to cover any of the more specialized parts of the API. The functions and types from these modules (baring a few major and important exceptions) are automatically translated into C wrappers and raw Haskell bindings. If there's sufficient interest in these raw bindings separately from the API I'm developing, I'll release them as a separate package on Hackage. I'm calling my project revelation for the moment because I'm bad at naming things and it was the best pun I could come up with. Github: www.github.com/arjuncomar/revelation Regards, Arjun

3 10

Proposal: new function for lifting
by Thiago Negri 29 Sep '13

29 Sep '13

Everybody is claiming that using lift is a bad thing. So, I come to remedy this problem. Stop lifting, start using shinny operators like this one: (^$) :: Monad m => m a -> (a -> b -> c) -> m b -> m c (^$) = flip liftM2 Then you can do wonderful stuff and you will never read the four-letter word in your code again: \> Just 42 ^$(+)$ Nothing Nothing \> Just 10 ^$(+)$ Just 20 Just 30 \> let add = (+) \> Just 30 ^$ add $ Just 12 Just 42

4 3

Fwd: [GSoC 2013] Porting Charts to Diagrams - Final Report
by Jan Bracker 28 Sep '13

28 Sep '13

Hello everybody, I am sorry to send this a second time. Someone hinted out that I would not reach everybody on the mailing list through the Google Groups address. I should have looked a bit more thoroughly. The Google Summer of Code 2013 is over! My project to port the charts [0] library to use diagrams [1] as an alternative to cairo [2] was a full success. The project goal [3,4] was to remove cairo as a dependency and replace it with a open backend API so different technologies can be used to render charts. This was mainly necessary, because cairo is hard to install on platforms like windows or mac. Aside of that it also makes charts more flexible and opens the doors for renderings charts in different contexts. We were successful. The cairo rendering code was completely removed from the chart library and replaced by a drawing API [5] that is backend independent. The cairo rendering backend, of course, is still there and now provided as the separate package Chart-cairo [6]. In addition we implemented a second backend based on the diagrams library. It is provided in Chart-diagrams [7]. To give some more detail on the development: The backend API is now based on a deep embedding of all drawing commands in the ChartBackend monad. The sequence of drawings commands resulting from this is then interpreted by a implementing backend. We use the operational package [9] to implement the deep embedding. Implementing the cairo backend was straightforward, because the backend API was developed with the cairo API in mind. Implementing the diagrams backend was some more work. Drawing on its own is not a problem but calculating text metrics is, because it requires to access the systems font rendering capabilities most of the time. Diagrams does not offer this access for several reasons (missing backend support, unclear how API would look, etc.). You can look at the diagrams-discuss mailing list for further information on this topic. We used the SVGFonts [10] library to render fonts, because of these issues. It is independent of the used backend and uses the SVGFonts format to render fonts and calculate their metrics. Like this fonts can be preloaded and metrics can be calculated on the fly. The only downside of this approach is that its performance is not to good, because we render each glyph as a path and because the math done in diagrams is not to fast either. At least when rendering to SVG files we could improve the performance by embedding fonts into the produced SVG and by that saving to insert each glyph as a path. The API to access this is not yet on hackage but the new version will be released soon. You can look at the GitHub repository [11] if you want to access it. Along with this development I also had the change to tackle some bugs and improve the diagrams-svg [12] and SVGFonts [10] code. Everybody who is interested in the details of the development process and see every bit of what was done can check the chart or diagrams mailing list. Both contain the progress reports of the project [8]. So have a look at charts [0] and see what it can do. We also have a nice little tutorial on how to use the new backends [13]. Greets Jan [0]: https://github.com/timbod7/haskell-chart/wiki [1]: http://projects.haskell.org/diagrams/ [2]: http://hackage.haskell.org/package/cairo [3]: http://www.google-melange.com/gsoc/proposal/review/google/gsoc2013/jbracker… [4]: http://www.google-melange.com/gsoc/project/google/gsoc2013/jbracker/33001 [5]: http://hackage.haskell.org/packages/archive/Chart/1.0/doc/html/Graphics-Ren… [6]: http://hackage.haskell.org/package/Chart-cairo [7]: http://hackage.haskell.org/package/Chart-diagrams [8]: https://groups.google.com/d/topic/diagrams-discuss/S2nkxyxbtcY/discussion [9]: http://hackage.haskell.org/package/operational [10]: http://hackage.haskell.org/package/SVGFonts [11]: https://github.com/timbod7/haskell-chart/blob/master/chart-diagrams/Graphic… [12]: http://hackage.haskell.org/package/diagrams-svg [13]: https://github.com/timbod7/haskell-chart/wiki/How-to-use-backends

2 2

Munich Haskell Meeting, 2nd birthday
by Heinrich Hördegen 28 Sep '13

28 Sep '13

Dear all, I am pleased to announce that our monthly Haskell meeting is scheduled on Monday, 30th of September, 19h30 at Cafe Puck. If you plan to join, please click the button at: http://www.haskell-munich.de/dates Our monthly meetings started on Thu, 29 Sept 2011, so this will be over two years now! With hope to coninue in this nice and friendly sprit, Heinrich

1 0