March 2009 - Haskell-Cafe

Stacking State on State.....
by Phil 04 Mar '09

04 Mar '09

Hi, I¹ve been teaching myself Monads recently with some success, but I¹ve hit a snag when I tried to look at transformers. I¹m not sure if the problem is my understanding of transformer use at a theoretical level or if I¹m just getting the syntax wrong. If I stick a (hopefully) fairly simple example below, I was wondering if people could comment: Bit of background I have no problem using the State Monad and find it very useful for holding the state or say a homemade random number generator. I written several little bits of code like this: VanDerCorput :: Int-> ( Double, Int ) VanDerCorput state = ( output, state+1 ) where output = reflect state getVanDC :: State Int Double getVanFC = State VanDerCorput This is just holding an incremental state and each time it is evaluated the next number in the Van Der Corput sequence in generated this is just a quasi random sequence the implementation details of the sequence are irrelevant safe to say that the sequence is generated from N=1,2,3,4.....Infinity. The above example is so trivial it can of course be implemented easily in purely functional code by threading the state as a parameter to a pure function and then mapping that function to an ³iterate (+1) 1² statement, but that is not the point of the exercise! The next step of the program is to wrap the above example up in another function which takes the Van Der Corput sequence as input and provides output depending on*it¹s own* state. I¹m passing it to a Box-Muller transform. Very quickly the Box-Muller transform requires TWO inputs from VanDerCourput to produce TWO outputs itself, however we only ever need one at a time, so the Box-Muller transform itself must hold state saying weather it has already saved the 2nd output from a previous call, and thus doesn¹t need to call Van Der Corput this time to produce output it just returns its own state. (P.S. If you know what I¹m doing from a maths point of view please ignore the fact using a 1D Van Der Corput with Box Muller is a very bad idea I know this; I¹m keeping the example simple and Haskell orientated!) In C-like imperative code you¹d could do something like the below not that this is massively elegant, but it shows the case-in-point: Boxmuller() { // The ³outer² states of Box Muller static bool myState = False; static double storedNormal = 0.; // Local copy of current state bool currentState = myState; // State always flips each run myState = not myState; // If we don¹t have a stored value from a previous run if currentState == False { // Generate two new Van Der Corputs this would increment a state in getNextVanDerCorput() twice producing different output each time double rand1 = getNextVanDerCorput(); double rand2 = getNextVanDerCorput(); // Store one result for the NEXT run of Boxmuller() storedNormal = SOME_TRANSFORM(rand2); // Return the other return SOME_TRANSFORM(rand1); } // We have a leftover value from a previous run get a local copy double currentNormal = storedNormal; // Reset the stored value to zero storedNormal = 0.; // Return the local copy of the stored value return currentNormal; } getNextVanDerCorput() { // Starting state state int n = 1; int currentState = n; // Incremented each time we call the function ++n; // Value computed on the internal state of this function return SOME_OTHER_TRANSFORM(currentState); } Right, hopefully that explains explicitly what I¹m trying to do apologies for dropping into C, it¹s easier to explain in code than in words. It struck me that this could be done using a plain and simple State Monad in Haskell carrying ALL states for both functions around in a tuple. This is pretty ugly tho, and I figure both BoxMuller and VanDerCorput should have their own internal states so they can be used as building blocks in other functionality too so one big ugly Monad is bad code design, even if it would work for this specific example. Let¹s not go there. The VanDerCorput building block is just the Monad at the start of this post. The problem is HOW DO I WRAP ANOTHER INDEPENDENT STATE AROUND THIS? After some googling it looked like the answer may be Monad Transformers. Specifically we could add a StateT transform for our Box Muller state to our VanDerCorput State Monad. Google didn¹t yield a direct answer here so I¹m not even sure if my thinking is correct, people describe the process of using a transform as wrapping one monad in another¹ or threading one monad into another¹. What we want to do is have some internal state controlled by an independent outer state - this sounds about right to me? So I started playing around with the code, and got the below to compile. test :: StateT (Bool,Double) (State Int) Double test = do (isStored,normal) <- get let (retNorm,storeNorm) = if isStored then (normal,0) else (n1,n2) where n1 = 2 n2 = 3 put (not isStored, storeNorm) return retNorm Now this is incomplete and may be even wrong! I¹ll Explain my thinking: (Bool,Double) is equivalent to myState and storedNormal in the C example The last Double is the return value of the BoxMuller Monad The (State Int) is supposed to represent the VanDerCorput monad but the compiler (GHC 6.10) will only let me specify one parameter with it so I¹ve put the state and left the return type to the gods!!.... As I said this isn¹t quite right any ideas how to specify the type? The next few lines get and test the BoxMuller state, this seems to work OK to me, the problem is when I try to look at the STATE OF THE INTERNAL monad. n1 and n2 should evaluate and increment the state of VanDerCorput monad but I can¹t get anything to compile here. 2 and 3 are just dummy values to make the thing compile so I could debug. My last gripe is how to actually call this from a pure function do I need to use both evalStateT and evalState I can¹t see how to initialize both the inner and outer state ? OK I think that¹s more than enough typing, apologies for the war&peace sized post. Any help muchly muchly appreciated, Many Thanks, Phil.

4 17

OpenVG: Linker errors with ghc --make, but not with ghci?
by Peter Verswyvelen 04 Mar '09

04 Mar '09

I followed the instructions on how to build OpenVG on Windows. It works fine when I run the examples using "GHCi -lopenvg32", but when compiling it with "GHC --make -lopenvg32" I get a bunch of linker errors, like C:\Program Files\Haskell\OpenVG-0.1\ghc-6.10.1/libHSOpenVG-0.1.a(Paths.o):fake:(.text+0x82): undefined reference to `vgInterpolatePath' C:\Program Files\Haskell\OpenVG-0.1\ghc-6.10.1/libHSOpenVG-0.1.a(Paths.o):fake:(.text+0x40d): undefined reference to `vgModifyPathCoords' etc However it does seem that the libopenvg32.a file contains all these undefined references, and it is in the gcc-lib directory of GHC. I'm a stuck. Any hints? Thanks, Peter

2 2

Data.Binary stack overflow with Data.Sequence String
by Gwern Branwen 04 Mar '09

04 Mar '09

So recently I've been having issues with Data.Binary & Data.Sequence; I serialize a 'Seq String' You can see the file here: http://code.haskell.org/yi/Yi/IReader.hs The relevant function seems to be: -- | Read in database from 'dbLocation' and then parse it into an 'ArticleDB'. readDB :: YiM ArticleDB readDB = io $ (dbLocation >>= r) `catch` (\_ -> return empty) where r x = fmap (decode . BL.fromChunks . return) $ B.readFile x -- We read in with strict bytestrings to guarantee the file is closed, -- and then we convert it to the lazy bytestring data.binary expects. -- This is inefficient, but alas... My current serialized file is about 9.4M. I originally thought that the issue might be the recent upgrade in Yi to binary 0.5, but I unpulled patches back to past that, and the problem still manifested. Whenever yi tries to read the articles.db file, it stack overflows. It actually stack-overflowed on even smaller files, but I managed to bump the size upwards, it seems, by the strict-Bytestring trick. Unfortunately, my personal file has since passed whatever that limit was. I've read carefully the previous threads on Data.Binary and Data.Map stack-overflows, but none of them seem to help; hacking some $!s or seqs into readDB seems to make no difference, and Seq is supposed to be a strict datastructure already! Doing things in GHCi has been tedious, and hasn't enlightened me much: sometimes things overflow and sometimes they don't. It's all very frustrating and I'm seriously considering going back to using the original read/show code unless anyone knows how to fix this - that approach may be many times slower, but I know it will work. -- gwern

2 1

Status of Haskell under OsX
by Cristiano Paris 03 Mar '09

03 Mar '09

Hi, I'm planning to purchase a MacBookPro so I'm wondering how well Haskell is supported under this platform. Thanks, Cristiano

10 16

Memory usage when passing arrays in state
by Tobias Olausson 03 Mar '09

03 Mar '09

Hello all. I am currently implementing an emulation of a CPU, in which the CPU's RAM is part of the internal state that is passed around in the program using a state monad. However, the program performs unexpectingly bad, and some profiling information makes us believe that the problem is the high memory usage of the program. The program below is similar to our main program used when testing a sorting algorithm in this CPU: module Main where import Control.Monad.State.Lazy import Data.Word import Data.Array.Diff import Control.Concurrent (threadDelay) data LoopState = LoopState { intVal :: Integer , diff :: DiffUArray Word8 Word8 } initState :: LoopState initState = LoopState 0 (array (0x00,0xFF) [(idx,0)|idx<-[0x00..0xFF]]) main :: IO () main = do execStateT looper initState >>= putStrLn . show . intVal looper :: StateT LoopState IO () looper = do st <- get let res = intVal st + 1 idx = fromIntegral res put $ st { intVal = res, diff = (diff st) // [(idx,idx)] } if res == 13000000 then return () else looper Of course our program does more than updating a counter ;-) Compiling and running this program yields the following result: [~]:[olaussot] >> ghc --make -O2 -o array ArrayPlay.hs [~]:[olaussot] >> ./array +RTS -sstderr ./array +RTS -sstderr 13000000 313,219,740 bytes allocated in the heap 1,009,986,984 bytes copied during GC 200,014,828 bytes maximum residency (8 sample(s)) 4,946,648 bytes maximum slop 393 MB total memory in use (3 MB lost due to fragmentation) Generation 0: 590 collections, 0 parallel, 3.06s, 3.09s elapsed Generation 1: 8 collections, 0 parallel, 3.56s, 4.21s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.27s ( 0.27s elapsed) GC time 6.62s ( 7.30s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 6.89s ( 7.57s elapsed) %GC time 96.1% (96.4% elapsed) Alloc rate 1,155,958,754 bytes per MUT second Productivity 3.9% of total user, 3.6% of total elapsed Why does the program spend 96.1% of its total running time collecting garbage? Any tips to make this program perform better are appreciated. Please do tell if anything is unclear. -- Tobias Olausson tobsan(a)gmail.com

4 5

How to build sourceview depend for gtk2hs?
by Andy Stewart 03 Mar '09

03 Mar '09

Hi all, I use Debian testing. I have install GHC 6.10.1 binary package. When i use "autoreconf && ./configure --enable-docs" to config gtk2hs ************************************************** * Configuration completed successfully. * * The following packages will be built: * * glib : yes * gtk : yes * gio : yes * glade : yes * cairo : yes * svgcairo : yes * gtkglext : yes * gconf : yes * sourceview : no * gtksourceview2 : yes * mozembed : yes * soegtk : yes * gnomevfs : yes * gstreamer : yes * documentation : yes * * Now do "(g)make" followed by "(g)make install" ************************************************** But "sourceview" is not pass, have anyone successful? I have install below packages: libglade2-dev libgtksourceview-dev libgconf2-dev librsvg2-dev libgstreamer-plugins-base0.10-dev libgstreamer0.10-dev libgtkglext1-dev libgnomevfs2-dev xulrunner-dev So i need install which depend package to fix above problem? Thanks! Below is the detail config information. checking for a BSD-compatible install... /usr/bin/install -c checking whether build environment is sane... yes checking for a thread-safe mkdir -p... /bin/mkdir -p checking for gawk... no checking for mawk... mawk checking whether make sets $(MAKE)... yes checking build system type... i686-pc-linux-gnu checking host system type... i686-pc-linux-gnu checking for style of include used by make... GNU checking for gcc... gcc checking for C compiler default output file name... a.out checking whether the C compiler works... yes checking whether we are cross compiling... no checking for suffix of executables... checking for suffix of object files... o checking whether we are using the GNU C compiler... yes checking whether gcc accepts -g... yes checking for gcc option to accept ISO C89... none needed checking dependency style of gcc... none checking how to run the C preprocessor... gcc -E checking for a BSD-compatible install... /usr/bin/install -c checking whether ln -s works... yes checking for ar... /usr/bin/ar checking for ld... /usr/bin/ld checking for basename... /usr/bin/basename checking for grep that handles long lines and -e... /bin/grep checking for gzip... /bin/gzip checking for a sed that does not truncate output... /bin/sed checking for cut... /usr/bin/cut checking for tar... /bin/tar checking for touch... /usr/bin/touch checking for ranlib... ranlib checking for xargs... /usr/bin/xargs checking for ghc... /usr/local/bin/ghc checking version of GHC... 6.10.1 checking for ghc-pkg... /usr/local/bin/ghc-pkg checking whether to build deprecated bindings... yes checking whether to build deprecated packages (gnomevfs, sourceview)... yes checking for the GHC package "base"... yes, version 4.0.0.0 checking for the GHC package "haskell98"... yes, version 1.0.1.0 checking for the GHC package "mtl"... yes, version 1.1.0.2 checking for the GHC package "bytestring"... yes, version 0.9.1.4 checking for the GHC package "containers"... yes, version 0.2.0.0 checking for the GHC package "array"... yes, version 0.2.0.0 checking for the GHC package "old-time"... yes, version 1.0.0.1 checking for the GHC package "pretty"... yes, version 1.0.1.0 checking for pkg-config... /usr/bin/pkg-config checking pkg-config is at least version 0.9.0... yes checking for GLIB... yes checking for GTK... yes checking whether to build gtk package... yes checking for GIO... yes checking whether to build gio package... yes checking for LIBGLADE... yes checking whether to build glade package... yes checking for GCONF... yes checking whether to build gconf package... yes checking for GTKSOURCEVIEW2... yes checking whether to build gtksourceview2 package... yes checking whether to build sourceview package... no checking for MOZILLA_MOZEMBED... yes checking whether to build mozembed package... yes checking for SEAMONKEY_MOZEMBED... no checking whether to build mozembed package... no checking for FIREFOX_MOZEMBED... no checking whether to build mozembed package... no checking for XULRUNNER_MOZEMBED... no checking whether to build mozembed package... no checking for CAIRO... yes checking whether to build cairo package... yes checking for SVGCAIRO... yes checking whether to build svgcairo package... yes checking for GTKGLEXT... yes checking whether to build gtkglext package... yes checking for GNOMEVFS... yes checking whether to build gnomevfs package... yes checking for GSTREAMER... yes checking whether to build gstreamer package... yes checking for hsc2hs... /usr/local/bin/hsc2hs checking for happy... /usr/local/bin/happy checking version of happy... 1.18.2 checking for alex... /usr/local/bin/alex checking for haddock... /usr/local/bin/haddock checking version of haddock... 2.4.1 configure: creating ./config.status config.status: creating Makefile config.status: creating gtk2hs.spec config.status: creating mk/chsDepend config.status: creating mk/link-splitobjs.sh config.status: creating mk/fix-package-conf.sh config.status: creating docs/prologue.txt config.status: creating glib/glib.package.conf config.status: creating glib/glib.cabal config.status: creating gtk/gtk.package.conf config.status: creating gtk/gtk.cabal config.status: creating gio/gio.package.conf config.status: creating gio/gio.cabal config.status: creating glade/glade.package.conf config.status: creating glade/glade.cabal config.status: creating gconf/gconf.package.conf config.status: creating gconf/gconf.cabal config.status: creating sourceview/sourceview.package.conf config.status: creating sourceview/sourceview.cabal config.status: creating gtksourceview2/gtksourceview2.package.conf config.status: creating gtksourceview2/gtksourceview2.cabal config.status: creating mozembed/mozembed.package.conf config.status: creating mozembed/mozembed.cabal config.status: creating cairo/cairo.package.conf config.status: creating cairo/cairo.cabal config.status: creating svgcairo/svgcairo.package.conf config.status: creating svgcairo/svgcairo.cabal config.status: creating gtkglext/gtkglext.package.conf config.status: creating gtkglext/gtkglext.cabal config.status: creating soegtk/soegtk.package.conf config.status: creating soegtk/soegtk.cabal config.status: creating gnomevfs/gnomevfs.package.conf config.status: creating gnomevfs/gnomevfs.cabal config.status: creating gstreamer/gstreamer.package.conf config.status: creating gstreamer/gstreamer.cabal config.status: creating gtk2hs-config.h config.status: gtk2hs-config.h is unchanged config.status: executing depfiles commands config.status: executing default commands ************************************************** * Configuration completed successfully. * * The following packages will be built: * * glib : yes * gtk : yes * gio : yes * glade : yes * cairo : yes * svgcairo : yes * gtkglext : yes * gconf : yes * sourceview : no * gtksourceview2 : yes * mozembed : yes * soegtk : yes * gnomevfs : yes * gstreamer : yes * documentation : yes * * Now do "(g)make" followed by "(g)make install" ************************************************** -- Andy

2 3

Relying on GCC as the hsc2hs C compiler
by John Van Enk 03 Mar '09

03 Mar '09

While working on my new bindings project (using hsc2hs) I came across the __alignof__() statement available in GNU's C compiler. As it turns out, having this computed for me in Storable instances using something like this would be great: instance Storable Foo where .... sizeOf _ = #{const sizeof(CFoo)} alignment _ = #{const __alignof__(CFoo)} .... Can I rely on hsc2hs using GCC? How many people will hate me if I depend on GCC-specific extensions? Legal? Acceptable? Infuriating? /jve

1 0

Threading and Mullticore Computation
by mwinter＠brocku.ca 03 Mar '09

03 Mar '09

Hi, I tried a get into concurrent Haskell using multiple cores. The program below creates 2 task in different threads, executes them, synchronizes the threads using MVar () and calculates the time needed. import System.CPUTime import Control.Concurrent import Control.Concurrent.MVar myTask1 = do return $! fac 60000 print "Task1 done!" where fac 0 = 1 fac n = n * fac (n-1) myTask2 = do return $! fac' 60000 1 1 print "Task2 done!" where fac' n m p = if m>n then p else fac' n (m+1) (m*p) main = do mvar <- newEmptyMVar pico1 <- getCPUTime forkIO (myTask1 >> putMVar mvar ()) myTask2 takeMVar mvar pico2 <- getCPUTime print (pico2 - pico1) I compiled the code using $ ghc FirstFork.hs -threaded and executed it by $ main +RTS -N1 resp. $ main +RTS -N2 I use GHC 6.8.3 on Vista with an Intel Dual Core processor. Instead of getting a speed up when using 2 cores I get as significant slow down, even though there is no sharing in my code above (at least none I am aware of. BTW, that was reason that I use 2 different local factorial functions). On my computer the 1-core version takes about 8.3sec and the 2-core version 12.8sec. When I increase the numbers from 60000 to 100000 the time difference gets even worse (30sec vs 51 sec). Can anybody give me an idea what I am doing wrong? Thanks, Michael

8 20

interaction between ghci and cudaBLAS library
by Simon Beaumont 03 Mar '09

03 Mar '09

In my efforts to integrate this library into Haskell (I am working on OS X 10.5.6 with ghc-6.10.1 and CUDA 2.0) I am getting a bad interaction between the threads in ghci - when I call the library init function via the FFI, ghci will block in __semwait_signal. Of course if I build an executable which I guess has only one thread then all is well. AFAIK the CUDA library is re-entrant (or threadsafe) in that it will initialize a device context for each thread that calls it. I guess that might be part of the problem. Certainly there is a call to _pthread_getspecific in that library. This is show stopper for me as I want to use GHCI to call blas routines on the device (this lends itself very nicely to a monadic approach - leaving the matrices on the device until we are done applying sequential computations - and only then bringing them back into the "real" world). Since there is this association between the device context and the calling thread - is there a way to get a handle on the threading in ghci? (or just have a single thread) But why are we blocking? I would have expected completion or is ghci smart enough to prevent any non-deterministic behaviour that the current setup would entail? Any ideas or suggestions of how to proceed with this? The final work should it be successful will be offered to the community as a basis for doing high performance linear algebra on CUDA devices as well as get my haskell up to speed as a side effect :) -- View this message in context: http://www.nabble.com/interaction-between-ghci-and-cudaBLAS-library-tp22300… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 6

