- Haskell-Cafe - Haskell.org

Deriving laws by systematic transformations
by Armando Blancas 01 Sep '11

01 Sep '11

Studying Wadler's "Comprehending Monads" and "Theorems for free!", I've been unable to derive law (iv) and I'm not sure about (iii). Will appreciate a pointer to similar examples or a massive hint. Here's my attempt at (iii): map f . unit x = map f [x] = [f x] = unit (f x) = (unit . f) x map f . unit = unit .f >From the Monads article: unit :: x -> M x join :: M (M x) -> M x For example, unit 3 = [3] and join [[1,2], [3]] = [1,2,3] (iii) map f . unit = unit . f (iv) map f . join = join . map (map f) Laws (iii) and (iv) may be derived by systematic transformations of the polymorphic types of unit and join.

1 0

Off-topic: Mathematics
by Andrew Coppin 01 Sep '11

01 Sep '11

This is fairly wildly off-topic but... does anybody know of a good forum where I can ask questions about mathematics and get authoritative answers? (Apart from "go visit the nearest university", that is.)

11 22

iOS and Haskell
by Vasili I. Galchin 01 Sep '11

01 Sep '11

Hello, I know nothing about the architecture of iOS running on an iPad. However, I have a friend who just bought the newer iPad. It seems that either C++ or Objective C is available on iPad for development(actually the icon says C++). What are the prospects of getting Haskell ported to iOS? Vasili

3 2

Parallel Haskell Digest 5
by Eric Y. Kow 31 Aug '11

31 Aug '11

