- Haskell-Cafe - Haskell.org

Un-memoization
by Victor Miller 23 Mar '12

23 Mar '12

I was writing a Haskell program which builds a large labeled binary tree and then does some processing of it, which is fold-like. In the actual application that I have in mind the tree will be *huge*. If the whole tree is kept in memory it would probably take up 100's of gigabytes. Because of the pattern of processing the tree, it occurred to me that it might be better (cause much less paging) if some large subtrees could be replaced by thunks which can either recalculate the subtree as needed, or write out the subtree, get rid of the references to it (so it can be garbage collected) and then read back in (perhaps in pieces) as needed. This could be fairly cleanly expressed monadically. So does anyone know if someone has created something like this? Victor

4 3

Open-source projects for beginning Haskell students?
by Brent Yorgey 23 Mar '12

23 Mar '12

Hi everyone, I am currently teaching a half-credit introductory Haskell class for undergraduates. This is the second time I've taught it. The last time, for their final project I gave them the option of contributing to an open-source project; a couple groups took me up on it and I think it ended up being a modest success. So I'd like to do it again this time around, and am looking for particular projects I can suggest to them. Do you have an open-source project with a few well-specified tasks that a relative beginner (see below) could reasonably make a contribution towards in the space of about four weeks? I'm aware that most tasks don't fit that profile, but even complex projects usually have a few "simple-ish" tasks that haven't yet been done just because "no one has gotten around to it yet". If you have any such projects, I'd love to hear about it! Here are a few more details: * The students will be working on the projects from approximately the end of this month through the end of April. * By "relative beginner" I mean someone familiar with the material listed here: http://www.cis.upenn.edu/~cis194/lectures.html and just trying to come to terms with Applicative and Monad. They definitely do not know much if anything about optimization/profiling, GADTs, the mtl, or Haskell-programming-in-the-large. (Although part of the point of the project is to teach them a bit about programming-in-the-(medium/large)). * What I would hope from you is a willingness to exchange email and/or chat with the student(s) over the course of the project, to give them a bit of guidance/mentoring. I am certainly willing to help on that front, but of course I probably don't know much about your particular project. thanks! -Brent

10 13

Parallelism causes space leaks
by Yavuz Yetim 23 Mar '12

23 Mar '12

Hi, For the code below, where it says "HERE" in comments, if I remove the part after `using` the code works fine. However, with this version it causes a Stack space overflow (if allowed uses GBs of memory). You just need to input a file with around 1M lines each having something like "Int Value: 3 @x". What is wrong with adding the parList to this code? (Same thing happens for parMap, and parListChunk, etc) Yavuz import System.IO import System.Environment import System.IO.Error import Control.Parallel import Control.Parallel.Strategies import Control.Monad import Data.Binary as DB import Data.Binary.Put import Data.Word import Data.Maybe import qualified Data.ByteString.Lazy as B import Text.Regex.TDFA import Text.Regex.Base.Context main = do { args <- getArgs; x <- getLines (head args); mapM_ writeMaybeIntBinary ((map perLineOperator x) `using` parList rdeepseq); -- HERE return (); } writeMaybeIntBinary :: Maybe Word32 -> IO () writeMaybeIntBinary Nothing = return (); writeMaybeIntBinary (Just intB) = do { B.hPut stdout (runPut (putWord32host intB));}; getLines :: FilePath -> IO [String] getLines = liftM lines . readFile perLineOperator :: String -> Maybe Word32 perLineOperator line = let { getIntStr :: String -> String; getIntStr "" = ""; getIntStr line = let { matches = (line =~ "Int Value: (-?[0-9]*) .*" :: [[String]]); } in if matches == [] then "" else (last (head matches)); } in let { intStr = (getIntStr line); } in if intStr == "" then Nothing else Just (read intStr :: Word32)

1 0

[ANNOUNCE] vector-conduit
by Jared Hance 23 Mar '12

23 Mar '12

