November 2009 - Haskell-Cafe

(possibly) a list comprehensions question
by Ozgur Akgun 19 Nov '09

19 Nov '09

Hi Cafe! I am struggling with an interesting problem while defining a function. It looks quite easy to me, but I couldn't manage to have a proper implementation yet. To illustrate what I'm trying to achive, I'll introduce special cases of the desired function, and hopefully build towards a solution step by step. -- simplest case, taking 2 lists as parameters and returning a list of list containing every possible pair (but represented as lists) allPossibilities2 :: [a] -> [a] -> [[a]] allPossibilities2 listX listY = [ [x,y] | x <- listX, y <- listY] -- sample output -- allPossibilities2 [1,2,3] [7,8,9] -- [[1,7],[1,8],[1,9],[2,7],[2,8],[2,9],[3,7],[3,8],[3,9]] -- simplest case with 3 parameters instead of 2 allPossibilities3 :: [a] -> [a] -> [a] -> [[a]] allPossibilities3 listX listY listZ = [ [x,y,z] | x <- listX, y <- listY, z <- listZ] -- allPossibilities3 [1,2] [3,4,5] [6,7] -- [[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]] These are easy and work just fine. All I want to do is to generalize this function receiving n lists as parameters and doing the simple action described above. Since I cannot pass variable number of parameters to a function, I'll use list of lists from now on. Following are the implementations of the same functions with different types (instead of two lists, a list of lists assumed to caontain those 2 elements) allPossibilities2' :: [[a]] -> [[a]] allPossibilities2' list = [ [x,y] | x <- list !! 0, y <- list !! 1] -- allPossibilities2' [[1,2,3],[7,8,9]] -- [[1,7],[1,8],[1,9],[2,7],[2,8],[2,9],[3,7],[3,8],[3,9]] allPossibilities3' :: [[a]] -> [[a]] allPossibilities3' list = [ [x,y,z] | x <- list !! 0, y <- list !! 1, z <- list !! 2] -- allPossibilities3' [[1,2],[3,4,5],[6,7]] -- [[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]] This is ugly! Anyway, just forget the fact that these funstions do not do a check on the length of the input list for a moment. My question is, how can I generalize this function to accept a list of lists of arbitrary length, and produce the required result. I hope I managed to make my point clear enough. Waiting for suggestions. Regards, -- Ozgur Akgun

4 5

How to show record syntax?
by Sean Leather 19 Nov '09

19 Nov '09

A while back, I was working on the Show function for EMGM [1] and verifying its output vs. that of GHC's when I discovered (I thought) a minor difference between what was necessary and what GHC did for record syntax. Labeled construction and update, according to the Report [2], have higher precedence than function application. This means that I can do the following > module Main where > data A = A {x :: Int} deriving Show > main = print $ Just A {x = 5} without putting parentheses around A {x = 5}. If I run this in GHCi, *Main> main Just (A {x = 5}) I see that the derived show in GHC adds parentheses around the record value. This led to an issue report [3] which developed a few responses. Some don't like the grammar as defined, because, at a glance, it appears too much like function application. Others noted that Hugs does not add the parentheses and wanted to see consistency between compilers. In the spirit of the GHC Bug Sweep [4] and finding resolution, I put the question to the wider community. How should we show record syntax? Should we try to ensure consistency between the compilers? Should we try to print as few parentheses as possible? Should we write a Haskell' proposal to "fix" the grammar and make Just A {x=5} illegal? What do you think? [1] http://hackage.haskell.org/packages/archive/emgm/0.3.1/doc/html/Generics-EM… [2] http://www.haskell.org/onlinereport/exps.html#sect3 [3] http://hackage.haskell.org/trac/ghc/ticket/2530 [4] http://hackage.haskell.org/trac/ghc/wiki/BugSweep Regards, Sean

3 2

Re: [Haskell-cafe] If you haven't bought any of Knuth's fascicles yet, this is definitely the one to get. Bitwise Tricks & Techniques
by Doug McIlroy 19 Nov '09

19 Nov '09

One of Knuth's sources is the well-named book "Hacker's Delight" by Henry S. Warren; see hackersdelight.org

