- Haskell-Cafe - Haskell.org

Please critique my code (a simple lexer)
by John Simon 23 May '12

23 May '12

Hi all, I've been teaching myself Haskell lately (I come from the C#/Python world). I wrote a simplistic lexer, and I was hoping I could get a code review or two. The code that follows is a stand-alone app that works under GHC. A few concerns of mine: - My `consume` function seems basic enough that it should be library code, but my searches turned up empty. Did I miss anything? - Is `case _ of x:xs -> x:xsr where xsr = something xs` a common idiom? It happened twice in my code, and it seems odd to split the first element away from the rest of the list as it's processed. - Is creating data structures with simple field names like `kind`, `offset`, etc a good practice? Since the names are global functions, I worry about namespace pollution, or stomping on functions defined elsewhere. Thanks in advance for anyone willing to take the time. -- code follows module Main where import qualified Data.Map as Map data Lexer = Lexer String makeLexer :: String -> Lexer makeLexer fn = Lexer fn data Loc = Loc {offset :: Int, line :: Int, column :: Int} locInc loc n = Loc (offset loc + n) (line loc) (column loc + n) locNL loc = Loc (offset loc + 1) (line loc + 1) 1 data TokenKind = Colon | RArrow1 | Def | Var | Identifier String | EOF deriving Show data Token = Token {lexer :: Lexer, loc :: Loc, kind :: TokenKind} idStart = ['a'..'z'] ++ ['A'..'Z'] ++ "!@$%^&*-_=+|<>/?" idNext = idStart ++ ['0'..'9'] ++ "'\"" namedTokens = Map.fromList [ ("def", Def), ("var", Var)] doLex :: Lexer -> String -> [Token] doLex lexer = doLex' lexer (Loc 0 1 1) doLex' lexer loc source = case source of [] -> [makeToken EOF] ' ':xs -> more (locInc loc 1) xs '\n':xs -> more (locNL loc) xs ':':xs -> makeToken Colon : more (locInc loc 1) xs '-':'>':xs -> makeToken RArrow1 : more (locInc loc 2) xs x:xs | x `elem` idStart -> makeToken kind : more (locInc loc $ length name) xsr where (namer, xsr) = consume idNext xs name = x:namer kind = maybe (Identifier name) id $ Map.lookup name namedTokens _ -> error "Invalid character in source" where makeToken = Token lexer loc more = doLex' lexer consume :: Eq a => [a] -> [a] -> ([a], [a]) consume want xs = case xs of x:xs | x `elem` want -> (x:xsr, rest) where (xsr, rest) = consume want xs _ -> ([], xs) main :: IO () main = do let toks = doLex (makeLexer "") "def x -> y" in putStrLn $ show $ map kind toks

4 3

Encoding issues with LDAP package
by Vincent Ambo 23 May '12

23 May '12

Hej, I'm using the LDAP package by John Goerzen to retrieve some information from an Active Directory database. Part of this information are the full names of my company's employees. Many of these names contain characters which aren't part of the standard ASCII set, for example ä å ü ê and so on. When I retrieve those names from the directory (the LDAP package returns them as Strings) the encoding breaks and I get results like "R\195\188diger" instead of "Rüdiger". The Active Directory server supports LDAP v2 and v3. I assume the OpenLDAP C API, which is the backend behind the LDAP package, automatically chooses v3 to connect if available (this is speculation, correct me if I'm wrong). Since LDAP v3 only speaks UTF8 and ASCII I also assume that the server returns UTF8. Is this a known problem in the LDAP package? Or is this related to the OpenLDAP C API? Or even something on the server side? Any information would be helpful! Best regards, Vincent

2 1

Heads up: importing the Cabal issue tracker to github next week
by Bryan O'Sullivan 23 May '12

23 May '12

I am planning on doing this early next week, probably in two phases. As part of the import process, github will generate a *lot* of notification emails. I'm afraid there is nothing I can do to stem the tide, as github does not provide a mechanism to suppress these. If you have a github account, and you have filed bugs against Cabal in Trac, please brace yourself.

2 1

Haskell Day 2012 (in Japan)
by Kazu Yamamoto 23 May '12

23 May '12

Hello Cafe, This is just FYI. We Hasekell community in Japan will have an event called Haskell Day 2012 on 27th May to cerebrate the publication of the Japanese version of "Learn you". 180+ people have already registered: # This page is written in Japanese. http://partake.in/events/ab7f77b4-7541-47a4-867d-21a096ca883c P.S. The Japanese version of "Learn you" was on sale yesterday and already sold out in many bookstores. :-) --Kazu

1 0

(+1) vs let inc=(+1)
by Greg Fitzgerald 22 May '12

22 May '12

In ghci 7.4.1: Prelude> :t (+1) (+1) :: Num a => a -> a Prelude> let inc=(+1) Prelude> :t inc inc :: Integer -> Integer Why the difference? Thanks, Greg

3 3

From some "High-Performance Computing" book; "It is hard to eradicate from C++'ers the need for objects, classes, etc. ..."
by KC 22 May '12

22 May '12

"For high-performance computing you want to avoid such software engineering abstractions as classes, objects, etc...." Therefore, I would say, since Haskell makes possible many fine-levels of abstraction, if the compiler can strip most of these away, then it would come close to the speed of C (i.e. C++ without most of the software engineering abstractions). Still, I remember that quote that, "Another level of indirection solves everything." Or If you're Penn & Teller, "Another level of misdirection solves everything." Casey -- -- Regards, KC

1 0

ANN: reform - a type-safe form generation and validation library in the spirit of formlets and digestive-functors < 0.2
by Jeremy Shaw 22 May '12

22 May '12

I am pleased to annouce the release of 'reform'. A full tutorial is available here: http://www.happstack.com/docs/crashcourse/Reform.html Reform is an HTML form generation and validation library. It follows in the footsteps of formlets and digestive-functors <= 0.2. In fact, much of the code in reform comes from the digestive-functors-0.2 code base. Reform is designed to be usuable with a wide variety of Haskell web servers and templating libraries. You can find the following packages on hackage: * reform - the core library * reform-happstack - support for using reform with the Happstack server * reform-blaze - support for creating forms for blaze-html * reform-hsp - support for creating forms for HSP (another xml/html template library) The source code is available via darcs: darcs get http://patch-tag.com/r/stepcut/reform The darcs repo also includes proof-of-concept support for 'Heist'. Reform will feel very familiar to formlets and digestive-functors <= 0.2 users. The primary motivation behind this library is to provide a supported alternative to digestive-functors 0.2 for users that prefer 0.2 over 0.3. The key new feature in reform is the ability to separate the validation code from the view generation code. This allows library authors to provide validators (known as Proofs) which the users can use when constructing their forms. The proof names appear in the type-signatures. This allows the library author to ensure that the value returned by a user created form is not merely the correct type, but has also passed validation. The reform-happstack package also provides simple and transparent Cross-Site Request Forgery (CSRF) protection, using the double-submit method. This method has some weaknesses. For example, I believe it can be circumvented if your site is vulnerable to cross-site scripting (XSS) attacks. If you have suggestions on how to improve the CSRF protection -- please let us know! I hope to do a full comparison of reform vs digestive-functors 0.3 vs yesod forms in a few weeks. - jeremy

3 3

Zipper and Comonad
by Mathijs Kwik 22 May '12

22 May '12

Hi all, After using zippers for a while, I wanted to dig a bit deeper into them. I found there is some relation between Zipper and Comonad, but this confuses me somewhat. After reading a bit more about Comonads [1] and [2], I think I understand them somewhat, and I see how they too are useful for navigating a data structures and giving functions the ability to "look around". What confuses me though, is the relation between these 2. This source [3] mentions all zippers can be made instances of Comonad, and demonstrates how to do this for simple, 1-dimensional (list) zippers. But a comment on [4] says a Zipper by itself is already an application of Comonad. I want to find out which is the case. Looking at the types does not yield me a solution yet. This is Zipper from LYAH: data Tree a = Empty | Node a (Tree a) (Tree a) data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a) type Breadcrumbs a = [Crumb a] type Zipper a = (Tree a, Breadcrumbs a) This is Comonad from the comonad package (flattened to 1 class): class Functor w => Comonad w where duplicate :: w a -> w (w a) extend :: (w a -> b) -> w a -> w b extract :: w a -> a Now, if [3] is correct, I can write "instance Comonad Zipper". If I understood all this correctly, "extend" becomes "(Zipper a -> b) -> Zipper a -> Zipper b". This gives me something like a "look-around fmap" which sounds useful. If the comment on [4] is correct though, Zipper somehow has a Comonad "built-in", (probably hidden the interaction between Tree and [Crumb]). So in that case, a Zipper would be a (somewhat customized) "instance Comonad Tree" with some extensions. "(Tree a -> b) -> Tree a -> Tree b" seems reasonable. It will build up a new tree with the same shape as the input tree, and allows the mapping function to examine every node _and_ its child nodes. It does not allow "looking up" though. So what do I make of this? It's clear that every Zipper can be a Comonad, and it's probably useful in some cases, but on the other hand, a Zipper already gives the ability to look around and modify (a -> a) things, so the comonadic instance only allows you to do this in a somewhat structure-preserving way. It's still not clear to me whether there is some truth in "a Zipper itself is an application of Comonad". What I looked at above is just a Tree instance, which obviously lost power compared to a full Zipper. But I somehow feel there indeed is a somewhat deeper relation between these 2 compared to just "can be made instance of". Please share your thoughts. Thanks, Mathijs [1] http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html [2] http://blog.sigfpe.com/2008/03/comonadic-arrays.html [3] http://blog.sigfpe.com/2007/01/monads-hidden-behind-every-zipper.html [4] http://gelisam.blogspot.com/2007/04/i-understand-comonads.html

3 2

Data.Array.Unboxed in GHC 7.4
by Tom Nielsen 22 May '12

22 May '12