Parallel Haskell Digest ======================= Edition 5 2011-08-31 Hello Haskellers! Eric here, reprising my role as Parallel Haskell Digester. Many thanks to Nick for good stewardship of the digest and nice new directions for the future. This month we have Erlang PhDs (and a postdoc), new partners, two Monad Reader articles in progress and some strategies. As usual, this digest is made possible by the [Parallel GHC Project][n0]. News ---------------------------------------------------------------------- [Scalable Erlang PostDoc and 2 PhD Studentships][n1] (8 Aug) What, Erlang?! Yes, you are reading the right digest. If you're generally into parallelism and concurrency in functional programming languages, you may be especially interested to know about this announcement from Phil Trinder. > RELEASE project - A High-level Paradigm for Reliable Large-scale > Server Software - is funded by the EU Framework 7 programme for 36 > months from October 2011. Its aim is to scale the radical > concurrency-oriented programming paradigm to build reliable > general-purpose software, such as server-based systems, on massively > parallel machines (100 000 cores). Word of the Month ---------------------------------------------------------------------- Last month, we had `par` and `pseq` as our twin words of the month. Let's pursue this little train of parallel thought; our next word the month is *strategy*. Strategies have been around since the 1993 paper [Algorithm + Strategy = Parallelism][asp]; that's before even we started using monads in Haskell! They've recently been revamped in Simon Marlow's [Seq no More][seq-nm] paper, and it's this version of strategies that we'll be exploring here. Strategies are built on top of the `par` and `pseq` primitives we saw in the [last digest][phd4]. They provide a nice way to express the often complicated logic we need to make the best use of parallelism in our code. Use of strategies can also help to make parallel code easier to read and maintain because they allow us to more cleanly separate the core logic from our code that which pertains to our use of parallelism. Before delving into strategies, let's take a small notational detour by introducing the `Eval` monad. Suppose we wanted a parallel version of the `map` function, something that would apply a function to each item of a list. Using the `par` and `pseq` from the last digest, we might express this function parMap :: (a -> b) -> [a] -> [b] parMap f [] = [] parMap f (a:as) = b `par` bs `pseq` (b:bs) where b = f a bs = parMap f as If we look carefully at the code we can observe that there is something inherently sequential in the way we have expressed this parallel computation: first spark off `f a` then recurse to the tail of the list, and finally cons. The `Eval` monad builds off the insight that expressing parallelism is fundamentally (perhaps counterintuitively) about ordering things. Monads are well-suited for expressing ordering relationships, and so they have been been pressed to work for expressing parallel computation as well. data Eval a instance Monad Eval runEval :: Eval a -> a rpar :: a -> Eval a rseq :: a -> Eval a `Eval` is just a strict identity monad, with `rpar` and `rseq` as counterparts to `par` and `pseq`. We use `Eval` to compose sequences of parallel computation, which we extract the results of by using the `runEval` function. If you're not familiar with monads, you can get away with just treating `Eval` as new notation, or rather, borrowed notation, the same that we use IO, parser combinator libraries, QuickCheck and a plethora of other useful monads. It's worth noting also that despite appearances, we are still in purely functional territory -- no IO here! -- with the notion of sequencing being limited to controlling parallelism and evaluation depth. To make use of `Eval` for our `parMap` function, we could write a version like the below. It introduces a change of type, from returning `[b]` to `Eval [b]`. In the general case, we could just use the `runEval` function to get our result back, but we are not baking it into `parMap` because we would typically want to use then function within a greater `Eval` context anyway. parMap :: (a -> b) -> [a] -> Eval [b] parMap f [] = return [] parMap f (a:as) = do b <- rpar (f a) bs <- parMap f as return (b:bs) As before, this function captures the basic idea of its sequential counterpart `map`: apply function, recurse to tail, cons new head to new tail. This is a passable parallel map, but there are still two things which are unfortunate about it. First, we have repeated the implementation of map, not a big deal for such a small function but a potential maintenance problem for more complex code. Second, we have only captured one sort of parallel evaluation firing off sparks for all the cons cells, but in practice getting parallelism right requires some often careful tuning to get the right level of granularity and account for dependencies. For instance, what if instead of doing each cell in parallel, we wanted to bunch them up into chunks so as to minimise the coordination overhead? What we need is a way to express ideas about running code in parallel (such as “break into chunks and run each chunk simultaneously"), preferably avoid duplicating existing code or otherwise making it more complicated than it needs to be. This is where strategies come in. A strategy is just a function that turns some data into an `Eval` sequence. We've already encountered two strategies above, `rpar` which sparks off a parallel evaluation, and `rseq` which evaluates its argument to weak head normal form. Many more strategies possible particularly when they are custom designed for specific data types. Also, if we have a strategy, we can imagine wanting to use it. This we capture with `using`, which applies the strategy function and runs the resulting sequence. Parallel evaluation aside, you can almost pretty much think of <code>x `using` s</code> as being semequivalent to as `id x` but you'll want to watch out for a couple of caveats described the tutorial [Parallel and Concurrent Programming in Haskell][smtutorial]. Strategy a = a -> Eval a using :: a -> Strategy a -> a x `using` s = runEval (s x) Now that we've put a name to the idea of building `Eval` sequences, we can think about trying to generalise our `parMap`. One way would be to write a higher-order strategy. This `parList` function is almost identical to `parMap`, except that instead of applying any function to a list we limit ourselves to just applying some strategy on it. parList :: Strategy a -> Strategy [a] parList strat [] = return [] parList strat (x:xs) = do x' <- rpar (x `using` strat) xs' <- parList xs strat return (x':xs') We can then define `parMap` by parameterising `parList` with `rseq` to get a parallel list strategy which we then apply to `map f xs`. (Food for thought: why `parList rseq` instead of `parList r0`? Reply to the Haskell-Cafe posting if you think you know why!) parMap :: (a -> b) -> [a] -> Eval [b] parMap f xs = map f xs `using` parList rseq We have now achieved two things. First we've improve the modularity of our code by separating algorithm (`map f xs`) from coordination (`parList rseq`). Notice how we are now reusing map instead of reimplementing it, and notice as well how we now have a reusable `parList` that we can use apply to any situation that involves a list. Second, by isolating the algorithm from the coordination code we have given ourselves a lot more flexibility to switch strategies. To bunch our list up into coarser-grained chunks, for example, we could just swap out `parList` with `parListChunk` parMap :: (a -> b) -> [a] -> Eval [b] parMap f xs = map f xs `using` parListChunk 100 rseq In this word of the month, we have very lightly touched on the idea of strategies as a compositional way of expressing parallel coordination and improving the modularity of our code. To make use of strategies, we basically need to be aware of two or three things: 1. How to apply a strategy: <code>foo `using` s</code> evaluates the value `foo` with strategy `s` 2. Useful strategies from the library: the basics are `r0` which does nothing, `rseq` which evaluates its argument to weak head normal form, `rdeepseq` which evaluates it all the way down to normal form, and `rpar` which sparks the value for parallel evaluation. Be sure to check out [Control.Parallel.Strategies][straddock] for more sophisticated strategies such as `parListChunk`, which divides the list into chunks and applies a strategy to each one of the chunks in parallel. 3. (Optionally) How to build strategies, the simplest way being to use the `dot` function to compose two strategies sequentially. If you implement your own strategies instead of combining those from the library, you may want to have a look at the [Seq no More][seq-nm] for a little safety note. If you want to know more about strategies, the first place to look is probably the tutorial [Parallel and Concurrent Programming in Haskell][smtutorial] (there is a nice example in there, implementing a parallel K-means algorithm) and followed by the Control.Parallel.Strategies API. You could also just dive in and give it a try on some of your own code. It's sometimes just a matter of grabbing a strategy and `using` it. Parallel GHC Project Update ---------------------------------------------------------------------- The Parallel GHC Project is an MSR-funded project to push forward the use of parallel Haskell in the real world. The aim is to demonstrate that parallel Haskell can be employed successfully in industrial projects. Speaking of industrial projects, our recent search for a new project partner has been successful! In fact, we will be welcoming two new partners to the project, the research and development group of Spanish telecoms company Telefónica, and VETT a UK-based payment processing company. We are excited to be working with the teams at Telefónica I+D and VETT. There may be some Cloud Haskell in our future; stay tuned for more details about the respective partner projects. Also coming up are a couple of Monad Reader articles featuring work from the Parallel GHC project. Kazu Yamamoto has been writing an article for the upcoming Monad Reader special edition on parallelism and concurrency. He'll be revisiting Mighttpd (pronounced "Mighty"), a high-performance web server written in Haskell in late 2009. Since Mighttpd came out the Haskell web programming landscape has evolved considerably, with the release of GHC 7 and development of several web application frameworks. The new mighttpd takes advantage of GHC 7's new IO manager as well as the Yesod Web Application Interface (WAI) and the HTTP engine Warp. Do check out his article when it comes out for proof that "we can implement a high performance web server in Haskell, which is comparable to highly tuned web servers written in C", or if you can't wait, try his [most recent slides][mighttpd] on the topic. Bernie Pope and Dmitry Astapov have been working on an article about the Haskell MPI binding developed in the context of this project. You can find out more about the binding on its [Hackage][hackage-mpi] and [GitHub][github-mpi] pages. Blogs, Papers, and Packages ---------------------------------------------------------------------- * [Data Parallel Haskell and Repa for GHC 7.2.1][b1] (11 Aug) Ben Lippmeier has updated the Data Parallel Haskell libraries on Hackage to go with the newly released GHC 7.2.1. While DPH is still a technology preview, this new version is significantly more robust than previous ones. If nested data parallelism isn't what you're after, Ben has also updated the Repa library for parallel arrays. See [PH Digest 3][phd3] for more details. * [thespian: Lightweight Erlang-style Actors for Haskell][b2] (18 Aug) Alex Constandache update Hackage with this intriguing library. I wrote to Alex asking about about the relationship with Cloud Haskell. It turns out Alex had somewhat similar goals in mind and may be focusing on Cloud Haskell instead. * [dbus-core 0.9][b3] (23 Jul) John Millikin announced "the first significant release to dbus-core in a while" with significant improvements to both the API and implementation. In particular, dbus-client has been merged into dbus-core. See the announcement for more details then a quick code sample showing the new simple API in action. For the curious, D-Bus is an inter-process communication mechanism used in desktop environments like Gnome. Mailing list discussions --------------------------------------------------------------------- * [How to ensure code executes in the context of a specific OS thread?][m1] (4 Jul) Jason Dagit has found the correct handling of GUI events on OS X requires checking for events and responding to them from the main thread. He wanted to know if such thing was even possible on the threaded RTS, particularly so that he could use the library from GHCi. David Pollak has a [bit of code][hs-ipad] that provides a runOnMain function using an FFI call to a bit objective C code. Simon Marlow pointed out that for compiled code, the main thread is a bound thread, bound to the main thread of the process. Simon is specifically talking about the threaded RTS here as this is already trivially true of the non-thread one. The question still remains open for GHCi. * [Cloud Haskell][m2] (22 Jul) Tom Murphy was curious to see anybody was using [Cloud Haskell][cloud-hs] yet. It looks like we have a couple people who are *thinking* of using it: Tim Cowlishaw might be using it for his masters thesis project (A Haskell EDSL for agent-based simulation). Julian Porter, who we mentioned in the last digest for his Monad Reader article, is planning to make his MapReduce monad framework work on the distribute cluster. Now how about those of us who have actually given it try? As for the Parallel GHC project, it's worth mentioning that our new partners are planning to use Cloud Haskell in their projects. We'll be sure to report back to the community about the results. * [A language that runs on the JVM or .NET...][m4] (31 Jul) KC was hoping for a version of Haskell "that runs on the JVM or .NET has the advantage of Oracle & Microsoft making those layers more parallelizable". Austin Seipp replied that it basically boils down to it being [a lot of work][why-no-jvm]. Chris Smith also cautions that while there may be many good reasons to easy to want a Haskell.Net or a Jaskell, Haskell parallelism and concurrency may not be one of them. Parallel and concurrent Haskell code relies generates a large volume of lightweight threads. Simply using their JVM or CLR counterparts as they are would not do. Are you interested in seeing a serious and long-term effort towards Haskell on the JVM? See the [FAQ][why-no-jvm] and get in touch! * [Error in the asynchronous exception operational semantics][m6] (9 Aug) Edward Z. Yang noticed at the end of [Asynchronous Exceptions as an Effect][async1] (Harrison et. al) that the authors have found an error in the operational semantics described in [Asynchronous Exceptions in Haskell][async2]. Anybody know what it is? Meanwhile, David Barbour took the opportunity to say > All you need to know about asynchronous exceptions is: *don't use them!* > They're too difficult to reason about, in terms of failure modes and such. > Use TVars or MVars instead. * [Haskell Actors, Linda, publish / subscribe models?][m7] (13 Aug) Dmitri O. Kondratiev needs to "build a framework to coordinate task producers / consumers distributed in the same and different address spaces. He needs to scale a data processing application somewhat Hadoop-like way yet in more flexible manner, without Hadoop-specific distributed FS constraints." At this point, Ryan Newton suggested "Cloud Haskell", which was greeted by with joy and great enthusiasm. "Finally Erlang actor model of communication comes to Haskell!" Keep us posted, Dmitri. * [More generic parfoldr than this... ][m8](23 Jul) Prabhat Totoo tried to implement a parallel foldr function by breaking the input listed chunks, mapping foldr over each chunk, and running foldr over the list of results. This solution only works if the input and output of the folded function have the same type. Prabhat wanted to know how he could go about generalising his parallel fold. Also while doing some timings, he noticed that the regular presumably sequential fold improved with multiple cores. What's up with that? Conal Elliott make the point that Prabhat's current parallelise-by-reassociating solution is only correct for an associative operation, which is forcibly of type (a -> a -> a). Have a look at the the rest of the thread for an exploration of parallel fold by Kevin Hammond, Conal Elliot and Sebastien Fischer. Stack Overflow and Reddit ---------------------------------------------------------------------- * [Are 'par' and 'pseq' good for data parallelism?][s1] * [Difference between MVar and a TVar?][s2] * [How to sort a list [MVar a] using a values?][s3] * [Understanding BlockedIndefinitelyOnMVar in Concurrent code][s4] * [Poor performance / lockup with STM][s5] * [If one of Haskell's goals is concurrency, then why is it based on the λ-calculus and not on a process calculus?][s6] Help and Feedback ---------------------------------------------------------------------- If you'd like to make an announcement in the next Haskell Parallel Digest, then get in touch with me, Eric Kow, at <parallel(a)well-typed.com>. Please feel free to leave any comments and feedback! [phd3]: http://www.well-typed.com/blog/55 [phd4]: http://www.well-typed.com/blog/56 [smtutorial]: http://community.haskell.org/~simonmar/par-tutorial.pdf [asp]: http://www.macs.hw.ac.uk/~dsg/gph/papers/abstracts/strategies.html [seq-nm]: http://research.microsoft.com/apps/pubs/default.aspx?id=138042 [mighttpd]: http://www.mew.org/~kazu/material/2011-mighttpd.pdf [hackage-mpi]: http://hackage.haskell.org/package/haskell-mpi [github-mpi]: https://github.com/bjpop/haskell-mpi [straddock]: http://hackage.haskell.org/packages/archive/parallel/3.1.0.1/doc/html/Contr… [hs-ipad]: https://github.com/dpp/LispHaskellIPad [cloud-hs]: http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/ [why-no-jvm]: http://www.haskell.org/haskellwiki/GHC:FAQ#Why_isn.27t_GHC_available_for_.N… [async1]: http://www.cs.missouri.edu/~harrison/papers/mpc08.pdf [async2]: http://community.haskell.org/~simonmar/papers/async.pdf [actors]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/actor [ph-libs]: http://www.haskell.org/haskellwiki/Applications_and_libraries/Concurrency_a… [n0]: http://www.haskell.org/haskellwiki/Parallel_GHC_Project [n1]: http://www.haskell.org/pipermail/haskell-cafe/2011-August/094484.html [b1]: http://tumblr.justtesting.org/post/8778213236 [b2]: http://hackage.haskell.org/package/thespian-0.999 [b3]: http://www.haskell.org/pipermail/haskell-cafe/2011-July/094203.html [m1]: http://www.haskell.org/pipermail/haskell-cafe/2011-July/093722.html [m2]: http://www.haskell.org/pipermail/haskell-cafe/2011-July/094176.html [m4]: http://www.haskell.org/pipermail/haskell-cafe/2011-July/094398.html [m6]: http://www.haskell.org/pipermail/haskell-cafe/2011-August/094521.html [m7]: http://www.haskell.org/pipermail/haskell-cafe/2011-August/094614.html [m8]: https://groups.google.com/d/topic/parallel-haskell/97dmSXickYM/discussion [s1]: http://stackoverflow.com/questions/6844378/are-par-and-pseq-good-for-data-p… [s2]: http://stackoverflow.com/questions/6915079/difference-between-tvar-and-tmvar [s3]: http://stackoverflow.com/questions/6955651/how-to-sort-a-list-mvar-a-using-… [s4]: http://stackoverflow.com/questions/6847307/understanding-blockedindefinitel… [s5]: http://stackoverflow.com/questions/6439925/poor-performance-lockup-with-stm [s6]: http://www.reddit.com/r/haskell/comments/jlipx/if_one_of_haskells_goals_is_… -- Eric Kow <http://erickow.com>

2 1

bitSize
by Andrew Coppin 31 Aug '11

31 Aug '11

Quoting the Haddock documentation for Data.Bits.bitSize: "Return the number of bits in the type of the argument. The actual value of the argument is ignored. The function bitSize is undefined for types that do not have a fixed bitsize, like Integer." Does anybody else think it would be *far* more useful if bitSize applied to an Integer would tell you how many bits that particular Integer is using? Especially given that it can vary? Is there a way to actually determine how many bits are in an Integer?

11 25

GHCI Feature Request: Last Successful Compilation State Saved
by aditya siram 31 Aug '11

31 Aug '11

Hi all, I would like for the GHCI interpreter to save its environment before reloading a file and allowed the user to revert back to that state if the compilation was unsuccessful. Many times I've changed files, loaded them, hit a compilation error and needed, for example, the inferred type signature of some function. Even though that function hasn't been changed I have to either fix my code, undo a bunch of changes or comment out the last change I made and reload in order to do a ":type" on the function. This really breaks the flow of development. Thanks for considering. -deech

7 12

installing/reinstalling haskell platform with profiling enabled on windows
by MH 31 Aug '11

31 Aug '11

How can I install/reinstall haskell platform with profiling enabled on windows? Or the other way to put it, how can I install/reinstall haskell platform on windows with my own cabal options? I googled on it and didn't find any solutions for windows OS. Thanks, Malik

2 1

Text.Parsec.Prim
by Roly Perera 31 Aug '11

31 Aug '11

Hi, I seem to have some trouble accessing this module. I would like to use the type synonym ParsecT directly. I'm running GHC 6.12.1. According to Hoogle, the type I want is part of parsec-3.1.1, in module Text.Parsec.Prim. But if try to import Text.Parsec.Prim, GHC complains Could not find module `Text.Parsec.Prim': Can anyone help me with this? In the 2+ years I've been using parsec I've never managed to use ParsecT directly, but now it would be very useful. thanks, Roly In verbose mode, GHC reports: Glasgow Haskell Compiler, Version 6.12.1, for Haskell 98, stage 2 booted by GHC version 6.12.1 Using binary package database: /usr/lib/ghc-6.12.1/package.conf.d/package.cache Using binary package database: /home/rolyp/.ghc/x86_64-linux-6.12.1/package.conf.d/package.cache hiding package Cabal-1.8.0.2 to avoid conflict with later version Cabal-1.10.2.0 hiding package QuickCheck-1.2.0.0 to avoid conflict with later version QuickCheck-2.1.0.2 hiding package base-3.0.3.2 to avoid conflict with later version base-4.2.0.0 wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-9d35c97e886f807a1e6d024aaa91dcec wired-in package integer-gmp mapped to integer-gmp-0.2.0.0-9a51ffb34a83618a1a3d4e472b9977a0 wired-in package base mapped to base-4.2.0.0-2cc27b7e43511c4ca001642a7f77a8f6 wired-in package rts mapped to builtin_rts wired-in package haskell98 mapped to haskell98-1.0.1.1-0fdaf3b26bc38c43ce8371edf538dbf6 wired-in package template-haskell mapped to template-haskell-2.4.0.0-bbc7c61990d2fe9d20be2deb924f833c wired-in package dph-seq mapped to dph-seq-0.4.0-52cfd6db5fc09a2abf793cd6a856a392 wired-in package dph-par mapped to dph-par-0.4.0-b4f339fed900d7bc4b3db61526caf863 Hsc static flags: -static

3 3

Ambiguous module name `System.Directory'
by informationen 31 Aug '11

31 Aug '11

Hi, i am using ghc version 7.0.3 and a pretty recent version of the haskell-platform. Whenever i use the System.Directory module, i run into this conflict: Ambiguous module name `System.Directory': it was found in multiple packages: system-fileio-0.2.1 directory-1.1.0.0 How can i resolve this conflict permamently (i know about :set -hide-package ... )? And shouldn't there be a rule in the haskell platform which forbids modules of the same name? Greetings Chris

5 5

[CUFP 2011] Birds of a Feather sessions
by Ashish Agarwal 30 Aug '11

30 Aug '11

========================================================= Birds of a Feather sessions (BOFs) Commercial Users of Functional Programming Workshop (CUFP 2011) http://cufp.org/bofs-2011 Tokyo, Japan, September 22 - 23 ========================================================= Following last year's success, CUFP 2011 will again include Birds of a Feather sessions. BoFs provide a place for our community to gather informally at CUFP and reach consensus on matters of importance. Any CUFP attendee can propose a BoF session, and grab one of the spare rooms to hold a discussion. Attendance in the evening is open to all. BoF sessions facilitate ad-hoc discussions and provide a place to gather and start off the chat, before moving on during the evening to a local restaurant or pub. There is no deadline for proposing a session, but we encourage you to do so at the earliest possible time to help us with planning and to publicize your proposed discussion. Attendees are also free to show up even if you have not confirmed, but again earlier confirmation will help us with planning. Please see http://cufp.org/bofs-2011 for details on how to propose a BoF session or confirm attendance at one of them. Scheduled BoFs will be listed here as they are confirmed. General information on CUFP 2011 can be found at http://cufp.org/conference/2011. The conference is co-located with ICFP. You can register for CUFP at the main ICFP website http://www.icfpconference.org/icfp2011.

1 0