1 0

Typefuck: Brainfuck in the type system
by Johnny Morrice 19 Nov '09

19 Nov '09

Greetings list, I was um well, drinking beer and thought it would be amusing to write a brainfuck interpreter which runs within the GHC type checker so I did, using type families. I haven't decided whether or not to put it on hackage (it is rather silly after all) but I have a link to a cabalized package and instructions on how to work it in an entry on my blog, here: http://killersmurf.blogspot.com/2009/11/typefuck.html Enjoy the ridiculousness. Johnny

5 6

Cabal + gfortran?
by Gregory Crosswhite 19 Nov '09

19 Nov '09

Hi, I want to set up a build that compiles fortran sources in addition to the Haskell, and which maybe also eventually checks for the existence of a library or two (specifically, LAPACK and BLAS). Does anyone here have a suggestion for where I should be looking to figure out how to do this, such as a package which uses such a setup that would provide an example? Thanks, Greg

2 1

pthread_kill missing?
by Gabor Greif 19 Nov '09

19 Nov '09

Hi all, I'd like to send a signal from the main thread to a forkOS-ed thread in GHC. The former should use raiseSignal and the second should sit in awaitSignal. I figured that the posix functionality in the unix-2.3 library does not cover this case. I would have expected that blocking/sending/receiving signals would utilize the pthread_* routines. This does not seem to be the case. Any idea when these will be available? Thanks in advance, cheers, Gabor PS: I guess some of you will say, "use condition variables". But that won't answer my question :-)

3 3

faster compiling for ghc
by Evan Laforge 19 Nov '09

19 Nov '09

Recently the "go" language was announced at golang.org. There's not a lot in there to make a haskeller envious, except one real big one: compilation speed. The go compiler is wonderfully speedy. Anyone have any tips for speeding up ghc? Not using -O2 helps a lot. I spend a lot of time linking (ghc api drags in huge amounts of ghc code) and I'm hoping the new dynamic linking stuff will speed that up. I suppose it should be possible to run the whole thing under the bytecode compiler, and this works fine for rerunning tests, I can just stay in ghci, make changes, :r and rerun, but it runs into trouble as soon as code wants to link in foreign C. I also recently discovered -fobject-code, which indeed starts compiling right away, cutting out the ghc startup overhead. However, it doesn't appear to help with the final link, so I wind up having to reinvoke ghc anyway. According to Rob Pike, the main reason for 6g's speed is that in a dependency tree where A depends on B depends on C, the interface for B will pull up all the info needed from C. So compiling A only needs to look at B. Would it help ghc at all if it did the same with hi files? I've heard that ghc does more cross module inlining than your typical imperative language, but with optimization off maybe we can ignore all that? I've seen various bits of noise about supporting parallel builds with --make and it seems to involve making the whole compiler re-entrant which is non-trivial. Would it be simpler to parallelize pure portions of the compilation, say with parallel strategies? Or just start one ghc per core and have a locking scheme so they don't step on each others files?

13 18

Re: [Haskell-cafe] Some help needed to start Haskell with Yi
by Robert Greayer 18 Nov '09

18 Nov '09

On Wed, Nov 18, 2009 at 8:15 PM, Daniel Fischer <daniel.is.fischer(a)web.de>wrote: > >> Am Donnerstag 19 November 2009 01:07:37 schrieb Henning Thielemann: >> > Kapil Hari Paranjape schrieb: >> > > Hello, >> > > >> > > On Sat, 14 Nov 2009, Jaco van Iterson wrote: >> > >> Only installation with 'cabal install yi' in a Cygwin shell under MS >> > >> Windows XP ended in: >> > >> Yi\Prelude.hs:182:9: >> > >> Duplicate instance declarations: >> > >> instance Category Accessor.T -- Defined at >> Yi\Prelude.hs:182:9-38 >> > >> instance Category Accessor.T >> > >> -- Defined in data-accessor-0.2.1:Data.Accessor.Private >> > >> cabal.exe: Error: some packages failed to install: >> > >> yi-0.6.1 failed during the building phase. The exception was: >> > >> exit: ExitFailure 1 >> > >> >> > >> Seems easy to fix but I can't even find where on my drive I can find >> the >> > >> source code. >> > >> >> > >> Where is the source? >> > >> > Seems to be that the author defined an orphan instance - something one >> > should never do! >> >> So what do you do if you need an instance ClassX TypeY but the author of >> the package that >> defines TypeY hasn't provided one? >> >> You can define an orphan instance or duplicate packageY but with the >> instance. Both are >> bad. Providing an orphan instance until packageY has one seems the lesser >> evil to me. >> Are there any good options? > > Whether it qualifies as 'good' or not, I'm not sure, but I think the standard recommendation is to newtype-wrap the type you want to make an orphan instance of, and make the instance on that (new) type. >