Dear cafe, I have just upgraded to GHC 7.4, and now I run into some compilation problems. Specifically, I have a package that needs both Data.Array.Unboxed and System.IO.Unsafe. But I cannot enable both base and haskell98 in a cabal file. is there any way out of this? If I enable both haskell98 and base, I get Query.hs:1:1: Ambiguous module name `Prelude': it was found in multiple packages: base haskell98-2.0.0.1 cabal: Error: some packages failed to install: as documented elsewhere (http://hackage.haskell.org/trac/ghc/ticket/4958) With haskell98 replacing base, I get Query.hs:55:8: Could not find module `System.IO.Unsafe' It is a member of the hidden package `base'. Perhaps you need to add `base' to the build-depends in your .cabal file. Use -v to see a list of the files searched for. cabal: Error: some packages failed to install: and without haskell98 or array, cabal tells me to add those to .cabal build-depends. So how can I use the Data.Array.Unboxed package together with all the stuff from base that is not in haskell98? Thanks, Tom

1 1

Large graphs
by Benjamin Ylvisaker 22 May '12

22 May '12

I have a problem that I'm trying to use Haskell for, and I think I'm running into scalability issues in FGL. However, I am quite new to practical programming in Haskell, so it's possible that I have some other bone-headed performance bug in my code. I tried looking around for concrete information about the scalability of Haskell's graph libraries, but didn't find much. So here are the characteristics of the problem I'm working on: - Large directed graphs. Mostly 10k-100k nodes, but some in the low 100ks. - Sparse graphs. The number of edges is only 2-3x the number of nodes. - Immutable structure, mutable labels. After initially reading in the graphs, their shape doesn't change, but information "flows" around the graph, changing the labels on nodes and edges. I wrote some code that reads in graphs and some some basic flow computations on them. The first few graphs I tried were around 10k nodes, and the performance was okay (on the order of several seconds). When I tried some larger graphs (~100k), the memory consumption spiked into multiple GB, the CPU utilization went down to single digit percentages and the overall running time was closer to hours than seconds. Because the graph structure is basically immutable for my problem, I'm tempted to write my own graph representation based on mutable arrays. Before I embark on that, I wonder if anyone else can share their experience with large graphs in Haskell? Is there a library (FGL or otherwise) that should be able to scale up to the size of graph I'm interested in, if I write my code correctly? Thanks, Ben

4 4

Mighttpd 2.6.0 has been released
by Kazu Yamamoto 21 May '12

21 May '12

Hello cafe, I have released Mighttpd 2.6.0: http://mew.org/~kazu/proj/mighttpd/en/ Some users started using Mighttpd 2 and I was requested to implement missing features for real world operation. So, I implemented the following features in Mighttpd 2.6.0: - Route file reloading - Graceful shutdown for upgrading - URL rewriting (with HTTP redirection) For more information, please read the homepage above. I would like to thank Michael Snoyman for merging the necessary patch to warp. Regards, --Kazu

1 0

Cardinal Haskell RBTree? And structural sharing.
by Matt Lamari 20 May '12

20 May '12

I dug this haskell code of the internet wayback machine. Don't worry, Dons - it may be old; but it's still Golden. . . it seems to be from the Okasaki book with a working delete and key-value variant: http://web.archive.org/web/20100629235553/http://www.cse.unsw.edu.au/~dons/… I'm still at the lower end of Haskell expertise; but I can read this, and am porting the concept into my Heresy library for CL. The algorithm seems to be proven via some haskell static means (that I don't fully understand); but it also holds up to my heavy unit tests. What I value from functional containers, though, is that the modded structure shares the bulk of its identity/nodes with the prior variant. However, I added sharing as a metric to my unit test, so it can also discover when a new (by identity) node exists in the modified/new reference that is logically analogous to a node the old/prior one. . . . . which would waste space if people are holding various references to evolving containers. When purely translating this code, even in zero-change cases, one function will build a red node from a black, only to have the caller use *that* to build a brand new black - as across the 2 levels it has no way of seeing that the optimal node is merely the original node. Through some fundamental changes, and a bit of "whack a mole" (especially in the delete case) I *think* I caught and removed them all. . . . Anyway, my point: It seems that these containers can be analyzed with respect to their pure algorithm/logical correctness; but also structural storage. Is there much talk on that side of the issue? Is there any cardinal reference for this or similar data structures with the storage issue resolved? I'd be interested in looking at another implementation, especially one where the size issue isn't just tested; but proven. . . .

1 0

darcs patch dependencies in dot format
by Sönke Hahn 20 May '12

20 May '12

Hi all! Yesterday I wrote a little tool to output the dependencies of darcs patches in dot format. The hardest part was to wrap my head around the darcs API and find a way to let it compute the patch dependencies. I don't know, if I got it right, but it looks correct at first glance. Here is the code: https://patch-tag.com/r/shahn/darcs2dot To use it just execute the program in a darcs repo and it will output a dot graph to stdout. The graph does not contain all dependencies, but the transitive reduction. The patch names are truncated at 15 characters. And here is an example graph: http://open-projects.net/~shahn/patchDeps.pdf These are the patch dependencies of one of my darcs repos (https://patch-tag.com/r/shahn/hate) Some observations I made: * There are two completely separate subgraphs. One subgraph seems to be for the testsuite, the other for the actual code. This means, the two don't depend on each other and could easily be put in two distinct repos. * There is a "re-implementation" patch with a lot of incoming and outgoing edges. (Which makes sense.) * There are some sequences of patches (e.g. these four "allow ..." patches in the upper left corner) that seem to contain related patches. * darcs's patch system is awesome! Any comments or suggestions? Cheers, Sönke

10 15

How to write Source for TChan working with LC.take?
by Hiromi ISHII 20 May '12

20 May '12

Hello, there. I'm writing a Source to supply values from TChan. I wrote three implementations for that goal as follows: ~~~~ import Data.Conduit import qualified Data.Conduit.List as LC import Control.Monad.Trans import Control.Concurrent.STM import Control.Monad sourceTChanRaw :: MonadIO m => TChan a -> Source m a sourceTChanRaw ch = pipe where pipe = PipeM next (return ()) next = do o <- liftIO $ atomically $ readTChan ch return $ HaveOutput pipe (return ()) o sourceTChanState :: MonadIO m => TChan a -> Source m a sourceTChanState ch = sourceState ch puller where puller ch = StateOpen ch `liftM` (liftIO . atomically $ readTChan ch) sourceTChanYield :: MonadIO m => TChan a -> Source m a sourceTChanYield ch = forever $ do ans <- liftIO . atomically $ readTChan ch yield ans ~~~~ Namely, one using raw Pipe constructors directly, using `sourceState` and `yield`. I tested these with GHCi. ~~~~ ghci> ch <- newTChanIO :: IO (TChan ()) ghci> atomically $ replicateM_ 1500 $ writeTChan ch () ghci> sourceTChanRaw ch $$ LC.take 10 [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanState ch $$ LC.take 10 [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanYield ch $$ LC.take 10 *thread blocks* ~~~~ First two versions' result is what I exactly expected but the last one not: the source written with `yield` never returns value even if there are much enough value. I also realized that following code runs perfectly as I expected: ~~~~ ghci> ch <- newTChanIO :: IO (TChan ()) ghci> atomically $ replicateM_ 1500 $ writeTChan ch () ghci> sourceTChanRaw ch $= LC.isolate 10 $$ LC.mapM_ print [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanState ch $= LC.isolate 10 $$ LC.mapM_ print [(),(),(),(),(),(),(),(),(),()] ghci> sourceTChanYield ch $= LC.isolate 10 $$ LC.mapM_ print [(),(),(),(),(),(),(),(),(),()] ~~~~ So, here is the question: Why the Source using `yield` doesn't work as expected with LC.take? Or, might be Semantically, what behaviour should be expected for LC.take? Thanks, -- Hiromi ISHII konn.jinro(a)gmail.com

1 0

Is protocol-buffers package maintainer reachable?
by Chris Kuklewicz 19 May '12

19 May '12

To those looking for me: I live! And I got reminded to get back in touch via http://www.well-typed.com/blog/66 (kudos to them!). protocol-buffers is updated, now on to regex-*

1 0

Protocol Buffers 2.0.7
by Chris Kuklewicz 19 May '12

19 May '12

I have returned from the shadows of the intenet to maintain some packages! Version 2.0.7 of protocol-buffers (3 packages) has been uploaded to hackage. This makes it compile with ghc-7.4.1 and handle missing package names better. Thanks to everyone who sent email and patches, including Nathan Howell, Alexey Khudyakov, Howard B. Golden, Bryan O'Sullivan, Michael Stone, Daniel Rebelo de Oliveira, Paul Graphov, Tsurann, Sergei Trofimovich, Yitzchak Gale. The usual hackage links: http://hackage.haskell.org/package/hprotoc http://hackage.haskell.org/package/protocol-buffers-descriptor http://hackage.haskell.org/package/protocol-buffers And the darcs repo is at: http://code.haskell.org/protocol-buffers/ Q: What is protocol-buffers? A: It is a Haskell version of Google's protocol buffer wire protocol, see http://code.google.com/p/protobuf/ for a full description. Q: What does the hprotoc executable do? A: It convers "protocol-buffer descriptor files" into Haskell code to implement those data messages. Q: What does the protocol-buffers library do? A: It is the runtime API for using the binary protocol, serializing and deserializing the data types generated by hprotoc. Q: What is the protocol-buffers-descriptor library do? A: It is the support library for parsing "protocol-buffer descriptor files" into data structures. Most of this code is generated by hprotoc from a "protocol-buffer descriptor file" for "protocol-buffer descriptor files". Yes, it had to be bootstrapped. -- Dr. Chris Kuklewicz

1 0

ANNOUNCE: time-lens-0.1
by Roman Cheplyaka 19 May '12

19 May '12

I'm happy to announce the first, experimental version of the time-lens library. http://hackage.haskell.org/package/time-lens https://github.com/feuerbach/time-lens Its goal is to simplify working with time and date data structures in Haskell by providing lens-based overloaded accessors for Data.Time types. E.g. to find the current hour you currently need to write something like todHour . localTimeOfDay . zonedTimeToLocalTime <$> getZonedTime With time-lens it becomes getL hours <$> getZonedTime The difference is even more impressive when you need to *update* the hour in a ZonedTime structure, but admittedly such a need is relatively rare. The library is pure Haskell 2010 code. It is also completely type-compatible with Data.Time, so it's very easy to start using it in existing projects. -- Roman I. Cheplyaka :: http://ro-che.info/

1 0

Re: [Haskell-cafe] Can Haskell outperform C++?
by Janis Voigtländer 19 May '12

19 May '12

Am 19.05.2012 12:00, schrieb wren ng thornton: > Exactly. That's what I was trying to get at re the problems of comparing > Haskell to C++ (or indeed any pair of dissimilar languages). A > legitimate comparison will involve far more than microbenchmarks, but > then a legitimate comparison must always have a specific focus and > context in order to be able to say anything interesting. The problems I > see in language comparisons is that by and large they tend not to have > any such focus[1], and consequently they shed little light on how the > languages compare and shed a bit of darkness by serving only to confirm > initial biases. > > > [1] A nice counter-example to this trend are papers like: > > http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf > > There was another one comparing the expressivity of Java-style > polymorphism vs Haskell-style polymorphism, based on an analysis of > in-the-wild code; but I can't seem to pull it up at the moment. Possibly "Software extension and integration with type classes" by Lämmel and Ostermann? http://doi.acm.org/10.1145/1173706.1173732 Best, Janis. -- Jun.-Prof. Dr. Janis Voigtländer http://www.iai.uni-bonn.de/~jv/

1 0

Can Haskell outperform C++?
by Isaac Gouy 19 May '12

19 May '12

Wed May 16 16:40:26 CEST 2012, Gregg Lebovitz wrote: 2) ... I think the problem with current comparisons, is that they are designed to favor imperative languages. Please be specific: - Which current comparisons? - How do you know what they are designed to favor?

5 10

Re: [Haskell-cafe] AI - machine learning
by C Gosch 18 May '12

18 May '12

Hi all, I have implemented max-sum/sum-product in c++ before and a while ago, did the same in Haskell. I don't think my implementation is as idiomatic Haskellish as I would like, and I have so far not published it and also not looked at it for a little while (since I have some more projects :) ). However, if you are interested, I will publish it (maybe on github?), and I think we should join forces. I am also very interested in machine learning techniques, but I can unfortunately use neither those nor Haskell at my day job at present. Let me know what you think. Best regards, Christian Message: 3 Date: Thu, 17 May 2012 15:36:08 +0400 From: Paul Graphov <graphov(a)gmail.com> Subject: Re: [Haskell-cafe] AI - machine learning To: miro <miroslav.karpis(a)gmail.com> Cc: haskell-cafe(a)haskell.org Message-ID: <CAKHAQn+yFGCdLPoKR0sEhvJobwPPykvqTYieqZeBbzhyVodizg(a)mail.gmail.com> Content-Type: text/plain; charset=UTF-8 Hi Miro! I have no useful information for you. Few weeks ago I also checked for any AI (machine learning first of all) related packages exist and found nothing satisfactory except for some quite small packages implementing a single algorithm (like NN-back-propagation). So there is a lot to do :) If you are going to do something in this area please let me know, I'll be glad to collaborate! p.s. Now I'm taking Machine Learning course at Coursera.org and looking forward to apply this knowledge with Haskell. On Tue, May 15, 2012 at 3:02 AM, miro <miroslav.karpis(a)gmail.com> wrote: > Hi All, recently I started to take a look at haskell, especially at AI. I > can see some email addresses of interested people there but not so much of > other activity behind. Does it exist some mailing group especially for AI? > > Basically I'm interested in trying some machine learning algorithms. Start > with reinforcement learning and value-based), and go towards AGI (Artificial > General Intelligence). Does anybody know about some already existing haskell > approaches, or is there anybody working on this? > > Cheers, > m.

2 1

How to use Plugins package?
by Андрей Янкин 18 May '12

18 May '12

Hi, I'm newbie and I've got a problem. I'm trying to get example programs from plugins-auto [1] or hotswap [2] to work. I think question on stackoverflow [3] somewhat related to my problem. They are compiled well, but in runtime I get either segfault or Prelude.undefined or internal error: PAP object entered! I use GHC 7.4.1. x86_64 Ubuntu I've read "Plugging Haskell In" and would like to make some fun with plugins, but alas... Maybe -dynamic flag is what I seek? Or maybe I need to know something else? Maybe I needn't use Plugins package like in gitit? Please, could you explain how to compile plugins in haskell correctly? Where should I start? [1] http://hackage.haskell.org/package/plugins-auto [2] http://hackage.haskell.org/package/hotswap [3] http://stackoverflow.com/questions/5427777/help-with-haskell-dynamic-plugin…

2 2

Parallel Haskell Digest 10
by Eric Kow 18 May '12

18 May '12

Hello Haskellers! Did you see Ambassador Peyton Jones in Scala land? Simon was recently at ScalaDays 2012 (a large gathering for professional Scala users) giving a [keynote talk on Cloud Haskell][v1] (one hour video). Cloud Haskell is a pretty exciting new development in the Haskell space, providing the beginnings of a story for distributed programming in Haskell. It's also one of the areas we're focused on over the Parallel GHC project, building a new implementation to replace the current prototype. We're looking forward to talking a bit more about Cloud Haskell in the next (and final) edition of the digest. Wait, did I say just **final**? Indeed, by the next digest, we'll be wrapping up the Parallel GHC project. In addition to a bit more Cloud Haskell material, we'll give a little recap of the things we and our partners worked on over the two years. It's been fun! Meanwhile, in this penultimate edition, we'll be taking a look at concurrent *channels* as our word of month. We also have new parallel Haskell book to look forward to, an update to Accelerate, the new `meta-par` family of packages to look at, and also a lot of recent activity on StackOverflow. (For fancy HTML version and images, see http://www.well-typed.com/blog/66 ) News ---------------------------------------------------------------------- * [GSoC: concurrent hashtables][n0] Loren Davis and 7 other students have been accepted to the Google Summer of Code project under Haskell.org. Loren will be working to [implement concurrent thread-safe mutable hash-table][n0]. Congratulations and best of luck to Loren, Aditya, David, Mark, Mikhail, Phillip, Shae, and Shayan. Hope it's a fun summer! * [Lectureship in Computer Science - Saint Andrews][n3] Kevin Hammond urges us to consider applying for this lecturship in functional programming (closing date 22 June) at the University of Saint Andrews: We seek lectureship applications from researchers who have a strong research background and excellent publication record in any area of functional programming, complementing and enhancing the existing research team, which has a strong focus on parallel programming models and implementation, resource-aware functional programming, dependent type systems, refactoring, static analysis, and performance modelling, and deep connections with the Haskell community. * [O'Reilly book on Parallel and Concurrent Haskell][n4] (17 May) Haskell is getting a third O'Reilly book! Joining the introductory [Real World Haskell][rwh], and web-oriented [Haskell and Yesod][yesod-book], will be a forthcoming book on parallelism and concurrency in Haskell (tentative completion date March 2013). Simon Marlow will building this book off his [CEFP 2012 tutorial][sm-cefp] tutorial. He's “really keen for this to be a book that will be useful to people both learning about parallelism and concurrency in Haskell, and coding stuff for real-world use.” Please let him know if you have suggestions for topics or application areas you'd like covered. ## Conferences * [Erlang Workshop (due 3 Jun, workshop 14 Sep)][n1] Haskell has been borrowing from Erlang lately (Cloud Haskell!). John Hughes suggests, “Why not adapt some cool Haskell ideas to Erlang too?” The Eleventh ACM SIGPLAN Erlang Workshop will take place this year in Copenhagen, Denmark on the tail end of the ICFP. Just two weeks to go! * [Facing the Multicore-Challenge III (19-21 Sep)][n2] And if ICFP isn't enough for you, how about this Conference for Young Scientists, just a few days after? The Hochschule für Technik, will hosting the third multicore-challenge conference in Stuttgart, Germany, from 19-21 September. It aims to combine new aspects of multi-/manycore microprocessor technologies, parallel applications, numerical simulation, software development and tools. Contributions are welcome from all participating disciplines. Particular emphasis is placed on the support and advancement of young scientists. Word of the month ---------------------------------------------------------------------- This month, we'll be taking a short breather in our exploration of the Haskell concurrency space, and fleshing out some of the uses for the tools we already have. In the past two digests, we saw how Haskell provides *locks* for low-level concurrency, and the vastly safer *transactions* for concurrency at a higher level. Both approaches give us the notion of a typed mutable variables, the idea being that an `MVar Int` would hold a locked integer, whereas a `TVar Int` would hold instead hold transactional reference to an integer. These variables can hold arbitrarily complex things of arbitrary type; you could have anything from a `TVar Char` to a `TVar Customer` (where `Customer` would be some record you've defined in your application). Now that we have mutable variables, it's worth thinking a bit harder about what we might actually put into them. Suppose you find yourself in a typical producer/consumer scenario, for example, with a web service that automatically marks student essays, and which is broken into a piece that accepts submissions (producer) and which passes them on to the core essay-marking engine (consumer). So the producer generates essays and the consumer eats them up and does some work on them; how do we get them talking to each other? It's not enough to just use a single `TVar` because we want the producer to be able to continue cranking out essays whilst the consumer is working, rather than waiting for it to finish. We assume here that essay-marking is a fairly clever and computationally expensive process, and for this reason, we would want some kind of backlog that the producer can tack things on to, and the consumer can pull things off of. As such, our word of the month is *channel*. The unbounded channel abstraction is something that you can fairly easily implement out of either the locky `MVar`'s or transactional `TVar`'s, but we'll focus on the latter as transactions are just so much more civilised (though the same concepts would mostly apply). In the STM world, channels look a little like the following: -- Control.Concurrent.STM.TChan data TChan a newTChan :: STM (TChan a) writeTChan :: TChan a -> a -> STM () readTChan :: TChan -> STM a In the same fashion as the `TVar`'s that we introduced last time, `TChan`'s are parameterised with a type variable, meaning that you could have a channel of characters with `TChan Char`, or a channel of customers with `TChan Customer`, and so forth. Creating, reading, and writing to a channel are all transactions (i.e., in the the STM monad). Revisiting our essay marking service, we can sketch out how these channels might be used: import Control.Concurrent.STM.TChan main :: IO () main = do chan <- newTChan forkIO (producer chan) forkIO (consumer chan) forever $ return () producer :: TChan Essay -> IO () producer chan = forever $ do essay <- magicalWebFrameworkStuff atomically $ writeTChan chan essay consumer :: TChan Essay -> IO () consumer chan = forever $ do essay <- atomically $ readTChan chan mark essay mark :: Essay -> IO () mark essay = putStrLn "Let me think..." -- State-of-the-art marking technology, -- just $25000 per site license randomRIO (1, 10000000) >>= threadDelay pass <- randomIO if pass then putStrLn "Pass, good job!" eles putStrLn "Fail!" And that's it! Using concurrent channels does not get more complicated or deeper than this. You may have noticed that in this particular example, we have not really gained (or for that matter lost) that much from sticking to the transactional version of channels. Using the locky `MVar` version would basically consist of dropping the `atomically`'s, importing from `Control.Concurrent.Chan`, and using `Chan` instead of `TChan`. Now that we have a bit of an idea what channels are about, it could be worthwhile to consider what it really offers over simpler alternatives. For example, in the introduction we rejected the idea of just using a single `TVar` because this would force our producer and consumers to wait on each other for each and every essay, rather than going about their asynchronously merry ways. So we know we want something *like* channels, but how exactly do we go about building them? For starters, wouldn't we get a channel structure by just wrapping `Data.Sequence.Seq` with a single `TVar`? It could be made to work as we are using STM (it simply wouldn't work if we were using `MVar`'s instead; consider the empty channel), but it would leave us with the unfortunately inability to simultaneously read from and write to the channel. These operations would have to grab a hold of the whole queue, leaving the other to retry until later. It would a little sad not to enable this bit of concurrency, considering that that reading and writing take place at opposite ends of the queue, the reader walking along trying to keep up with the writer. Instead of naively wrapping a queue, the current implementation uses a sort of linked list with `TVar`'ed cons cells and `TVar`'s pointing to both the beginning (the read end) and the end of the list (the write end). Here are the data structures that make up a channel: type TVarList a = TVar (TList a) data TList a = TNil | TCons a (TVarList a) data TChan a = TChan (TVar (TVarList a)) -- read end (TVar (TVarList a)) -- write end It can be a little bit tricky to think about because we've got `TVar`'s wrapping around things that eventually wrap around `TVar`'s themselves. It's a whole chain of `TVar`'s, and if you can have a `TVar a`, there's no reason not to have a `TVar (TVar a)`. If that feels a bit shaky, try implementing channels yourself as a quick little exercise. We'll speed things along with a handful of pictures to illustrate how it might work. First, our visual language for talking about `TVar`'ed cons cells: ![TChan legend](channel-legend.png) A new channel has three `TVar`'s, one for the linked list (it points to `TNil`), and a pair of read/write ones pointing to this pointer: ![new TChan](channel-new.png) Writing the channel involves adding to the list and moving the write pointer to the new tail of the list: ![write TChan](channel-write.png) And finally reading those items off the channel involves moving the read pointer forward: ![read TChan](channel-read.png) The implementation should be fairly straightforward from the pictures, although one place you might get stuck when trying to read from an empty channel. After all, how do you return a value from a channel that doesn't have any, especially since you're expected to return plain old `a` instead of `Maybe a`? Well, sometimes you just gotta wait. We briefly glossed over this in our taste of STM in the [last word of the month][ph-digest-9], but STM offers a `retry` function simply causes a transaction to be aborted and tried again. Using this notion of blocking, you should be able to get a `readTChan` that waits until there is something to be read. Hopefully, the exercise of implementing channels will be a useful reminder to think of the concurrency abstractions that Haskell provides (threads, transactional mutable variables) as primitives on top of which you can build more interesting and useful abstractions. For a little more fun, head over to Simon Marlow's [tutorial on parallelism and concurrency][tutorial-sm]. In this tutorial, Simon illustrates the building channels over `MVar`'s (also worth doing) and mentions an easy generalisation to *multicast* channels (one write end, two read ends!) and also a small extension to “unread” a value (pushing it back on to the read end). Both extensions are easy on the surface, but hard to nail down to the exact desired semantics (there's no known correct implementation of the unread extension), at least when you're dealing with locks and `MVar`'s. But if you stick to transactions and `TVar`'s, both wind up being straightforward. Check out his tutorial! Videos ---------------------------------------------------------------------- * [Towards Haskell in the Cloud][v1] (17 Apr, 1 hour) Simon Peyton Jones gave one of the keynote lectures at the recent ScalaDays 2012 in London. Simon sets the stage with some of the recent thinking about how functional programming and parallel programming fit together: that functional is the way forward, but no one single approach is going to cover all scenarios; that cost models are important to keep in mind; and that being able to explore all these different approaches within a single language is a great thing. From here, Simon launches into the heart of his presentation, Cloud Haskell (Scala hackers, think Akka). Cloud Haskell was developed with distributed programming in mind, in other words, large scale, multiple machines, no shared memory. Simon's talk covers quite a bit of ground: the Erlang-style actor model as an explicit embrace of distributed memory; the Haskell typed channels twist; programmer-controlled serialisation with type classes; and finally the longtime big stumper, how we go about serialising functions. It's interesting stuff. And as a sort of side bonus, even if don't walk away with a better idea what Cloud Haskell is all about, you should at least get a concrete sense for how type classes work. Blogs and packages ---------------------------------------------------------------------- * [hpuns: parallel jeux de mots (plays on words)][b2] HPuns is a valuable tool for making your future (French speaking) children's lives miserable. It generates awful puns from names, and in parallel, no less! Paul Brauner was just looking for some parallel “speedups out of the box.“ Where he was previously was able to get only a mediocre speedup with Strategies, with the monad-par package he was able to knock out a quick 1.3x speedup (-N3) over a lunchbreak. HPuns may just be a toy (one file!) but it could be what you're looking for if monad-par usage examples is what you're after. * [Accelerate version 0.12: GPU computing with Haskell][b5] (14 May) Manuel Chakravarty the recent 0.12 release of Accelerate, with full sharing recovery in scalar expressions and array computations, some more examples, and bug fixes. Accelerate should still be considered a beta release, but the folks at UNSW are hungry for early adopters. So do give it a try! * [How to write hybrid CPU/GPU programs with Haskell][b3] (4 May) If you like your monad-par and your Accelerate working together, consider this proposition from Ryan Newton: “What’s better than programming a GPU with a high-level, Haskell-embedded DSL (domain-specific-language)? Well, perhaps writing portable CPU/GPU programs that utilize both pieces of silicon…” Ryan walks us through installing the recently released meta-par packages and writing some simple hybrid code. The general idea seems to be to define CPU and GPU implementations of a task and to allow the generalised work-stealing scheduler to choose between them; the promise being that if a program performs much better on one device (say the GPU), that device will wind up doing most of the work. More generally, the meta-par family of packages is aimed at heterogeneous programming (it provides a mechanism for building parallel schedulers out of "mix-in" components). Ryan's post focuses on the CPU/GPU scenario, but there are also future packages coming our way for distributed programming too. If you are interested in learning more, have a look at the [meta-par GitHub][meta-par] page and the the draft paper [A Meta-Scheduler for the Par-Monad][meta-par-paper]. Mailing lists ---------------------------------------------------------------------- * [Is protocol-buffers package maintainer reachable?][m1] (23 Apr) Paul Graphov finds the protocol-buffers and hprotoc packages failing to build with the latest GHC. Unfortunately, he seems to be having trouble getting his patches to maintainer Chris Kuklewicz. The mailing list thread came up with suggestions for places we might get in touch with Chris, and also touched on a sort of recurring dilemma in the Haskell community: what do we do when package maintainers disappear? The general feeling seems to be that provided we can find a new maintainer, we should discuss it on the mailing list, then go ahead and take over. * [Threads and hGetLine][m5] (28 Apr) H.M. has a simplified scenario he's having trouble with: suppose you have thread waiting on input with `hGetLine`, and you have a supervisor thread to close the handle and/or kill the first thread. How do you make it work? It seems that `hClose` and `killThread` do not work for H. because the first thread is blocking for input. Alvaro Gutierrez suggests perhaps using a different approach which doesn't involve killing threads, perhaps non-blocking IO and a synchronised condition variable. Perhaps H.M. is on Windows? Joey Adams points out that “GHC currently doesn't have proper IO manager support for Windows. On Windows, IO is performed through FFI calls. An FFI call masks asynchronous exceptions… If another thread tries to `killThread` the thread waiting for input, the exception will not be received until the FFI call completes. This means both threads will hang.” * [using ResourceT with MVars][m2] (2 May) Warren Harris would like to use LevelDB (an open source on-disk key-value store inspired by BigTable). Unfortunately for Warren, the 0.0.3 version of leveldb-haskell switches from `get`/`put` in the `IO` monad to `ResourceT`. This makes it tricky for him to write code like withMVar state $ \db -> do maybeValue <- get db rdOpts key put db wrOpts key $ maybe init incr maybeValue In effect, the question is “how do I run MVar operations in ResourceT?” Michael Snoyman suggests the [lifted-based][lifted-base] package for exactly this. Lifted-base exports IO operations from the base library lifted to any instance of `MonadBase` or `MonadBaseControl`. Warren can use any of the `Control.Concurrent.MVar.Lifted` functions since `ResourceT` is an instance of `MonadBaseControl` * [meaning of `__PARALLEL_HASKELL__` and -parallel][m3] (13 Apr) Facundo Domínguez was wondering what the `__PARALLEL_HASKELL__` CPP macro, and the `-parallel` flags stand for. Jost Berthold explains that they both relate to parallel versions of GHC on distributed memory platforms. * [Can Haskell outperform C++?][m4] (6 May) Janek S. has seen claims floating around the internet that Haskell programs can have comparable performance to C and C++ versions. He's also seen claims about the promise of functional programming for automatically parallelising the software. Is there any evidence for these claims? This is a tricky question to pin down, and one that is vulnerable to apple/orange comparisons (some suggestions in the thread, [1][donscore], [2][bfusion], [3][shootout]) or debates about what makes a programming language desirable. Janek's question sparked a fairly epic thread, maybe worth digging through if you're struggled with Haskell performance before; or are member of the shadowy Haskell propaganda committee. For parallel Haskellers, I'll pick out a handful of sub-topics that came up. Ertugrul Söylemez makes a general comment to look at the bigger picture. While (currently) seldomly beats C/C++ for number crunching algorithms, “where [it] really gets beyond C and C++ is in concurrency. Multithreaded network servers written in Haskell are not only a lot easier to write, but they also perform better than well written server programs in C/C++. This is because Haskell's concurrency goes well with its parallel execution model, where in machine code you don't really have a notion of procedures. You have thunks and they can not only be executed in parallel, but they can also be moved between threads freely.” As for automatic parallelisation, Simon Marlow points out that there isn't yet any fully implicit parallelism in Haskell. What Haskell does provide, on the other hand, is a “a guarantee that you can safely call any function in parallel… as long as the function does not have an IO type”. So while fully automatic parallelism isn't here (and may not ever be), you can at least take an arbitrary piece of Haskell code and use it with something like `parMap`, or call it from mulitple threads, and expect some sort of speedup from it; and safely, with a fully deterministic result and no nasty concurrency bugs to worry about. Finally, showing how it can be tricky to performance can be quite tricky, Ryan Newton had an example in his monad-par repo of a (rather C-ish) [aggressively optimised Haskell program][mandel] that was 6⨉ slower than its counterpart and worse 9⨉ with the new LLVM backend (said backend has been helpful in other cases, though, eg. for Manuel Chakravarty). There's a happy ending behind this. After some digging, Ryan uncovered a clever math trick used in the OCaml standard library. Porting it to Haskell makes his program not only faster than OCaml and Scheme but 48% faster than C++ too! Looks like we'll be getting a library patch from Ryan soon. “The moral,” Ryan comments, “is that community members could do a great deal to help "Haskell" performance by simply microbenchmarking and optimizing library routines in base!” StackOverflow and Reddit ---------------------------------------------------------------------- This month saw quite a lot of activity on StackOverflow, largely from [user Clinton][so-clinton] trying to puzzle through STM and other concurrency issues. The STM and `atomicModifyIORef` series of questions could be interesting, at the very least, to see what sorts of things people wonder about when they first run into Haskell concurrency. ## General questions * [Identifying the current HEC for a function in Haskell][s1] * [Haskell parallel computation using an STArray][s2] * [Slowdown when using parallel strategies in Haskell][s3] * [Haskell parallel performance][s4] * [“Monad-friendly” event-based IO][s5] * [Haskell concurrency - is forkIO really nondeterministic?][s6] * [TimeoutManager uses tryPutMVar to put nothing][s8] * [Software transactional memory with a big, shared piece of data][s9] ## STM * [How does TVar work?][sc11] * [Container for Haskell TVars][s7] * [Updating two or more TVars atomically. Possible?][sc10] * [TVar: Preventing starvation][sc9] * [TVar: orElse][sc8] * [Concurrent generic data structure without deadlocks or resource starvation][sc7] * [Concurrent data structure guidelines][sc2] * [“Wait-free” data in Haskell][sc1] ## atomicModifyIORef * [How does 'atomicModifyIORef' work?][sc6] * [Concurrency using simple IORef?][sc5] * [Atomic IO wrapper/laziness?][sc4] * [Attempt at parallel `atomicModifyIORef` implementation][sc3] * [Concurrent data structure guidelines][sc2] ## Reddit * [SPJ talk: Towards Haskell in the Cloud : haskell][r1] * [Revamped Haskell concurrency and parallelism libraries page: from parallel arrays to Cloud Haskell : haskell][r2] 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! [lifted-base]: http://hackage.haskell.org/package/lifted-base [tutorial-sm]: http://community.haskell.org/~simonmar/par-tutorial.pdf [ph-digest-6]: http://www.well-typed.com/blog/60 [ph-digest-9]: http://www.well-typed.com/blog/65 [so-clinton]: http://stackoverflow.com/users/525980/clinton [meta-par]: https://github.com/simonmar/monad-par/ [meta-par-paper]: http://www.cs.indiana.edu/~rrnewton/papers/meta-par_submission.pdf [donscore]: http://donsbot.wordpress.com/2007/11/29/use-those-extra-cores-and-beat-c-to… [bfusion]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.3166 [mandel]: https://github.com/simonmar/monad-par/blob/662fa05b2839c8a0a6473dc490ead8dd… [shootout]: http://shootout.alioth.debian.org/ [rwh]: http://book.realworldhaskell.org/ [yesodbook]: http://www.yesodweb.com/book [sm-cefp]: http://community.haskell.org/~simonmar/papers/par-tutorial-cefp-2012.pdf [yesod-book]: http://www.yesodweb.com/book [n0]: http://www.google-melange.com/gsoc/project/google/gsoc2012/lorehead/36001 [n1]: http://www.haskell.org/pipermail/haskell/2012-April/023275.html [n2]: http://www.multicore-challenge.org/ [n3]: https://www.vacancies.st-andrews.ac.uk//ViewVacancy.aspx?enc=mEgrBL4XQK0+ld… [n4]: http://www.haskell.org/pipermail/haskell/2012-May/023328.html [b1]: http://www.haskell.org/haskellwiki/Applications_and_libraries/Concurrency_a… [b2]: http://code.google.com/p/hpuns/source/browse/Main.hs [b3]: http://parfunk.blogspot.co.uk/2012/05/how-to-write-hybrid-cpugpu-programs.h… [b4]: http://www.haskell.org/pipermail/haskell-cafe/2012-May/101113.html [b5]: http://justtesting.org/gpu-accelerated-array-computations-in-haskell [v1]: http://skillsmatter.com/podcast/home/haskell-cloud/js-4179 [m1]: http://www.haskell.org/pipermail/haskell-cafe/2012-April/100867.html [m2]: http://www.haskell.org/pipermail/haskell-cafe/2012-May/101027.html [m3]: https://groups.google.com/d/msg/parallel-haskell/kU0Ndl-IH3Y/GoQog9psZJIJ [m4]: http://www.haskell.org/pipermail/haskell-cafe/2012-May/101123.html [m5]: http://www.haskell.org/pipermail/haskell-cafe/2012-April/100988.html [s1]: http://stackoverflow.com/questions/10105127/identifying-the-current-hec-for… [s2]: http://stackoverflow.com/questions/10079710/haskell-parallel-computation-us… [s3]: http://stackoverflow.com/questions/10009361/slowdown-when-using-parallel-st… [s4]: http://stackoverflow.com/questions/9578416/haskell-parallel-performance [s5]: http://stackoverflow.com/questions/10364549/monad-friendly-event-based-io [s6]: http://stackoverflow.com/questions/10247555/haskell-concurrency-is-forkio-r… [s7]: http://stackoverflow.com/questions/10098506/container-for-haskell-tvars [s8]: http://stackoverflow.com/questions/9869763/timeoutmanager-uses-tryputmvar-t… [s9]: http://stackoverflow.com/questions/9547325/software-transactional-memory-wi… [r1]: http://www.reddit.com/r/haskell/comments/t0qg0/spj_talk_towards_haskell_in_… [r2]: http://www.reddit.com/r/haskell/comments/stn2b/revamped_haskell_concurrency… [sc1]: http://stackoverflow.com/questions/10239239/wait-free-data-in-haskell [sc2]: http://stackoverflow.com/questions/10220629/haskell-concurrent-data-structu… [sc3]: http://stackoverflow.com/questions/10203446/haskell-attempt-at-parallel-ato… [sc4]: http://stackoverflow.com/questions/10169434/haskell-atomic-io-wrapper-lazin… [sc5]: http://stackoverflow.com/questions/10115756/haskell-concurrency-using-simpl… [sc6]: http://stackoverflow.com/questions/10102881/haskell-how-does-atomicmodifyio… [sc7]: http://stackoverflow.com/questions/10101861/haskell-concurrent-generic-data… [sc8]: http://stackoverflow.com/questions/10101044/haskell-tvar-orelse [sc9]: http://stackoverflow.com/questions/10099990/haskell-tvar-preventing-starvat… [sc10]: http://stackoverflow.com/questions/10099815/haskell-updating-two-or-more-tv… [sc11]: http://stackoverflow.com/questions/10092655/haskell-how-does-tvar-work -- Eric Kow <http://erickow.com>

1 0

Data Kinds and superfluous (in my opinion) constraints contexts
by Serguey Zefirov 17 May '12

17 May '12

I decided to take a look at DataKinds extension, which became available in GHC 7.4. My main concerns is that I cannot close type classes for promoted data types. Even if I fix type class argument to a promoted type, the use of encoding function still requires specification of context. I consider this an omission of potentially very useful feature. Example is below. ----------------------------------------------------------------------------------------- {-# LANGUAGE TypeOperators, DataKinds, TemplateHaskell, TypeFamilies, UndecidableInstances #-} {-# LANGUAGE GADTs #-} -- a binary numbers. infixl 5 :* data D = D0 | D1 | D :* D deriving Show -- encoding for them. data EncD :: D -> * where EncD0 :: EncD D0 EncD1 :: EncD D1 EncDStar :: EncD (a :: D) -> EncD (b :: D) -> EncD (a :* b) -- decode of values. fromD :: D -> Int fromD D0 = 0 fromD D1 = 1 fromD (d :* d0) = fromD d * 2 + fromD d0 -- decode of encoded values. fromEncD :: EncD d -> Int fromEncD EncD0 = 0 fromEncD EncD1 = 1 fromEncD (EncDStar a b) = fromEncD a * 2 + fromEncD b -- constructing encoded values from type. -- I've closed possible kinds for class parameter (and GHC successfully compiles it). -- I fully expect an error if I will try to apply mkD to some type that is not D. -- (and, actually, GHC goes great lengths to prevent me from doing that) -- By extension of argument I expect GHC to stop requiring context with MkD a where -- I use mkD "constant function" and it is proven that a :: D. class MkD (a :: D) where mkD :: EncD a instance MkD D0 where mkD = EncD0 instance MkD D1 where mkD = EncD1 -- But I cannot omit context here... instance (MkD a, MkD b) => MkD (a :* b) where mkD = EncDStar mkD mkD data BV (size :: D) where BV :: EncD size -> Integer -> BV size bvSize :: BV (size :: D) -> Int bvSize (BV size _) = fromEncD size -- ...and here. -- This is bad, because this context will arise in other places, some of which -- are autogenerated and context for them is incomprehensible to human -- reader. -- (they are autogenerated precisely because of that - it is tedious and error prone -- to satisfy type checker.) fromIntgr :: Integer -> BV (size :: D) -- doesn't work, but desired. -- fromIntgr :: MkD size => Integer -> BV (size :: D) -- does work, but is not that useful. fromIntgr int = BV mkD int -----------------------------------------------------------------------------------------

4 5

Fwd: Can Haskell outperform C++?
by Colin Adams 17 May '12

17 May '12

Oops. Forget to reply to all. ---------- Forwarded message ---------- From: Colin Adams <colinpauladams(a)gmail.com> Date: 17 May 2012 08:43 Subject: Re: [Haskell-cafe] Can Haskell outperform C++? To: Roman Werpachowski <roman.werpachowski(a)gmail.com> On 17 May 2012 07:12, Roman Werpachowski <roman.werpachowski(a)gmail.com>wrote: > > It depends on what you use the code for. If I run an overnight report > for the trading book of my bank in 16 hours, it is > not acceptable and is a disaster. If I run it in 8h, it's OK-ish. In > business settings, you often have strict deadlines and > optimizing the code to be 2x faster can make a huge difference, as you > change from missing the deadline to > meeting a deadline. > > Seconded. I remember once being asked to examine a certain batch program for performance improvements. I spotted an obvious inefficiency, and made a recommendation, which was implemented. It saved something like 10 - 30 minutes on the overnight run (which took hours), so I was disappointed with the result. But the client was delighted, as the run now fitted into the batch window.

1 0

Re: [Haskell-cafe] Can Haskell outperform C++?
by Roman Werpachowski 17 May '12

17 May '12

> Date: Wed, 16 May 2012 06:54:08 -0400 > From: wren ng thornton <wren(a)freegeek.org> > Subject: Re: [Haskell-cafe] Can Haskell outperform C++? > To: haskell-cafe(a)haskell.org > Message-ID: <4FB38750.9060009(a)freegeek.org> > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > But on the other hand, there are quite a lot of people who focus > excessively on "optimization" when the actual differences for the code > they're writing are either negligible (e.g., because of I/O bottlenecks) > or uninteresting (e.g., a 2x slowdown is a nuisance rather than a > crisis). It depends on what you use the code for. If I run an overnight report for the trading book of my bank in 16 hours, it is not acceptable and is a disaster. If I run it in 8h, it's OK-ish. In business settings, you often have strict deadlines and optimizing the code to be 2x faster can make a huge difference, as you change from missing the deadline to meeting a deadline. Regards, RW

1 0

Re: [Haskell-cafe] Can Haskell outperform C++?
by Richard O'Keefe 17 May '12

17 May '12

On 17/05/2012, at 2:04 PM, Gregg Lebovitz wrote: > Richard, > > Thank you. This is an example of what I had in mind when I talked about changing the playing field. Do you have a slide deck for this lecture that you would be willing to share with me? I am very interested in learning more. No slide deck required. The task is "generating alternating permutations". Method 1: generate permutations using a backtracking search; when a permutation is generated, check if it is alternating. Method 2: use the same backtracking search, but only allow extensions that preserve the property of being an alternating permutation. For n=12 the second method is 94 times faster than the first, and the ratio increases with growing n. At the time I wrote the program I had not heard of Bauslaugh and Ruskey's constant-average-time algorithm for generating alternating permutations. Experimentally the Method 2 backtracking search appears to take constant time per solution anyway. n (time ms): En n! 1 ( 0.0): 1 1 <- method 1 1 ( 0.0): 1 <- method 2 2 ( 0.0): 1 2 2 ( 0.0): 1 3 ( 0.0): 2 6 3 ( 0.0): 2 4 ( 0.0): 5 24 4 ( 0.0): 5 5 ( 0.0): 16 120 5 ( 0.0): 16 6 ( 0.1): 61 720 6 ( 0.0): 61 7 ( 0.6): 272 5040 7 ( 0.1): 272 8 ( 4.4): 1385 40320 8 ( 0.3): 1385 9 ( 35.2): 7936 362880 9 ( 1.4): 7936 10 ( 359.7): 50521 3628800 10 ( 9.3): 50521 11 ( 4035.7): 353792 39916800 11 ( 67.0): 353792 12 (49584.6): 2702765 479001600 <- method 1 12 ( 528.1): 2702765 <- method 2 Those times are in C; SWI Prolog (which compiles to an abstract instruction set that is then interpreted by portable C) was about 24 times slower. A factor of 94 comfortably exceeds a factor of 24...

1 0

Haskell Weekly News: Issue 227
by Daniel Santa Cruz 17 May '12

17 May '12

Welcome to issue 227 of the HWN, an issue covering crowd-sourced bits of information about Haskell from around the web. This issue covers the week of May 6 to 12, 2012. Announcements Doaitse Swierstra reminded us about the Summer School on Applied Functional Programming, at Utrech University. Hurry to check it out, as the deadline for registration is May 20th! [1] http://goo.gl/TZYdd Janis Voigtlander announced the release of the 22nd edition of the Haskell Communities and Activities Report. [2] http://goo.gl/pXIZn Quotes of the Week * dcoutts: (on #darcs): "[on github:] it's like the facebook of source repos" * dmwit: "Functional programming" is a technical term that means more than just what the two words mean separately. * Axman6: "GHC Warning: Did you see that in an OOP textbook? You probably don't want to be doing that" * StevenKaas: Haskell's Wager: what if infinite lists can suffer infinitely even when lazily evaluated? * quicksilver: "Patent covering a device for emitting greetings to the world community as a whole in computer-readable format" (US Patent no 1787528391) Top Reddit Stories * Videos to the functional programming course I attend are freely available. I thought you might enjoy them. Domain: self.haskell, Score: 47, Comments: 10 On Reddit: [3] http://goo.gl/SoV7x Original: [4] http://goo.gl/SoV7x * red-black trees in haskell, using GADTs, existential types, and zippers, oh my Domain: gist.github.com, Score: 40, Comments: 21 On Reddit: [5] http://goo.gl/Ae08L Original: [6] http://goo.gl/iDxjY * Equality proofs and deferred type errors, A compiler pearl [Vytiniotis, Peyton Jones,Magalhaes PDF] Domain: research.microsoft.com, Score: 40, Comments: 17 On Reddit: [7] http://goo.gl/6OUbX Original: [8] http://goo.gl/OP6ep * LLVM now supports NVIDIA GPU's Domain: nvidianews.nvidia.com, Score: 36, Comments: 19 On Reddit: [9] http://goo.gl/DF7sY Original: [10] http://goo.gl/rvYdL * The Architecture of Open Source Applications, Volume II (with chapters on GHC and Yesod, royalties go to Amnesty International) Domain: lulu.com, Score: 35, Comments: 9 On Reddit: [11] http://goo.gl/XfsXB Original: [12] http://goo.gl/1sr6u * Jesper's Blog: My Take on Haskell vs Scala Domain: jnordenberg.blogspot.com, Score: 29, Comments: 8 On Reddit: [13] http://goo.gl/3EM45 Original: [14] http://goo.gl/aWGgn * Haskell Communities and Activities Report --- May 2012 Domain: haskell.org, Score: 27, Comments: 3 On Reddit: [15] http://goo.gl/q8XFZ Original: [16] http://goo.gl/fW3Sf * Keter: Web App Deployment Domain: yesodweb.com, Score: 23, Comments: 19 On Reddit: [17] http://goo.gl/VOSVF Original: [18] http://goo.gl/OJ783 * A small and simple tip for Google Code Jam-mers Domain: self.haskell, Score: 22, Comments: 15 On Reddit: [19] http://goo.gl/9QPDW Original: [20] http://goo.gl/9QPDW * Composable Value Editors for GTK Domain: twdkz.wordpress.com, Score: 21, Comments: On Reddit: [21] http://goo.gl/w4WoR Original: [22] http://goo.gl/LevtB * The Brittleness of Type Hierarchies (codegrunt.co.uk) and a Haskell approach Domain: self.haskell, Score: 16, Comments: 17 On Reddit: [23] http://goo.gl/w4m8o Original: [24] http://goo.gl/w4m8o Top StackOverflow Questions * Static types, polymorphism and specialization votes: 18, answers: 3 Read on SO: [25] http://goo.gl/wxDZt * Redoing the standard classes [closed] votes: 12, answers: 2 Read on SO: [26] http://goo.gl/22MCG * Using Cont to acquire values from the future and the past votes: 11, answers: 1 Read on SO: [27] http://goo.gl/1zSVo * Why is `($ 4) (> 3)` equivalent to `4 > 3`? votes: 9, answers: 3 Read on SO: [28] http://goo.gl/5oTei * Recursively defined instances and constraints votes: 9, answers: 1 Read on SO: [29] http://goo.gl/uliWA * Freeing memory allocated with newCString votes: 8, answers: 1 Read on SO: [30] http://goo.gl/k3Izw * What is the meaning of “quasi” in quasiquotations? votes: 8, answers: 5 Read on SO: [31] http://goo.gl/YjPbl * Ensuring files are closed promptly votes: 7, answers: 3 Read on SO: [32] http://goo.gl/UCKSB * Is there ever a good reason to use unsafePerformIO? votes: 7, answers: 5 Read on SO: [33] http://goo.gl/y2meC * What characters are permitted for haskell operators? votes: 7, answers: 3 Read on SO: [34] http://goo.gl/0n1kX * Defining an algebra module using constructive-algebra package votes: 6, answers: 2 Read on SO: [35] http://goo.gl/vqIcG * Haskell: Type safety with logically different Boolean values votes: 6, answers: 3 Read on SO: [36] http://goo.gl/f1Gtz * Data structure to represent automata votes: 5, answers: 2 Read on SO: [37] http://goo.gl/MhsvC Until next time, Daniel Santa Cruz References 1. http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/98235 2. http://permalink.gmane.org/gmane.comp.lang.haskell.general/19294 3. http://www.reddit.com/r/haskell/comments/tgz57/videos_to_the_functional_pro… 4. http://www.reddit.com/r/haskell/comments/tgz57/videos_to_the_functional_pro… 5. https://gist.github.com/2659812 6. http://www.reddit.com/r/haskell/comments/ti5il/redblack_trees_in_haskell_us… 7. http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/icfp12.p… 8. http://www.reddit.com/r/haskell/comments/tjnzj/equality_proofs_and_deferred… 9. http://nvidianews.nvidia.com/Releases/NVIDIA-Contributes-CUDA-Compiler-to-O… 10. http://www.reddit.com/r/haskell/comments/tgdia/llvm_now_supports_nvidia_gpu… 11. http://www.lulu.com/shop/amy-brown-and-greg-wilson/the-architecture-of-open… 12. http://www.reddit.com/r/haskell/comments/teqai/the_architecture_of_open_sou… 13. http://jnordenberg.blogspot.com/2012/05/my-take-on-haskell-vs-scala.html 14. http://www.reddit.com/r/haskell/comments/tedrh/jespers_blog_my_take_on_hask… 15. http://www.haskell.org/communities/05-2012/html/report.html 16. http://www.reddit.com/r/haskell/comments/tivjx/haskell_communities_and_acti… 17. http://www.yesodweb.com/blog/2012/05/keter-app-deployment 18. http://www.reddit.com/r/haskell/comments/thygx/keter_web_app_deployment/ 19. http://www.reddit.com/r/haskell/comments/ta5lx/a_small_and_simple_tip_for_g… 20. http://www.reddit.com/r/haskell/comments/ta5lx/a_small_and_simple_tip_for_g… 21. http://twdkz.wordpress.com/2012/05/10/composable-value-editors/ 22. http://www.reddit.com/r/haskell/comments/tg58a/composable_value_editors_for… 23. http://www.reddit.com/r/haskell/comments/tdmt5/the_brittleness_of_type_hier… 24. http://www.reddit.com/r/haskell/comments/tdmt5/the_brittleness_of_type_hier… 25. http://stackoverflow.com/questions/10534744/static-types-polymorphism-and-s… 26. http://stackoverflow.com/questions/10500320/redoing-the-standard-classes 27. http://stackoverflow.com/questions/10560124/using-cont-to-acquire-values-fr… 28. http://stackoverflow.com/questions/10476883/why-is-4-3-equivalent-to-4-3 29. http://stackoverflow.com/questions/10529360/recursively-defined-instances-a… 30. http://stackoverflow.com/questions/10513007/freeing-memory-allocated-with-n… 31. http://stackoverflow.com/questions/10556631/what-is-the-meaning-of-quasi-in… 32. http://stackoverflow.com/questions/10518049/ensuring-files-are-closed-promp… 33. http://stackoverflow.com/questions/10529284/is-there-ever-a-good-reason-to-… 34. http://stackoverflow.com/questions/10548170/what-characters-are-permitted-f… 35. http://stackoverflow.com/questions/10536990/defining-an-algebra-module-usin… 36. http://stackoverflow.com/questions/10544984/haskell-type-safety-with-logica… 37. http://stackoverflow.com/questions/10516603/data-structure-to-represent-aut…

1 0

Haskell Symposium 2012 - deadline approaching
by Janis Voigtländer 17 May '12

17 May '12

[Deadline for submission of abstracts is in two weeks. The submission page is open, earlier submissions welcome.] ======================================================================== "Haskell 2012" ACM SIGPLAN Haskell Symposium 2012 Copenhagen, Denmark 13th September, 2012 (directly after ICFP) CALL FOR PAPERS http://www.haskell.org/haskell-symposium/2012/ ======================================================================== The ACM SIGPLAN Haskell Symposium 2012 will be co-located with the 2012 International Conference on Functional Programming (ICFP), in Copenhagen, Denmark. The purpose of the Haskell Symposium is to discuss experiences with Haskell and future developments for the language. Topics of interest include, but are not limited to: * Language Design, with a focus on possible extensions and modifications of Haskell as well as critical discussions of the status quo; * Theory, such as formal treatments of the semantics of the present language or future extensions, type systems, and foundations for program analysis and transformation; * Implementations, including program analysis and transformation, static and dynamic compilation for sequential, parallel, and distributed architectures, memory management as well as foreign function and component interfaces; * Tools, in the form of profilers, tracers, debuggers, pre-processors, testing tools, and suchlike; * Applications, using Haskell for scientific and symbolic computing, database, multimedia, telecom and web applications, and so forth; * Functional Pearls, being elegant, instructive examples of using Haskell; * Experience Reports, general practice and experience with Haskell, e.g., in an education or industry context. Papers in the latter three categories need not necessarily report original research results; they may instead, for example, report practical experience that will be useful to others, reusable programming idioms, or elegant new ways of approaching a problem. (Links with more advice appear on the symposium web page.) The key criterion for such a paper is that it makes a contribution from which other Haskellers can benefit. It is not enough simply to describe a program! Regular papers should explain their research contributions in both general and technical terms, identifying what has been accomplished, explaining why it is significant, and relating it to previous work (also for other languages where appropriate). In addition, we solicit proposals for system demonstrations, based on running (perhaps prototype) software rather than necessarily on novel research results. Such short demo proposals should explain why a demonstration would be of interest to the Haskell community. Travel Support: =============== Student attendees with accepted papers can apply for a SIGPLAN PAC grant to help cover travel expenses. PAC also offers other support, such as for child-care expenses during the meeting or for travel costs for companions of SIGPLAN members with physical disabilities, as well as for travel from locations outside of North America and Europe. For details on the PAC programme, see its web page (http://www.sigplan.org/PAC.htm) Proceedings: ============ There will be formal proceedings published by ACM Press. In addition to printed proceedings, accepted papers will be included in the ACM Digital Library. Authors must transfer copyright to ACM upon acceptance (for government work, to the extent transferable), but retain various rights (http://www.acm.org/publications/policies/copyright_policy) Authors are encouraged to publish auxiliary material with their paper (source code, test data, etc.); they retain copyright of auxiliary material. Accepted demo proposals, assessed for relevance by the PC, will be published on the symposium web page, but not formally published in the proceedings. Submission Details: =================== * Abstract Submission: Thu 31st May 2012 * Paper Submission : Sat 2nd June 2012, anywhere on earth * Author Notification: Wed 27th June 2012 * Final Papers Due : Tue 10th July 2012 Submitted papers should be in portable document format (PDF), formatted using the ACM SIGPLAN style guidelines (9pt format, more details appear on the symposium web page). The length is restricted to 12 pages, except for "Experience Report" papers, which are restricted to 6 pages. Each paper submission must adhere to SIGPLAN's republication policy, as explained on the web. Demo proposals are limited to 2-page abstracts, in the same format. "Functional Pearls", "Experience Reports", and "Demo Proposals" should be marked as such with those words in the title at time of submission. The paper submission deadline and length limitations are firm. There will be no extensions, and papers violating the length limitations will be summarily rejected. Submission is via EasyChair: https://www.easychair.org/conferences/?conf=haskell2012 Programme Committee: ==================== * Amal Ahmed, Northeastern University * Jost Berthold, University of Copenhagen * Nils Anders Danielsson, University of Gothenburg * Iavor Diatchki, Galois Inc. * Jeremy Gibbons, University of Oxford * Jurriaan Hage, Utrecht University * Zhenjiang Hu, National Institute of Informatics Tokyo * Daan Leijen, Microsoft Research * Ben Lippmeier, University of New South Wales * Simon Peyton Jones, Microsoft Research * Colin Runciman, University of York * Eijiro Sumii, Tohoku University * Janis Voigtländer (chair), University of Bonn * Brent Yorgey, University of Pennsylvania Links: ====== * http://www.haskell.org/haskell-symposium (the permanent web page of the Haskell Symposium) * http://www.haskell.org/haskell-symposium/2012 (the 2012 Haskell Symposium web page) * http://www.icfpconference.org/icfp2012 (the ICFP 2012 web page)

1 0

import IO
by A Smith 16 May '12

16 May '12

Hi folks I need a little help. I had a hiccup upgrading my Ubuntu system, and eventually did a fresh install. Its mostly fixed to my old favourite ways but I cannot remember what's needed to install the stuff that the "import IO" statement uses! -- Andrew

2 1

ANN: variable-precision floating point
by Claude Heiland-Allen 16 May '12

16 May '12

Hi all, I'm pleased to announce variable-precision-0.2: http://hackage.haskell.org/package/variable-precision There was no announcement for previous versions, as I quickly found their flaws to be too irritating in practice. --8<-- excerpt from the hackage page Software floating point with type-tagged variable mantissa precision, implemented using a strict pair of Integer and Int scaled alike to decodeFloat. Instances of the usual numeric type classes are provided, along with additional operators (with carefully chosen fixities) to coerce, adjust and reify precisions. --8<-- end excerpt Known shortcomings of this release: * no implementation of (inverse) (hyperbolic) trigonometric functions * no support for negative zero * no support for rounding modes * accuracy has not been extensively verified * termination of algorithms has not been proven The intention of this package is to be simple yet useable in the meantime until there is a version of hmpfr[1] or fixed-precision[2] that work without requiring a custom-compiled GHC. The design of variable-precision was inspired by the latter, and variable-precision is probably inferior, but the lifetime of the variable-precision package is hopefully going to be short. [1] http://hackage.haskell.org/package/hmpfr [2] http://hackage.haskell.org/package/fixed-precision I'm currently mainly using variable-precision for exploring the Mandelbrot Set, particularly in algorithms using Newton's method (for example, tracing external rays, where more precision is needed the closer you get to the boundary of the set). Thanks, Claude PS: --8<-- excerpt from ghci session Prelude Numeric.VariablePrecision> (pi :: F24) .@$ 200 $ show . (pi -) "1.5815072737072126433832795028841971693993751058209749096292229e-6" Prelude Numeric.VariablePrecision> (pi :: F53) .@$ 200 $ show . (pi -) "4.1192675685652988632476805983544532308209749096292228904414057e-15" Prelude Numeric.VariablePrecision> (2 :: F53) .@$ 200 $ show . log "0.69314718055994530941723212145817656807550013436025525413214402" Prelude Numeric.VariablePrecision> log 2 0.6931471805599453 Prelude Numeric.VariablePrecision> (2 :: F53) .@$ 200 $ show . exp "7.3890560989306502272304274605750078131803155705518473240869941" Prelude Numeric.VariablePrecision> exp 2 7.38905609893065 --8<-- end excerpt

1 0

Can't prevent memoizing in simple code
by Yves Parès 16 May '12

16 May '12

The buffer http://hpaste.org/68595 presents a simple code I tried to profile. I spotted what I strongly think to be an abusive memoization. The problem is that I don't see how to (simply) get rid of it. Compiled with -O2, it consumes 130MB of memory, however lines A and B executed separately consume each only 1MB. The infinite list (l 1), whatever I do, keeps being shared between lines A and B. I tried to wrap it in a function, as you can see, I also tried to make it explicitely polymorphic (bypassing monomorphic restriction), nothing solves it, GHC is just to good at memoizing. NB: When compiled without optimisations, the sharing does not happen (side note: but then lack of strictness analysis -- which is what I was testing at the first place -- makes line A (call to suminit2) consume a lot of memory, but this is normal).

2 2

Call for AusHac 2012
by Ivan Lazar Miljenovic 16 May '12

16 May '12

For any Australian Haskellers (or indeed anyone that feels willing to come from wherever you may hail) who have _not_ yet received an email, seen it on Reddit or Google+ but is interested in attending AusHac 2012, we are currently trying to determine which weekend in July best suits everyone. So if you're interested in coming, please fill out the form at http://tinyurl.com/AusHac2012PreferredDates This year we're going to hold AusHac in central Sydney (thanks to Atlassian putting their offices at our disposal!) rather than UNSW, which should make transport and accommodation easier for people. AusHac is open to anyone interested in Haskell, from a complete newbie to one of the Simons. We don't have any specific themes or projects to work on; instead just come along and hack on whatever takes your fancy. -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com http://IvanMiljenovic.wordpress.com

1 0

hackage & hackage accounts
by Dmitry Malikov 16 May '12

16 May '12

Good day. Recently, in irc://#haskell you can see very often replicas of people, who are tired of waiting their hackage accounts. After next release of any package from hackagebot, some depressed people definitely comes out and starts telling to everybody how hard life is without having hackage account. 11:15 * hackagebot shakespeare 1.0.0.2 - A toolkit for making compile-time interpolated templates http://hackage.haskell.org/package/shakespeare-1.0.0.2 (MichaelSnoyman) 11:15 <|> I'm still waiting for my Hackage account... ... 15:12 * hackagebot hspec-discover 0.0.0 - Automatically discover and run Hspec tests http://hackage.haskell.org/package/hspec-discover-0.0.0 (SimonHengel) 15:13 <|> Still haven't got my hackage account And so on and so on. Yes, you can tolerate, that a lot of people considered in the order of things for asking lambdabot in public window every day, every hour. Yes, you can tolerate, that every five minutes some another notification from hackagebot will be be appeared, or maybe two or even three in a time. But how can you tolerate, that adding to all that stuff there is a permanent disturbances from the people, who can't submit their packages to hackage because they have no hackage account (frankly speaking, I'm also do not have one, but I've send 5 letters to Ross)? Previously, #haskell's log was really like something readable and interesting. But now it's a robot-like speeches with 2 bots, minimal slightly mixed with something really meaningfull. This raises some questions: 1) Did anyone successfully get their hackage account in last 2 months? Because it's really strange to see some "still don't have my hackage account"-message and another Ross answer in HC. 2) You should give hackage account for all of ther requiring people or remove hackagebot from #haskell. 3) Could I finally have my hackage account in the amount of all others, please? Dmitry Malikov

3 2

How to use Jacobian from levmar lib?
by Martin Hilbig 15 May '12

15 May '12

hi, i'm using the nice levmar package like this [1]. why is there such a big difference in 'infNorm2E' between using/not using the Jacobian? thanks in advance martin hilbig [1]: http://hpaste.org/68537

1 0

Safe Haskell at the export symbol granularity?
by Ryan Newton 14 May '12

14 May '12

Separate from whether or not we actually want this -- is it feasible? Here's my situation. When working on parallel programming libraries in Haskell there are very often unsafe operations one wants to do within an otherwise pure model. For example, Accelerate currently violates safe haskell because it trusts the user to provide an associative function to parallel "fold". No associativity, no referential transparency. The solution is to put fold in a separate namespace and mark that module as Unsafe. Likewise for certain monad-par operations that are unsafe. But this factoring can have a serious impact. Not only are extra modules required, but extra type classes as well. For example, if Accelerate is ever refactored for "Safe Haskell" then the following ParAccelerate type class probably should be as well: https://github.com/simonmar/monad-par/blob/5cc656bc45dc473d7a185ec99bb15619… I.e. ParAccelerate & ParAccelerateUnsafe for the "unsafeHybrid" operation. But this starts to be death by a thousand organizational factorings! - The package, abstract-par-accelerate, is already factored out from abstract-par just to avoid an unnecessary Accelerate dependency (which used to mean CUDA errors). (And *another* factoring is possibly warranted for whether or not the module depends on accelerate-io.) - The file would be separate to mark it as Safe Haskell. - The type class ParAccelerateUnsafe would be separate so as to put it in a separate file. What's a possible solution? If, in addition to "Safe" and "Unsafe" modules, there were "Partially Safe" modules, which exported a mix of safe and unsafe identifiers, then this could all be much cleaner. The simple rule is that any reference whatsoever to an unsafe identifier disqualifies the client code. For example, in the above ParAccelerate type class we would mark the unsafeHybrid binding with something like {-# UNSAFE unsafeHybrid #-}. We wouldn't even have to factor it out of the type class. Likewise, Accelerate could mark "fold" as unsafe (providing safe variants as well) without introducing module namespace bloat and confusion. What do you think? -Ryan

1 0

[ANN] Accelerate version 0.12: GPU computing with Haskell
by Manuel M T Chakravarty 14 May '12

14 May '12

We just released version 0.12 of Data.Array.Accelerate, the GPGPU[1] library for Haskell: http://justtesting.org/gpu-accelerated-array-computations-in-haskell This is a beta release. The library is not perfect, but it is definitely usable, and we are looking for early adopters. Manuel [1] Currently only NVIDIA GPUs are supported via NVIDIA's CUDA framework.

1 0

Bug in SYB, SYB-documentation or GHC-API (or I messed up somewhere)
by "Philip K. F. Hölzenspies" 14 May '12

14 May '12

Dear Haskelers, Since I don't quite know whether this is a SYB-thing or a GHC-specific thing, I figured this report should go here. If not, kindly redirect. I am trying to write a program, using the GHC-API to refactor some parts of the GHC-code (initially, I want to add a type variable to the types in the AST to express the representation of types, as noted to be a Good Thing at [1]). To do this, I first search for all definitions of and references to type constructors. I do this using SYB. Consider these functions: type OccurrenceTable = [(RdrName, (SrcSpan,Bool))] locTyNames :: SrcSpan -> Bool -> HsType RdrName -> OccurrenceTable locTyNames l p (HsTyVar n ) = [(n, (l, p))] <… HSType-specific traversal cases omitted for brevity …> extTyNamesDef :: Data a => SrcSpan -> a -> OccurranceTable extTyNamesDef l x = gmapQl (++) [] (extTyNames l) x extTyNamesTy :: SrcSpan -> HsType RdrName -> OccurranceTable extTyNamesTy l x = locTyNames l True x extTyNames l x = (extTyNamesDef l x `mkQ` extTyNamesTy l) x The OccurrenceTable type collects for every type constructor (RdrName) the location of its occurrence (either definition or reference, SrcSpan) and whether adding a type variable (formal or actual) requires parenthesis (Bool). This works fine, although now, we always find the same SrcSpan for everything. When traversing an AST, whenever we find anything that's Located, we want to continue the traversal with this new location information. To this end, we define: extTyNamesLoc :: Data a => Located a -> OccurrenceTable extTyNamesLoc (L l x) = extTyNames l x and modify the universal entry point to: extTyNames l x = (extTyNamesDef l x `mkQ` extTyNamesTy l `ext1Q` extTyNamesLoc) x However, it turns out that this never leads to an evaluation of extTyNamesLoc. I've come as far as to see that, since "Located a" is a synonym for "GenLocated SrcSpan a", the type we're looking for really has a binary constructor, thus we should use ext2Q. This made things work: We first modify the function we apply to Located things: extTyNamesLoc :: (Data loc, Data a) => SrcSpan -> GenLocated loc a -> OccurrenceTable extTyNamesLoc l (L l' x) = case cast l' of Just l'' -> extTyNames l'' x Nothing -> extTyNames l x and define the universal entry point to be: extTyNames l x = (extTyNamesDef l x `mkQ` extTyNamesTy l `ext2Q` extTyNamesLoc l) x Even though I see why this works, I'm not completely sure why the former version does not. Is there no currying with type constructors (for SYB)? The cast I perform always succeeds, because all types that occur in the traversal are "Located x" and never "GenLocated NonSrcSpanType x". The extensions to extX functions (i.e. ext1Q, ext2Q, ext1T, etc.) are not very extensively documented. Their discussion in the ICFP04 paper only discusses their relation to TypeableX classes, but not to the partiality of type constructor application and/or synonyms. (As a side-note on that discussion in ICFP04, the remark that we're generally interested in type constructors with arguments of kind * sounded fine, until I started to try and parameterise the AST in the location-annotation-type as well; it made my brain hurt.) Apologies for the waffling, but comments would be greatly appreciated. Regards, Philip [1] http://hackage.haskell.org/trac/ghc/wiki/Commentary/Compiler/HsSynType

3 2

ANN: Patterns 0.0.3
by Tobias Schoofs 12 May '12

12 May '12

Hi! I am pleased to announce patterns-0.0.3. On Hackage: http://hackage.haskell.org/package/patterns The Patterns package implements communication patterns that are often used in distributed, message-oriented applications. The package implements a set of basic patterns and a device to connect basic patterns through routers, brokers, load balancers, etc. The package is based on the zeromq library, but abstracts from the notion of sockets, on which zeromq is built. Cheers Tobias

1 0

Linear Diaphantine equation solver bug
by John D. Ramsdell 12 May '12

12 May '12

I uploaded a new version of the ACU unifier in package cmu. It includes a Linear Diaphantine equation solver that now handles inhomogeneous equations. What's interesting is the algorithm is based on a paper by Contejean and Devie. That paper includes a proof of correctness of their algorithm. Yet I found an example in which following the steps in the order they gave, the algorithm produces extra answers. I had to switch the order of the steps in the algorithm to get the right answer. I wonder if anyone else knows of this issue. The example is given in the module documentation on Hackage. John http://hackage.haskell.org/packages/archive/cmu/1.6/doc/html/Algebra-Commut…

1 1

Problem with forall type in type declaration
by Magicloud Magiclouds 11 May '12

11 May '12

Hi, Assuming this: run :: Monad IO a -> IO a data Test = Test { f } Here I'd like to set f to run, like "Test run". Then what is the type of f? The confusing (me) part is that, the argument pass to f is not fixed on return type, like "f1 :: Monad IO ()", "f2 :: Monad IO Int". So "data Test a = Test { f :: Monad IO a -> IO a} does not work. -- 竹密岂妨流水过山高哪阻野云飞 And for G+, please use magiclouds#gmail.com.

4 6

Oxford Haskell Users Group
by Nicolas Wu 10 May '12

10 May '12

Dear all, I'd like to announce that the Oxford Haskell User's Group will be meeting up next week at 7pm on Tuesday 15th May. As is our custom, we'll be catching up over a few drinks in a local pub, this time, it's at the Three Goats Heads, St Michael's Street. Discussion is informal, with the occasional presentation about some interesting aspect of Haskell. All are welcome! If you'd like to be kept up to date about future meetings, which are roughly once a week during term time, then do join our mailing list, which can be found under OxHUG at google groups [1]. All the best, Nick [1]: http://groups.google.com/group/oxhug

1 0

ANNOUNCE: haskell-src-exts 1.13.3
by Niklas Broberg 10 May '12

10 May '12

Fellow Haskelleers, I'm pleased to announce the release of haskell-src-exts-1.13.3! * On hackage: http://hackage.haskell.org/package/haskell-src-exts * Via cabal: cabal install haskell-src-exts * Darcs repo: http://code.haskell.org/haskell-src-exts This release attempts to fix a bunch of long-standing (and a few new) bugs, while still avoiding a new major version bump. Changelog: 1.13.2 --> 1.13.3 =============== * Fundep premises are now allowed to be empty. * Fix the bug where the lexer would crash on a LINE pragma that did not include a line number. * Fix the bug where the lexer would require the # of a MagicHash-style type constructor to be succeeded by at least one character in the file. * Fix really long-standing bug where the parser would crash with an ugly "Internal error" error message if encountering an extra }. * Report errors at the right place for function arity mismatches. Earlier they were reported at end of file, now they are reported where the function is declared. * Lexer now properly fails on line-breaks in string literals. * Lexer now handles character escapes up to 0x10FFFF (unicode). Cheers, /Niklas

1 0

Gentle reminder: Summer school on Applied Functional Programming at Utrecht University; deadline for registration May 20
by S D Swierstra 10 May '12

10 May '12

Again we will teach an "Applied Functional Programming Summer in Haskell" school this year at Utrecht University. In the previous two occasions students were all very happy with the school and we plan to repeat this success this year. The intended audience are prospective master students who have been in contact with Functional Programming, e.g. by taking a general course on programming languages, and want to learn more about Haskell and its typical programming patterns. In the previous two years we have taught an introductory part (advanced bachelor level), an advanced part (beginning master level) and a shared part for both groups. Topics covered are, besides some examples of domain specific languages, also monads, monad transformers, arrows, parser combinators and self-analysing programs, underlying principles, type inferencing, etc. Half of the course time is spent on a larger programming exercise; you can also come with a problem of your own if you want, and get help from the Utrecht University Software Technology group in finding the proper Haskell idioms, tools and libraries, for solving it. Important links: -- our own page where we supply information based on questions asked http://www.cs.uu.nl/wiki/bin/view/USCS2012/WebHome -- the poster you can print and hang somewhere (why not your office door): http://www.cs.uu.nl/wiki/pub/USCS2012/WebHome/USCSpos12.pdf -- the official summerschool site where you can register: http://www.utrechtsummerschool.nl/index.php?type=courses&code=H9 Furthermore we ask for your cooperation to bring this announcement under the attention of potential participants. Best, Doaitse Swierstra PS: apologies if you get this mail more than once _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Template Haskell: Generate annotated function of a typeclass
by Ismael Figueroa Palet 10 May '12

10 May '12

Hi all, I think this is the right place for the following questions and I thank beforehand for your answers :-) I'm experimenting with typeclasses and TH, and I want to define a 'macro' that works more or less like this: Given the name of a typeclass and a function, return the expressions corresponding to the type-annotated instances, for instance $(foo Show show) should translate to: ["(show :: Int -> String)", "(show :: Bool -> String)", ....] for all instances currently in scope. I'm currently playing with the isInstance function (I'm running GHC 7.4.1) and can get a list of instances, and check if a given type is part of a typeclass or not. But I don't know how to create the expression corresponding to "instantiated function", as above. Thanks! -- Ismael

2 3

anyone else driven mad by trying to setup a gmp free version of haskell platform?
by Anatoly Yakovenko 10 May '12

10 May '12

i would really like to be able to ship haskell based linux binaries, but the gmp dependency makes it virtually impossible. so what version of host os, host ghc, and haskell-platform sources are known to build a working compiler? any reason why the dependency on gmp is static? are the interfaces between versions actually different? or can we build a version fo the compiler that loads the library via dlopen on demand? Thanks, Anatoly

3 2

Re: [Haskell-cafe] [Q] multiparam class undecidable types
by oleg＠okmij.org 10 May '12

10 May '12

> | instance (Table a c, Show c) => Show a where > I would have thought that there is on overlap: the instance in my code > above defines how to show a table if the cell is showable; No, the instance defines how to show values of any type; that type must be an instance of Table. There is no `if' here: instances are selected regardless of the context such as (Table a c, Show c) above. The constraints in the context apply after the selection, not during. Please see ``Choosing a type-class instance based on the context'' http://okmij.org/ftp/Haskell/TypeClass.html#class-based-overloading for the explanation and the solution to essentially the same problem. There are other problems with the instance: | instance (Table a c, Show c) => Show a where For example, there is no information for the type checker to determine the type c. Presumably there could be instances Table [[Int]] Int Table [[Int]] Bool So, when the a in (Table a c) is instantiated to [[Int]] there could be two possibilities for c: Int and Bool. You can argue that the type of the table uniquely determines the type of its cells. You should tell the type checker of that, using functional dependencies or associated types: class Table table where type Cell table :: * toLists :: table -> [[Cell table]]