I've released a small (one-module) library [1] inspired by functions in Data.Conduit.List like sourceList, consumeList, and take. The most recent (by a few days) depends on conduit-0.3.*, but vector-conduit-0.2.1.0 depends on conduit-0.2.*. Notably, however, the two have different APIs (0.3 has an API more consistent with other vector operations). Use of any versions below 0.2.1 is discouraged as consumeVector is notably less efficient since in those versions it relies on a dlist. This should be useful for replacing consumeList with consumeVector, since consumeVector is much more efficient for reading in a large amount of values with, at this point, very little code overhead for using a Vector rather than a list. The library uses Data.Vector.Generic so unboxed, boxed, immutable, and mutable vectors are all supported, along with conduits for converting between mutable and immutable. [1] http://hackage.haskell.org/package/vector-conduit-0.3.0.0

2 4

haskell-platform vs macports
by Warren Harris 22 Mar '12

22 Mar '12

I assume that many haskell users out there on macs who are also users of macports, and I bet they've hit this same issue that I've hit numerous times. The problem is that there are 2 incompatible versions of libiconv -- one that ships with the mac, and one that's built with macports and that many macports-compiled libraries depend on. Work-arounds have been documented in numerous places (notably here: http://blog.omega-prime.co.uk/?p=96) but if you are trying to link with a macports-compiled libraries that depends on /opt/local/lib/libiconv.2.dylib, your only alternative seems to be building ghc from source in order to avoid the incompatibility. I hit this problem while trying to build a foreign-function interface to libarchive. So I built ghc from scratch -- in fact I built the whole haskell-platform. This was relatively painless, and fixed the libiconv problem. However, it brings me to the real point of my message, which is that the version of haskell-platform available via macports is way out of date (2009.2.0.2 http://www.macports.org/ports.php?by=name&substr=haskell-platform) I'm wondering whether the haskell-platform team has considered maintaining a macports version of the haskell-platform for us mac users in addition to the binary install that's available now. This would avoid the incompatibilities such as this nagging one with libiconv. Perhaps it's just a matter of maintaining template versions of the port files? Warren Undefined symbols for architecture x86_64: "_locale_charset", referenced from: _localeEncoding in libHSbase-4.3.1.0.a(PrelIOUtils.o) "_iconv_close", referenced from: _hs_iconv_close in libHSbase-4.3.1.0.a(iconv.o) (maybe you meant: _hs_iconv_close) "_iconv", referenced from: _hs_iconv in libHSbase-4.3.1.0.a(iconv.o) (maybe you meant: _hs_iconv, _hs_iconv_open , _hs_iconv_close ) "_iconv_open", referenced from: _hs_iconv_open in libHSbase-4.3.1.0.a(iconv.o) (maybe you meant: _hs_iconv_open) ld: symbol(s) not found for architecture x86_64 collect2: ld returned 1 exit status cabal: Error: some packages failed to install: Libarchive-0.1 failed during the building phase. The exception was: ExitFailure 1

2 2

Puzzled about inlining and specialise inline under ghc -O2
by Rafal Kolanski 22 Mar '12

22 Mar '12