1 0

ANNOUNCE: parallel-2.0.0.0
by Simon Marlow 18 Nov '09

18 Nov '09

I've just uploaded parallel-2.0.0.0 to Hackage. If you're using Strategies at all, I'd advise updating to this version of the parallel package. It's not completely API compatible, but if you're just using the supplied Strategies such as parList, the changes should be relatively minor. The Haddock docs include a full description of the changes, reproduced below. Haddock docs are also here, until Hackage catches up: http://www.haskell.org/~simonmar/parallel/index.html The Strategy-using programs I've tried so far go faster. Enjoy! Cheers, Simon --------------------------------------------------------------------- Version 1.x The original Strategies design is described in <http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html> and the code was written by Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al. Version 2.x Later, during work on the shared-memory implementation of parallelism in GHC, we discovered that the original formulation of Strategies had some problems, in particular it lead to space leaks and difficulties expressing speculative parallelism. Details are in the paper \"Runtime Support for Multicore Haskell\" <http://www.haskell.org/~simonmar/papers/multicore-ghc.pdf>. This module has been rewritten in version 2. The main change is to the 'Strategy a' type synonym, which was previously @a -> Done@ and is now @a -> a@. This change helps to fix the space leak described in \"Runtime Support for Multicore Haskell\". The problem is that the runtime will currently retain the memory referenced by all sparks, until they are evaluated. Hence, we must arrange to evaluate all the sparks eventually, just in case they aren't evaluated in parallel, so that they don't cause a space leak. This is why we must return a \"new\" value after applying a 'Strategy', so that the application can evaluate each spark created by the 'Strategy'. The simple rule is this: you /must/ use the result of applying a 'Strategy' if the strategy creates parallel sparks, and you should probably discard the the original value. If you don't do this, currently it may result in a space leak. In the future (GHC 6.14), it will probably result in lost parallelism instead, as we plan to change GHC so that unreferenced sparks are discarded rather than retained (we can't make this change until most code is switched over to this new version of Strategies, because code using the old verison of Strategies would be broken by the change in policy). The other changes in version 2.x are: * Strategies can now be defined using a convenient Applicative type Eval. e.g. parList s = unEval $ traverse (Par . s) * 'parList' has been generalised to 'parTraverse', which works on any 'Traversable' type. * 'parList' and 'parBuffer' have versions specialised to 'rwhnf', and there are transformation rules that automatically translate e.g. @parList rwnhf@ into a call to the optimised version. * 'NFData' is deprecated; please use the @DeepSeq@ class in the @deepseq@ package instead. Note that since the 'Strategy' type changed, 'rnf' is no longer a 'Strategy': use 'rdeepseq' instead.

3 2

If you haven't bought any of Knuth's fascicles yet, this is definitely the one to get. Bitwise Tricks & Techniques
by Casey Hawthorne 18 Nov '09

18 Nov '09

If you haven't bought any of Knuth's fascicles yet, this is definitely the one to get. "The Art of Computer Programming: Volume 4 Bitwise Tricks & Techniques Binary Decision Diagrams" Fascicle 1 Donald E. Knuth 2009 Describes basic "broadword" operations and an important class of data structures that can make computer programs run dozens - even thousands - of times faster. I started a Haskell program using bitwise operations and then discarded them thinking them to low level. I think one of the dangers of Haskell, is that I get carried away with medium and high level abstractions and think "everything" MUST be done that way. :) -- Regards, Casey

2 2