2 2

Re: [Haskell-cafe] Datapacker?
by sharon kimble 10 May '12

10 May '12

On Thursday 10 May 2012 04:09:33 sharon kimble wrote: > On Thursday 10 May 2012 04:01:56 you wrote: > > What is datapacker? Can you summarize the sort of problem you are having? > > https://github.com/jgoerzen/datapacker/wiki ............ datapacker is a > tool to group files by size. It is perhaps most often used to fit a set of > files onto the minimum number of CDs or DVDs. > > I just want to check the syntax of the command before i commit it to stone > for backing up my mp3s? > > Thanks > Sharon. > > > On May 9, 2012 9:34 PM, "sharon kimble" <boudiccas(a)talktalk.net> wrote: > > > Is this the right place to ask questions about datapacker please? If > > > not, can > > > anyone tell me where is please? > > > > > > Thanks > > > Sharon. > > > -- -- A taste of linux = http://www.sharons.org.uk/taste/index.html efever = http://www.efever.blogspot.com/ efever = http://sharon04.livejournal.com/ Debian 6,0.4, Gnome 1:2.30+7, LibreOffice 3.4.6 Registered Linux user 334501

1 0

Re: [Haskell-cafe] Datapacker?
by Antoine Latter 10 May '12

10 May '12

On Wed, May 9, 2012 at 10:09 PM, sharon kimble <boudiccas(a)talktalk.net> wrote: > On Thursday 10 May 2012 04:01:56 you wrote: >> What is datapacker? Can you summarize the sort of problem you are having? > > https://github.com/jgoerzen/datapacker/wiki ............ datapacker is a tool > to group files by size. It is perhaps most often used to fit a set of files onto > the minimum number of CDs or DVDs. > > I just want to check the syntax of the command before i commit it to stone for > backing up my mp3s? > You should probably ask the author - that link is a part of the author's personal github page. Here is some contact information: http://www.complete.org/JohnGoerzen Antoine > Thanks > Sharon. >> >> On May 9, 2012 9:34 PM, "sharon kimble" <boudiccas(a)talktalk.net> wrote: >> > Is this the right place to ask questions about datapacker please? If not, >> > can >> > anyone tell me where is please? >> > >> > Thanks >> > Sharon. >> > -- > > -- > A taste of linux = http://www.sharons.org.uk/taste/index.html > efever = http://www.efever.blogspot.com/ > efever = http://sharon04.livejournal.com/ > Debian 6,0.4, Gnome 1:2.30+7, LibreOffice 3.4.6 > Registered Linux user 334501