Dear Haskell-Cafe, I'm computing a histogram of a bunch of symbols with up to 8 bits of information each, stored in a unboxed vector of Word8. The histogram is represented as an unboxed vector of Int with size 2^bits. I compute the histogram by folding an increment function. The problem: depending on what types and what annotations I give to the increment and histogram function (see below), the GC gets through a different amount of memory. I'm using GHC 7.0.3 and -O2. I'd like to better understand how and why the optimisation does/doesn't kick in. Here are the functions with the most generic types I can think of: import qualified Data.Vector.Unboxed as UV import qualified Data.Vector.Unboxed.Mutable as UMV import Control.Monad.Primitive (PrimMonad, PrimState) increment :: (PrimMonad m, UMV.Unbox a, Num a, Integral b) => UMV.MVector (PrimState m) a -> b -> m (UMV.MVector (PrimState m) a) increment v x = do n <- UMV.read v (fromIntegral x) UMV.write v (fromIntegral x) (n+1) return v histogram :: (Integral a, UMV.Unbox a) => Int -> UV.Vector a -> UV.Vector Int histogram bitsPerSym v = runST $ do a <- UMV.replicate (2^bitsPerSym) (0::Int) a' <- UV.foldM' increment a v UV.unsafeFreeze a' Running my test load, I get: total alloc = 33,206,568 bytes Looking at the core, ghc is not specialising the functions, even if I tell it to inline them. So let's brutally change the types to be as specific as I need for my application: increment :: UMV.MVector s Int -> Word8 -> ST s (UMV.MVector s Int) histogram :: Int -> UV.Vector Word8 -> UV.Vector Int result: total alloc = 19,581,152 bytes and if I put INLINE pragmas for both functions: 16,952,512 bytes I should be able to achieve the same effect with SPECIALISE INLINE pragmas, right? Let's try that: {-# SPECIALISE INLINE increment :: UMV.MVector s Int -> Word8 -> ST s (UMV.MVector s Int) #-} {-# SPECIALISE INLINE histogram :: Int -> UV.Vector Word8 -> UV.Vector Int #-} result: 33,139,856 bytes (GHC can't figure out application of the first rule, giving: Warning: RULE left-hand side too complicated to desugar) So unfortunately my most generic form won't work here, I need to specialise increment to be in ST (which sucks, because I want it to work for both IO and ST): increment :: (UMV.Unbox a, Num a, Integral b) => UMV.MVector s a -> b -> ST s (UMV.MVector s a) {-# SPECIALISE INLINE increment :: UMV.MVector s Int -> Word8 -> ST s (UMV.MVector s Int) #-} result: 17,016,192 bytes This is very close to the most specific function instantiations and INLINE, but: - I've lost being generic between ST and IO - it's still a little bigger than the specific instances + INLINE So my questions are: what is going on? Can I have genericity between ST and IO while keeping the low GC usage? How come SPECIALISE INLINE does not give the same result as specific instances + INLINE? Obviously, for this example, I don't really *need* increment to work inside IO, since I'm using runST... but I want to understand what is going on. Profiling Haskell performance and memory usage has always been difficult for me. Much thanks in advance, Rafal Kolanski.

1 0

Munich Haskell Meeting
by Heinrich Hördegen 22 Mar '12

22 Mar '12

Dear all, once again, it's time for our monthly Haskell get-together in Munich. On Wed, 28 Feb 2012, at 19h30, we will meet at Cafe Puck (near the universities). Everybody is invited. If you plan to join, please go to: http://www.haskell-munich.de/dates and add yourself. This will help to reserve tables. Have a nice time until Wednesday, Heinrich -- -- hoerdegen(a)funktional.info www.funktional.info --

1 0

Re: [Haskell-cafe] Are there arithmetic composition of functions?
by oleg＠okmij.org 22 Mar '12

22 Mar '12

> At present we can easily express different flavors of conjunction, but > expressing disjunction is hard. Disjunction is not particularly difficult. See, for example, http://okmij.org/ftp/Haskell/TTypeable/TTypeable.hs and search for ORELSE. The code demonstrates higher-order type-level programming (for example, higher-order function Member with the equality predicate as the argument). The file implements closed-world negation for type predicates. See http://okmij.org/ftp/Haskell/typeEQ.html for explanations. Incidentally, one application of that machinery is precisely your original problem. The code http://okmij.org/ftp/Haskell/TTypeable/NotAFunctionT.hs implements vector spaces as function spaces, so you can use the same operation <+> :: Vspace v => v -> v -> v to add arguments of the type (Num n =>n), Num n => a -> n, Num n => a -> b -> n, etc. (there is also a scalar-vector multiplication).

1 0

GSoC and Data Parallel Haskell
by Dmitry Dzhus 22 Mar '12

22 Mar '12

How are you gentlemen. I'm interested about what additions to DPH would really benefit the community. The only ticket on DPH in GSoC Trac seems a bit stale: http://hackage.haskell.org/trac/summer-of-code/ticket/1537. Any new tips? My field is currently molecular simulation. (I'm doing a Direct Simulation Monte-Carlo implementation for rarefied gas dynamics with application to space satellites&stuffs aerodynamics in Haskell for my Master's thesis, I believe using DPH as well would be my final goal as molecular simulations vectorize nicely. Simulation domain is partitioned into cells and stochastic collision sampling (as in DSMC) may be performed in every cell in parallel.)

3 4

Haskell Weekly News: Issue 219
by Daniel Santa Cruz 22 Mar '12

22 Mar '12