ANNOUNCE: Extensible and Modular Generics for the Masses: emgm-0.3
by Sean Leather 03 Mar '09

03 Mar '09

============================================== Extensible and Modular Generics for the Masses ============================================== Extensible and Modular Generics for the Masses (EMGM) is a library for generic programming in Haskell using type classes and a sum-of-products view. ------- Updates ------- emgm-0.3 is the third major release, and it arrives a little over a month after emgm-0.2. Deriving is now greatly improved! Due to recent reports from users, we realized the current implementation just wasn't going to cut it. EMGM already supports a wide range of datatypes, so why not make the deriving code support just as many. Hopefully, it works well for you. Please let us know if your datatype is not supported. There are several new functions in the EMGM family. These include: cast (a type-safe, configurable, generic cast) and everywhere and everywhere' (functions similar to those of the same name in SYB that apply a transformation everywhere a certain type is found). ------- Changes ------- Changes from emgm-0.2 include: * Improved deriving can now handle datatype collections like this one: http://www.haskell.org/pipermail/generics/2009-February/000429.html * cast function > cast :: Rep (Map a) b => a -> b * everywhere and everywhere' > everywhere :: Rep (Everywhere a) b => (a -> a) -> b -> b > everywhere' :: Rep (Everywhere' a) b => (a -> a) -> b -> b They both perform transformations on a-values in a b-value. The former does them bottom-up, the latter top-down. The names come from similar functions in SYB that use rank-2 types. Note the difference. > everywhere :: (forall a. Data a => a -> a) -> forall a. Data a => a -> a > everywhere' :: (forall a. Data a => a -> a) -> forall a. Data a => a -> a ------------ Known Issues ------------ Due to a problem with the template-haskell package and Cabal, you cannot cabal-install the emgm package with GHC 6.8. However, take heart! EMGM works very well with GHC 6.8. You merely have to download the tar.gz package from Hackage yourself, build it, and install it. Since it doesn't require any dependencies beyond what comes with GHC, installation is a breeze! ------------------- General Information ------------------- Visit the home page: http://www.cs.uu.nl/wiki/GenericProgramming/EMGM ---------------- General Features ---------------- The primary features of EMGM include: * Datatype-generic programming using sum-of-product views * Large collection of ready-to-use generic functions * Included support for standard datatypes: lists, Maybe, tuples * Easy to add support for new datatypes * Type classes make writing new functions straightforward in a structurally inductive style * Generic functions are extensible with ad-hoc cases for arbitrary datatypes * Good performance of generic functions The features of this distribution include: * The API is thoroughly documented with Haddock * Fully tested with QuickCheck and HUnit * Program coverage ensures that all useful code has been touched by tests * Tested on both Mac and Windows systems ------------ Requirements ------------ EMGM has the following requirements: * GHC 6.8.1 - It has been tested with versions 6.8.3 and 6.10.1 * Cabal library 1.2.1 - It has been tested with versions 1.2.4.0 and 1.6.0.1. ----------------- Download & Source ----------------- Use caball-install: cabal install emgm Get the package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/emgm Check out the current source with Subversion: svn checkout https://svn.cs.uu.nl:12443/repos/dgp-haskell/EMGM/trunk Or view it online: https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/trunk/ -------- Examples -------- Check out the examples: https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/trunk/examples/ -------------- Bugs & Support -------------- Report issues or request features: http://code.google.com/p/emgm/issues/list Discuss EMGM with the authors, maintainers, and other interested persons: http://www.haskell.org/mailman/listinfo/generics ------- Credits ------- The research for EMGM originated with Ralf Hinze. It was extended with work by Bruno Oliveira and Andres Löh. More details of the library functionality were explored by Alexey Rodriguez. We are very grateful to all of these people for the foundation on which this library was built. The current authors and maintainers of EMGM are: * Sean Leather * José Pedro Magalhães * Alexey Rodriguez * Andres Löh

2 2