1 0

Datapacker?
by sharon kimble 10 May '12

10 May '12

Is this the right place to ask questions about datapacker please? If not, can anyone tell me where is please? Thanks Sharon. -- A taste of linux = http://www.sharons.org.uk/taste/index.html efever = http://www.efever.blogspot.com/ efever = http://sharon04.livejournal.com/ Debian 6,0.4, Gnome 1:2.30+7, LibreOffice 3.4.6 Registered Linux user 334501

2 1

Haskell Weekly News: Issue 226
by Daniel Santa Cruz 10 May '12

10 May '12

Welcome to issue 226 of the HWN, an issue covering crowd-sourced bits of information about Haskell from around the web. This issue covers the week of April 29 to May 5, 2012. Quotes of the Week * acowley: I write the most complicated bottoms * Cale: OpenGL is the Rubik's Cube of graphics libraries. It's nearly impossible to change some things without affecting other things Top Reddit Stories * HJ — Haskell-to-JavaScript compiler (WIP) Domain: chrisdone.com, Score: 74, Comments: 23 On Reddit: [1] http://goo.gl/gP51N Original: [2] http://goo.gl/g32rz * Life Without Objects Domain: skipoleschris.blogspot.co.uk, Score: 52, Comments: 17 On Reddit: [3] http://goo.gl/LZmLC Original: [4] http://goo.gl/NLhKH * New major release of the containers package Domain: blog.johantibell.com, Score: 52, Comments: 25 On Reddit: [5] http://goo.gl/yjblJ Original: [6] http://goo.gl/DKlmd * Haskell and the World: Encodings and the Common Misuse of ByteString Domain: a-dimit.blogspot.com, Score: 50, Comments: 27 On Reddit: [7] http://goo.gl/WloCn Original: [8] http://goo.gl/oeIIW * How to write hybrid CPU/GPU programs with Haskell Domain: parfunk.blogspot.com.au, Score: 48, Comments: 3 On Reddit: [9] http://goo.gl/u9A9l Original: [10] http://goo.gl/s917R * phantom tainting with kind error messages Domain: article.gmane.org, Score: 35, Comments: 5 On Reddit: [11] http://goo.gl/V9qRd Original: [12] http://goo.gl/cx4cD * Annotated slides: Comparing Dynamic and Static Language Approaches to Web Frameworks (Rails vs Yesod) Domain: cs.kent.ac.uk, Score: 32, Comments: 11 On Reddit: [13] http://goo.gl/jE2iK Original: [14] http://goo.gl/2dIjQ * SPJ talk: Towards Haskell in the Cloud Domain: skillsmatter.com, Score: 30, Comments: 16 On Reddit: [15] http://goo.gl/fVc0e Original: [16] http://goo.gl/NMtPD * hotswap -- a simple, high level interface to plugins for hotswapping code Domain: hackage.haskell.org, Score: 29, Comments: 8 On Reddit: [17] http://goo.gl/kvhOS Original: [18] http://goo.gl/VMAe0 * Online Haskell typechecker Domain: haskellonline.org, Score: 29, Comments: 12 On Reddit: [19] http://goo.gl/uV3HY Original: [20] http://goo.gl/lSwhb Top StackOverflow Questions * Algebraically interpreting polymorphism votes: 21, answers: 5 Read on SO: [21] http://goo.gl/7krnc * Absolute value of negative zero - bug, or a part of the floating point standard? votes: 16, answers: 3 Read on SO: [22] http://goo.gl/HDpRc * how to implement doubly linked lists votes: 10, answers: 1 Read on SO: [23] http://goo.gl/hXyDM * GHC type inference for higher rank types - assigning to monotypes votes: 10, answers: 1 Read on SO: [24] http://goo.gl/TqYtX * Communication between Java and Haskell votes: 9, answers: 3 Read on SO: [25] http://goo.gl/zMYwx * Default constraint kinds are ignored votes: 9, answers: 2 Read on SO: [26] http://goo.gl/AElL4 * Scrap Your Boilerplate equivalent in Scala? votes: 7, answers: 1 Read on SO: [27] http://goo.gl/Cd7k4 * Does the chain function in underscore.js create a monad? votes: 7, answers: 1 Read on SO: [28] http://goo.gl/DUYkB * Why do Haskell list comprehensions with multiple generators treat the rightmost generator as the tightest loop? votes: 6, answers: 3 Read on SO: [29] http://goo.gl/BnndW * Haskell records, cleaner approach? votes: 6, answers: 1 Read on SO: [30] http://goo.gl/MymyL Until next time, Daniel Santa Cruz References 1. http://chrisdone.com/hj/ 2. http://www.reddit.com/r/haskell/comments/t06ej/hj_haskelltojavascript_compi… 3. http://skipoleschris.blogspot.co.uk/2012/04/life-without-objects.html 4. http://www.reddit.com/r/haskell/comments/t1oen/life_without_objects/ 5. http://blog.johantibell.com/2012/05/new-major-release-of-containers-package… 6. http://www.reddit.com/r/haskell/comments/t688l/new_major_release_of_the_con… 7. http://a-dimit.blogspot.com/2012/04/strings-in-haskell.html 8. http://www.reddit.com/r/haskell/comments/syo8h/haskell_and_the_world_encodi… 9. http://parfunk.blogspot.com.au/2012/05/how-to-write-hybrid-cpugpu-programs.… 10. http://www.reddit.com/r/haskell/comments/t7znh/how_to_write_hybrid_cpugpu_p… 11. http://article.gmane.org/gmane.comp.lang.haskell.cafe/98103 12. http://www.reddit.com/r/haskell/comments/t6dn7/phantom_tainting_with_kind_e… 13. http://www.cs.kent.ac.uk/~nccb/rails-yesod-slides.pdf 14. http://www.reddit.com/r/haskell/comments/t1aw8/annotated_slides_comparing_d… 15. http://skillsmatter.com/podcast/home/haskell-cloud/js-4179 16. http://www.reddit.com/r/haskell/comments/t0qg0/spj_talk_towards_haskell_in_… 17. http://hackage.haskell.org/package/hotswap-0.1.9.3 18. http://www.reddit.com/r/haskell/comments/t24lr/hotswap_a_simple_high_level_… 19. http://haskellonline.org/ 20. http://www.reddit.com/r/haskell/comments/t41bk/online_haskell_typechecker/ 21. http://stackoverflow.com/questions/10453558/algebraically-interpreting-poly… 22. http://stackoverflow.com/questions/10395761/absolute-value-of-negative-zero… 23. http://stackoverflow.com/questions/10386616/how-to-implement-doubly-linked-… 24. http://stackoverflow.com/questions/10424375/ghc-type-inference-for-higher-r… 25. http://stackoverflow.com/questions/10370177/communication-between-java-and-… 26. http://stackoverflow.com/questions/10381278/default-constraint-kinds-are-ig… 27. http://stackoverflow.com/questions/10423329/scrap-your-boilerplate-equivale… 28. http://stackoverflow.com/questions/10431999/does-the-chain-function-in-unde… 29. http://stackoverflow.com/questions/10399577/why-do-haskell-list-comprehensi… 30. http://stackoverflow.com/questions/10427217/haskell-records-cleaner-approach

1 0