Welcome to issue 218 of the HWN, an issue covering crowd-sourced bits of information about Haskell from around the web. This issue covers the week of March 11 to 17, 2012. Quotes of the Week * cmccann: * cmccann needs to hurry up and get his stream processing library finished before all the possible synonyms for "thing that other things flow through" are taken * shergill: silver bullets don't respect eta equivalency. it needs to be made of silver, and not simply *act* like one :P Top Reddit Stories * Shelly: Write your shell scripts in Haskell Domain: yesodweb.com, Score: 65, Comments: 34 On Reddit: [1] http://goo.gl/lZdyV Original: [2] http://goo.gl/HHIU0 * The Glasgow Haskell Compiler (draft chapter for "The Architecture of Open Source Applications, Volume 2") Domain: community.haskell.org, Score: 53, Comments: 28 On Reddit: [3] http://goo.gl/qVoFj Original: [4] http://goo.gl/Rc42A * Announcing the Yesod Platform Domain: yesodweb.com, Score: 52, Comments: 13 On Reddit: [5] http://goo.gl/TzW0w Original: [6] http://goo.gl/z3fwC * The Cabal of my dreams Domain: blog.johantibell.com, Score: 42, Comments: 19 On Reddit: [7] http://goo.gl/VTpJu Original: [8] http://goo.gl/wrrNP * Announcing: Snap Framework v0.8 Domain: snapframework.com, Score: 39, Comments: 6 On Reddit: [9] http://goo.gl/19EyG Original: [10] http://goo.gl/USfny * Leksah 0.12 Domain: haskell.org, Score: 32, Comments: 9 On Reddit: [11] http://goo.gl/5Ft8w Original: [12] http://goo.gl/K6OEx * uncurryWith and concatenative programming Domain: self.haskell, Score: 30, Comments: 4 On Reddit: [13] http://goo.gl/dzzXH Original: [14] http://goo.gl/dzzXH * New course on parallel functional programming at Chalmers Domain: cse.chalmers.se, Score: 29, Comments: 2 On Reddit: [15] http://goo.gl/vwH6F Original: [16] http://goo.gl/zKQjh * Announcing Haskell project support on travis-ci.org Domain: about.travis-ci.org, Score: 28, Comments: 8 On Reddit: [17] http://goo.gl/uH7g3 Original: [18] http://goo.gl/KbE7I * Anyone in the Toronto area looking for a job? Domain: self.haskell, Score: 28, Comments: 22 On Reddit: [19] http://goo.gl/NHdwz Original: [20] http://goo.gl/NHdwz * Building a Concurrent Web Scraper With Haskell Domain: adit.io, Score: 26, Comments: 1 On Reddit: [21] http://goo.gl/G7QXM Original: [22] http://goo.gl/FV2LO * Using Text.Parsec.Indent to parse an indentation-sensitive language with Haskell’s Parsec library. Domain: spin.atomicobject.com, Score: 26, Comments: 7 On Reddit: [23] http://goo.gl/dXkzO Original: [24] http://goo.gl/9BFa3 * Coapplicative Functor? Domain: self.haskell, Score: 21, Comments: 37 On Reddit: [25] http://goo.gl/4eluT Original: [26] http://goo.gl/4eluT * HalVM: Easy install on Fedora 16 + 64bit support Domain: community.galois.com, Score: 21, Comments: 2 On Reddit: [27] http://goo.gl/goN4p Original: [28] http://goo.gl/6EQAu Top StackOverflow Questions * How do you represent a graph in Haskell? votes: 18, answers: 4 Read on SO: [29] http://goo.gl/t5vij * Impredicative types vs. plain old subtyping votes: 16, answers: 0 Read on SO: [30] http://goo.gl/3cmCj * Can GHC really never inline map, scanl, foldr, etc.? votes: 14, answers: 3 Read on SO: [31] http://goo.gl/se91V * Redefine IO to simplify debugging? votes: 11, answers: 1 Read on SO: [32] http://goo.gl/s62s9 * Quadratic programming in Haskell votes: 11, answers: 1 Read on SO: [33] http://goo.gl/jYWEP * How can I test a higher-order function using QuickCheck? votes: 11, answers: 2 Read on SO: [34] http://goo.gl/1YHql * Haskell: how to map a tuple? votes: 10, answers: 7 Read on SO: [35] http://goo.gl/fk7LE * Repacking monads — any generic way? votes: 9, answers: 4 Read on SO: [36] http://goo.gl/QklWI * Is there any reason not to use the INLINABLE pragma for a function? votes: 9, answers: 1 Read on SO: [37] http://goo.gl/t75CV * Repa 3 performance and correct usage of 'now' votes: 9, answers: 1 Read on SO: [38] http://goo.gl/PbyzK Until next time, Daniel Santa Cruz References 1. http://www.yesodweb.com/blog/2012/03/shelly-for-shell-scripts 2. http://www.reddit.com/r/haskell/comments/qt17p/shelly_write_your_shell_scri… 3. http://community.haskell.org/~simonmar/papers/aos.pdf 4. http://www.reddit.com/r/haskell/comments/qvyup/the_glasgow_haskell_compiler… 5. http://www.yesodweb.com/blog/2012/03/announcing-yesod-platform 6. http://www.reddit.com/r/haskell/comments/qxopq/announcing_the_yesod_platfor… 7. http://blog.johantibell.com/2012/03/cabal-of-my-dreams.html 8. http://www.reddit.com/r/haskell/comments/qwj5j/the_cabal_of_my_dreams/ 9. http://snapframework.com/blog/2012/03/16/snap-0.8-released 10. http://www.reddit.com/r/haskell/comments/qzzfe/announcing_snap_framework_v0… 11. http://www.haskell.org/pipermail/haskell-cafe/2012-March/100023.html 12. http://www.reddit.com/r/haskell/comments/qro91/leksah_012/ 13. http://www.reddit.com/r/haskell/comments/qy8h2/uncurrywith_and_concatenativ… 14. http://www.reddit.com/r/haskell/comments/qy8h2/uncurrywith_and_concatenativ… 15. http://www.cse.chalmers.se/edu/course/pfp/ 16. http://www.reddit.com/r/haskell/comments/quc64/new_course_on_parallel_funct… 17. http://about.travis-ci.org/blog/announcing_support_for_haskell_on_travis_ci/ 18. http://www.reddit.com/r/haskell/comments/qsyr5/announcing_haskell_project_s… 19. http://www.reddit.com/r/haskell/comments/qw99e/anyone_in_the_toronto_area_l… 20. http://www.reddit.com/r/haskell/comments/qw99e/anyone_in_the_toronto_area_l… 21. http://adit.io/posts/2012-03-10-building_a_concurrent_web_scraper_with_hask… 22. http://www.reddit.com/r/haskell/comments/qvp1u/building_a_concurrent_web_sc… 23. http://spin.atomicobject.com/2012/03/16/using-text-parsec-indent-to-parse-a… 24. http://www.reddit.com/r/haskell/comments/qzeyk/using_textparsecindent_to_pa… 25. http://www.reddit.com/r/haskell/comments/qsrmq/coapplicative_functor/ 26. http://www.reddit.com/r/haskell/comments/qsrmq/coapplicative_functor/ 27. http://community.galois.com/pipermail/halvm-devel/2012-March/000022.html 28. http://www.reddit.com/r/haskell/comments/qynuq/halvm_easy_install_on_fedora… 29. http://stackoverflow.com/questions/9732084/how-do-you-represent-a-graph-in-… 30. http://stackoverflow.com/questions/9732766/impredicative-types-vs-plain-old… 31. http://stackoverflow.com/questions/9658438/can-ghc-really-never-inline-map-… 32. http://stackoverflow.com/questions/9656734/redefine-io-to-simplify-debugging 33. http://stackoverflow.com/questions/9672686/quadratic-programming-in-haskell 34. http://stackoverflow.com/questions/9686665/how-can-i-test-a-higher-order-fu… 35. http://stackoverflow.com/questions/9722689/haskell-how-to-map-a-tuple 36. http://stackoverflow.com/questions/9684252/repacking-monads-any-generic-way 37. http://stackoverflow.com/questions/9709823/is-there-any-reason-not-to-use-t… 38. http://stackoverflow.com/questions/9713378/repa-3-performance-and-correct-u…

1 0