- Haskell-Cafe - Haskell.org

Hash table constructors return table in IO Monad. Why?
by michael rice 13 May '11

13 May '11

Is there some reason why ALL the ways to create a hash table return one in the IO Monad, but all the functions for retrieving a value from a hash table take as an argument a hash table NOT in the IO Monad? Michael ================= Prelude Data.HashTable> let ht = fromList id [(5,'a'),(6,'b')]Prelude Data.HashTable> fmap ((flip Data.HashTable.lookup) 6) htPrelude Data.HashTable> Prelude Data.HashTable> :t fmap ((flip Data.HashTable.lookup) 6) htfmap ((flip Data.HashTable.lookup) 6) ht :: IO (IO (Maybe Char))

4 6

ANNOUNCE: iterIO-0.1 - iteratee-based IO with pipe operators
by David Mazieres 12 May '11

12 May '11

Hi, everyone. I'm pleased to announce the release of a new iteratee implementation, iterIO: http://hackage.haskell.org/package/iterIO IterIO is an attempt to make iteratees easier to use through an interface based on pipeline stages reminiscent of Unix command pipelines. Particularly if you've looked at iteratees before and been intimidated, please have a look at iterIO to see if it makes them more accessible. Some aspects of iterIO that should simplify learning and using iteratees are: * Every aspect of the library is thoroughly document in haddock including numerous examples of use. * Enumerators are easy to build out of iteratees. * There is no difference between enumerators and "enumeratees" (i.e., inner pipeline stages). The former is just a type-restricted version of the latter. * Parsing combinators provide detailed error reporting and support LL(*) rather than LL(1) parsing, leading to fewer non-intuitive parsing failures. A couple of tricks avoid consuming excessive memory for backtracking. * Super-fast LL(1) parsing is also available through seamless integration with attoparsec. * A universal exception mechanism works across invocations of mtl monad transformers, thereby unifying error handling. * All pipe operators have uniform semantics, eliminating corner cases. In particular, if the writing end of a pipe fails, the reading end always gets EOF, allowing it to clean up resources. * One can catch exceptions thrown by any contiguous subset of stages in a pipeline. Moreover, enumerator exception handlers can resume downstream stages that haven't failed. * The package is full of useful iteratees and enumerators, including basic file and socket processing, parsec-like combinators, string search, zlib/gzip compression, SSL, HTTP, and "loopback" enumerator/iteratee pairs for testing a protocol implementation against itself. Please enjoy. I'd love to hear feedback. David

16 32

parsing currency amounts with parsec
by Eric Rasmussen 12 May '11

12 May '11

Hi everyone, I am relatively new to Haskell and Parsec, and I couldn't find any articles on parsing numbers in the following format: Positive: $115.33 Negative: ($1,323.42) I'm working on the parser for practical purposes (to convert a 3rd-party generated, most unhelpful format into one I can use), and I'd really appreciate any insight into a better way to do this, or if there are any built-in functions/established libraries that would be better suited to the task. My code below works, but doesn't seem terribly efficient. Thanks! Eric ------------------------------------------------- {- parses positive and negative dollar amounts -} integer :: CharParser st Integer integer = PT.integer lexer float :: CharParser st Double float = PT.float lexer currencyAmount = try negAmount <|> posAmount negAmount = do char '(' char '$' a <- currency char ')' return (negate a) posAmount = do char '$' a <- currency return a currency = do parts <- many floatOrSep let result = combine orderedParts where combine = sumWithFactor 1 orderedParts = reverse parts return result floatOrSep = try float <|> beforeSep beforeSep = do a <- integer char ',' return (fromIntegral a :: Double) sumWithFactor n [] = 0 sumWithFactor n (x:xs) = n * x + next where next = sumWithFactor (n*1000) xs

5 6

Haskell Weekly News: Issue 181
by Daniel Santa Cruz 12 May '11

12 May '11

Welcome to issue 181 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of May 1 to 7, 2011. Announcements Last week I failed to note the announcement [http://goo.gl/ApClU] of a new version of Leksah (0.10.0). If you haven't yet, give Leksha a test run and send some feedback! Ketil Malde started a thread [http://goo.gl/Prlu2] about Robert Harper's thoughts on monads and laziness. Hakim Cassimally extended an invitation [http://goo.gl/QIjcF] to anyone living in the Northwest UK for Tuesday May 31st to Geekup's first ever "Functional Programming Night". Andy announced [http://goo.gl/uCEn1] a new release of Manatee (0.2.1). Quotes of the Week * hpc: [SPOILER] You can check wikipedia for the definition of fibonacci sequences if you get stuck after half an hour * pmetzger: it is always possible to make an algorithm slower. just give it to a CS freshman to code up. * kmc: ghc -XMixfixOperators -XDependentTypes -XMakeMeASandwich * pmetzger: I have my password tattooed to my forehead. that way when I forget it others can tell me what it is. * alexbagel: i find that my first 26 variables are always easy to name. after that it becomes a bit harder. * Eric Kow: Haskell is a good fit for me because I tend to practise Doh!-oriented programming Top Reddit Stories * More points for lazy evaluation Domain: augustss.blogspot.com, score: 56, comments: 24 On Reddit: http://goo.gl/qecQ1 Original: http://goo.gl/OnJXx * iterIO: iteratee-based IO with pipe operators, courtesy David Mazieres Domain: haskell.org, score: 43, comments: 15 On Reddit: http://goo.gl/YzPJn Original: http://goo.gl/6WQAk * Monad comprehensions are finally in GHC Domain: self.haskell, score: 37, comments: 32 On Reddit: http://goo.gl/1Rjnw * Horner's Rule Domain: patternsinfp.wordpress.com, score: 34, Comments: 2 On Reddit: http://goo.gl/A1wYo Original: http://goo.gl/zeC1f * Patent 5,893,120 reduced to mathematical formulae (via Haskell) Domain: paulspontifications.blogspot.com, score: 31, comments: 13 On Reddit: http://goo.gl/PmB4K Original: http://goo.gl/QknmV * Custom Haskell mug! Domain: imgur.com, score: 31, comments: 6 On Reddit: http://goo.gl/lD388 Original: http://goo.gl/bzZR8 * Differences between 'data' and 'newtype' ... in pictures Domain: stackoverflow.com, score: 31, comments: 2 On Reddit: http://goo.gl/5YaSo Original: http://goo.gl/KQiJv * Haskell: not pure enough? Domain: blog.ezyang.com, score: 30, comments: 19 On Reddit: http://goo.gl/6v28x Original: http://goo.gl/zsfSq * Galois is hiring computer scientists Domain: corp.galois.com,score: 27, comments: 28 On Reddit: http://goo.gl/ToeJ0 Original: http://goo.gl/osjJY * Fancy comparison of Data values Domain: pnyf.inf.elte.hu, score: 26, comments: 18 On Reddit: http://goo.gl/BlFVl Original: http://goo.gl/RuMKT Top StackOverflow Questions * Ordering of parameters to make use of currying votes: 43, answers: 3 Read on SO: http://goo.gl/7LnBJ * Difference between 'data' and 'newtype' in Haskell votes: 29, answers: 2 Read on SO: http://goo.gl/KQiJv * Haskell: why the convention to name a helper function "go"? votes: 24, answers: 3 Read on SO: http://goo.gl/CE1O7 * How do you design programs in Haskell or other functional programming languages? [migrated] votes: 24, answers: 0 Read on SO: http://goo.gl/IW7Z5 * Haskell Graphics Library that works in GHCi on MacOS X votes: 19, answers: 3 Read on SO: http://goo.gl/VZGAK About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz

1 0

request for example code referenced in "All About Monads"
by Michael Litchard 11 May '11

11 May '11

The html version of All About Monads has dissapeared, so I am making due with the pdf version. As a consequence I don't have access to the example code files referenced. I know someone out there has them. Could you make them available please?

1 0

Parallel Haskell Digest 2
by Eric Y. Kow 11 May '11

11 May '11

Parallel Haskell Digest ======================= Edition 2 2011-05-11 Hello Haskellers! Welcome to the second edition of the Parallel Haskell Digest, bringing you news, discussions and tasters of parallelism and concurrency in Haskell. The digest is made possible by the Parallel GHC project. More news about how we're doing below. Note that this edition of the digest may be best viewed in blog form at http://www.well-typed.com/blog/52 (there's an inline picture). News ---------------------------------------------------------------------- * Workshop of the 2nd SICSA MultiCore Challenge (27 May, Glasgow; registration deadline 18 May) The goal of the SICSA MultiCore challenge is to bring together researchers in the area of parallel programming, by implementing one or more challenge applications on (networks of) multi-core machines. The goal is to learn about the strengths and weaknesses of current systems for parallel programming by comparing them on a common application. The final workshop will feature presentations of the individual implementations, assessing both raw performance as well as ease of parallelisation and other aspects in the development of this parallel application. https://groups.google.com/d/topic/parallel-haskell/K-IJ2roA59I/discussion * Parallel Haskell Portal One of things I've been working on at Well-Typed is to help clean up the Haskell wiki documentation on parallelism and concurrency. There's still a bit of gardening to do, but we're ready to unveil what we have now. The Parallel Haskell portal is targeted primarily at people getting started with parallelism and concurrency in Haskell. It places a lot of emphasis on steering readers towards mature technologies, while still offering a path for more advanced users to dig deeper into current research. http://www.haskell.org/haskellwiki/Parallel Word of the Month ---------------------------------------------------------------------- This edition of the digest is brought to you by threads, threads and more threads. In the last digest, we took a look at Haskell sparks and particularly at how they differ from threads. Now let's delve a little bit deeper into threads. A "thread of execution" is a programming abstraction that helps the programmer separate concerns within a program. Consider a web server serving many documents to many clients simultaneously. The programmer may wish to use threads, using one thread per client making it easier to manage concurrent action. [1] In the Haskell world, this programming abstraction is provided by Haskell threads. To implement Haskell threads, the GHC runtime system uses what is known as a M:N threading model, where many Haskell threads are scheduled across a much smaller number of operating system threads. This model has two key benefits: * it can make use of multiple CPU cores * it allows Haskell threads to be very cheap Don Stewart illustrated this on StackOverflow with the following diagram, citing 2011 figures of a handful of CPUs, a dozen or so OS threads and tens of thousands of Haskell threads (plus for those of us interested in pure parallelism, millions of sparks). http://i.imgur.com/u53Uk.png If you want to try generating some figures for yourself, have a look at the benchmark utility at http://darcs.haskell.org/nofib/smp/threads005/Main.hs The benchmark tool creates a large "pipeline" of simultaneous Haskell threads, and tries to send a message through the pipeline, passing it from one thread to the next. On my laptop, I can create 10000 Haskell threads in 0.074 seconds and pump "Hello World" through them in 0.07 seconds. That works out to 7.4 microseconds per thread (0.7 microseconds for pumping). How about giving it a shot on your computer? Haskell threads are very lightweight. For most concurrency needs, you can generally forget that operating system threads exist. Indeed, when the documentation for modules like Control.Concurrent refers to "threads", or when Haskell hackers discuss threads in Haskell code it's a good bet that they're referring to Haskell threads rather than OS threads. That said, there are a few occasions where you may want to be aware about OS threads, in order of importance, if you * want your Haskell threads to be running in parallel on multiple cores (for better performance) instead of just being interleaved on a single core, or * need to make foreign calls concurrently with doing other things (eg. running Haskell code or making other foreign calls) Doing any of these things requires that you use GHC's multi-threaded runtime system. GHC currently uses a single-threaded runtime system by default, but until this changes, you will have to explicitly enable the multi-threaded one by linking your program with the flag `-threaded`. With the multi-threaded runtime system all Haskell threads are scheduled across multiple OS threads as opposed to being interleaved on a single one. This allows for parallelism in the first case, for concurrent foreign code in the second case. For the first case, you may want to note that on top of enabling the multi-threaded RTS, you will also need to tell the runtime system to let some of those run some of those OS threads simultaneously (which in run requires that you have multiple cores). You can do this by passing `+RTS -N` to your program during runtime (with GHC 6.12.1 and higher, the bare -N flag will cause the RTS to use a sensible default based on the number of CPU cores on your machine). This is only if you are specifically interested in parallelism. If you are only concerned about making foreign calls, just enabling the multi-threaded RTS is enough. The issue with the single-threaded runtime system is that Haskell threads that make foreign calls to the operating system or C libraries will block all other Haskell threads. This means that if a foreign call should take a long time, or worse, if it should block in its own right, all other Haskell threads will be stuck. With the multi-threaded runtime system, Haskell that make foreign calls do not block other Haskell threads, because they can be handed over to another OS thread while the one making the foreign call is churning away. But be careful! Concurrency with foreign calls can be a tricky business. If you are only using one OS thread at a time, you are effectively shielded from having to worry about concurrency issues in foreign code (by not being able to run foreign code concurrently). Enabling multi-threaded mode comes with extra responsibility of making sure any foreign libraries you use are thread-safe, or that you have adequate mechanisms to deal with the ones that are not. Thread-safety isn't an issue with Haskell-only code because shared state is always managed with locks or atomicity. But when concurrency and foreign calls mix, you will need to take care. There's another issue to watch out for when mixing foreign calls with multiple OS threads. The nice thing thing about the M:N threading model in Haskell is that the GHC RTS scheduler will automatically move Haskell threads between OS thread to achieve a good balance of work. But this introduces a new problem for foreign libraries that use thread-local state: the Haskell thread may calling the library from any number of OS threads, so if the foreign library uses OS-thread-local state then this state could be different from one call to the next... what a mess! To solve this problem we have to use a feature called "bound threads". Bound threads are Haskell threads that are bound to a single OS thread; they are not moved around by the scheduler. Bound threads are more expensive than unbound ones because they tie up a whole OS thread, but they are necessary for working with certain foreign libraries like OpenGL that make essential use of thread local state. Summing up threads in Haskell: * When writing concurrent programs in Haskell, we deal primarily with Haskell threads, paying attention only to OS threads when we have to. * Haskell threads run on one or more OS threads, but you get concurrency either way. It is likely that in the future, GHC will use multiple OS threads by default but for now you have to explicitly enable it by linking your program using `-threaded`. * Foreign calls are potentially tricky! Make sure you either use thread-safe libraries or know how to manage non thread-safe ones. * If you are using foreign libraries that use thread-local state, use bound threads, that is, Haskell threads tied to an OS thread. [1] Thanks to Paul Bone for this paragraph https://groups.google.com/d/topic/parallel-haskell/fd6B9zbOvwM/discussion and also to Andres and Duncan from Well-Typed for extensive help revising this word of the month! Parallel GHC project news ---------------------------------------------------------------------- The Parallel GHC Project is an MSR-funded project to push the real-world use of parallel Haskell. Part of this project involves effort by Well-Typed to provide tools for use by the general community: We have begun work on making the "Modified Additive Lagged Fibonacci" and perhaps other random number generators from the SPRNG library available in Haskell. As a first step to the Haskell SPRNG reimplementation, we have developed a [binding](https://github.com/bjpop/haskell-sprng) to the existing C++ library. The binding will serve as a refernence implementation to test against, but it also ready to be used now. To complement our work on extending GHC eventlog and Threadscope to support multi-process or distributed Haskell systems, we have begun work on developing new visualisations for ThreadScope, including the rate of parallel spark creation, and the distribution of spark evaluation times. Meanwhile, work continues on our project partners' side. We hope to be say more about it in the next edition of the digest :-) For more information on the Parallel GHC project, see http://www.haskell.org/haskellwiki/Parallel_GHC_Project Talks ---------------------------------------------------------------------- 1. High-Performance Web Applications in Haskell Gregory Collins gave a talk at QCon London (11 March). Greg delivered this message to an an enterprise software development crowd: "Haskell is a really good choice for web programming". Check out his slides to see how Haskell can help you to write scalable web applications http://qconlondon.com/dl/qcon-london-2011/slides/GregoryCollins_HighPerform… 1. Parallel = functional: the way of future. Simon Peyton-Jones gave the keynote talk at the London FP Exchange (18 March), with a whirlwind overview of what's going on in the world of parallel Haskell. You can watch the [video](http://skillsmatter.com/podcast/scala/talk-by-haskell-expert-simon-p… and follow along on the [slides](http://research.microsoft.com/%7Esimonpj/papers/parallel/Parallel-H…. Blogs, papers and packages ---------------------------------------------------------------------- 1. Mstate - a concurrent state monad (5 April). Nils Schweinsberg released a small library called mstate which offers a threadsafe equivalent to the State monad (and transformer). The library makes it easy to start stateful threads, grab their results when they finish and handle any exceptions along the way. http://blog.n-sch.de/2011/04/05/mstate-a-concurrent-state-monad/ 1. monad-par - This library offers an alternative parallel programming API to that provided by the parallel package. The Par monad allows the simple description of parallel computations, and can be used to add parallelism to pure Haskell code. The basic API is straightforward: the monad supports forking and simple communication in terms of IVars. The library comes with an efficient work-stealing implementation, but the internals are also exposed so that you can build your own scheduler if necessary. http://hackage.haskell.org/package/monad-par 1. Real-time edge detection with the latest release of the parallel array library Repa. The folks at UNSW have released version 2.0.0.1 of the Repa high performance parallel array library, with along with an example use case doing edge detection in real time with the Canny algorithm. http://pls.posterous.com/real-time-edge-detection-with-the-latest-rele 1. Haskell for the Cloud (Jeff Epstein, Andrew Black and Simon Peyton Jones) Erlang style distributed programming in Haskell "We present Cloud Haskell, a domain-specific language for developing programs for a distributed-memory computing environment. Implemented as a shallow embedding in Haskell, it provides a message-passing communication model, inspired by Erlang, without introducing incompatibility with Haskell's established shared-memory concurrency. A key contribution is a method for serializing function closures for transmission across the network. Cloud Haskell has been implemented; we present example code and some preliminary performance measurements'" * http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/remot… * http://www.reddit.com/r/haskell/comments/gjb52/haskell_for_the_cloud_new_pa… * http://hackage.haskell.org/trac/ghc/wiki/ErlangInHaskell Parallel-Haskell and Haskell Cafe ---------------------------------------------------------------------- * How to daemonize a threaded Haskell program? (5 March). Bas van Dijk would like to turn his Haskell program into a Unix daemon. This is made complicated by the fact that his program needs to run simultaneous threads, and that forkProcess is not supported in GHC when running on multiple processors. Bas wrote a C wrapper to do the forking and call his Haskell main function, and asked about the practicalities of combining the two pieces with Cabal. Further discussion converged on doing the daemonization outside the program, in particular with the help of Upstart on Ubuntu. * http://www.haskell.org/ghc/docs/latest/html/libraries/unix-2.4.2.0/System-P… * http://www.haskell.org/pipermail/haskell-cafe/2011-March/089891.html * Parallel Haskell stories (9 March). Simon Peyton Jones was looking for stories about using parallel or concurrent Haskell to use in his keynote talk (see above). Stories so far: basic concurrency in the IRC Hulk (see PH Digest 1), STM in a vending machine simulator, and the BitTorrent client Combinatorrent, and parallelism in the Cryptographic Protocol Shapes Analyzer http://www.haskell.org/pipermail/haskell-cafe/2011-March/090028.html * Light and fast HTTP server (11 March) Victor Oliveira needed help choosing among all the HTTP servers on Hackage. He wanted something light, fast and basic along the lines of nginx. Responses so far point mainly to Snap and Warp. http://www.haskell.org/pipermail/haskell-cafe/2011-March/090114.html * Simple STM question (15 March) qld3303 noticed a bit of STM code seemed to stop working when he upgrade to GHC 7.0.2. The issue turns out to have been a mistaken use of "pure" to run an IO action, which is a no-op as pure for IO is the same as return. http://www.haskell.org/pipermail/haskell-cafe/2011-March/090182.html * STM, newArray, and a stack overflow? (23 March) Ketil Malde got a stack overflow creating a large array in STM. The equivalent code works fine in the ST monad, or in GHCi. After some digging around, Bas van Dijk tracked it down to a bug in the newArray method of TArray. His fix has been pushed and should appear in GHC 7.2. * http://www.haskell.org/pipermail/haskell-cafe/2011-March/090419.html * http://hackage.haskell.org/trac/ghc/ticket/5042 * Writing to a FIFO when the reader stops reading (13 March) Brian D had some simple code that continuously writes to a FIFO and gets a "Broken pipe" error when the reader goes away. He wanted to check that this was expected behaviour (it was) and that he wasn't missing something on the Haskell side (he wasn't). The advice was to use a Unix file socket instead. http://www.haskell.org/pipermail/haskell-cafe/2011-March/090142.html * BlockedIndefinitelyOnMVar exception (31 March) Mitar wanted to know if there was any way to disable throwing BlockedIndefinitelyOnMVar exceptions. Such exceptions are thrown during a particular known deadlock, "when a thread is blocked on an MVar but there are no other references to the MVar so it can't ever continue." This lead to more discussion about what to do during cases where it would be desirable to just keep the thread around (eg. until it's explicitly killed). Some options are to catch and ignore the exception; or to contrive to keep some other references to the MVar (eg. putting it in a StablePtr), or otherwise prevent the thread from being garbage collected. * http://www.haskell.org/pipermail/haskell-cafe/2011-March/090624.html * http://www.haskell.org/ghc/docs/latest/html/libraries/base-4.3.1.0/Control-… * Parallelism and concurrency revisited and diagrammed. To help me come to grips with how people talk about "parallelism" and "concurrency" in Haskell, I tried making a diagram how our language about the two interleave. https://groups.google.com/d/topic/parallel-haskell/j85VZvRujyg/discussion Stack Overflow ---------------------------------------------------------------------- * How to choose between parList and parBuffer ? http://stackoverflow.com/questions/5352683/how-to-choose-between-parlist-an… * How to exploit any parallelism in my haskell parallel code ? (17 March) http://stackoverflow.com/questions/5345981/how-to-exploit-any-parallelism-i… * Performance considerations of Haskell FFI / C? (14 April) http://stackoverflow.com/questions/5665209/performance-considerations-of-ha… * Reentrant caching of “referentially transparent” IO calls http://stackoverflow.com/questions/5484847/reentrant-caching-of-referential… (30 March) Help and feedback ---------------------------------------------------------------------- Got something for the digest? Send me an email at eric(a)well-typed.com. I'm particularly interested in short parallelism/concurrency puzzles, cool projects for featured code. Other comments and feedback (criticism and corrections especially!) would be welcome too. -- Eric Kow <http://erickow.com>

1 0

Markov chain algorithm (from "The Practice of Programming", Kernighan/Pike)
by michael rice 11 May '11

11 May '11

It's hard to improve on a 20 line Awk program for generating text but I thought it would be fun to investigate a Haskell solution. Why can't I cons an element onto an existing list? Michael Prelude Data.List Data.Map> insertWith (:) ("Moby", "Dick") "will" (fromList [(("Joe", "Blow"),["is"]), (("Moby", "Dick"),["may"])]) <interactive>:1:11: Occurs check: cannot construct the infinite type: a = [a] Expected type: a Inferred type: [a] In the first argument of `insertWith', namely `(:)' In the expression: insertWith (:) ("Moby", "Dick") "will" (fromList [(("Joe", "Blow"), ["is"]), (("Moby", "Dick"), ["may"])])Prelude Data.List Data.Map>

3 2

need help on building a huge graph
by Bin Jin 11 May '11

11 May '11

Hi, cafe I'm recently solving some algorithm puzzles from previous Google Code Jam rounds, and today I met some problem I can't solve now. It's a problem (Round 3 2010, B) that the solution require to find a shortest path in a graph with about 100,000 vertices and 50 edges from each vertex. Apart from find shortest path, I find that building graph also takes a lot of time. Yes, I know it's unnecessary to dump the entire graph to the memory, but I want to know if it's possible to build such graph in some reasonable time. following is a snippet of code building the graph, runs about 15 mins on Core 2 Duo 2.40GHz without any RTS flags > > > import Data.Array > > > > main = graph `seq` putStrLn "Finished" > > > > n = 100000 > > bnds = (0, n-1) > > > > buildGraph bnds edges = accumArray (flip (:)) [] bnds edges > > > > graph = buildGraph bnds edges > > > > edges = [ (i, (y, 1 - x::Int)) > > | i <- range bnds > > , j <- [2..50] > > , let (x, y) = if i + j >= n then (1, i + j - n) else (0, i + j) > > ] > > > Regards, Bin Jin

2 2

Calculating the accuracy of bloom filters
by Ketil Malde 11 May '11

11 May '11

Hi, I'm using Bryan's bloomfilter package, and I would like to calculate the false positive rate after constructing the bloom filter. Two reasons: 1. Bloom filters have a power-of-two size, which means that the FP rate you ask for becomes an approximation (upper bound), and the real FP rate might be much smaller (down to the square of the requested value?) 2. When constructing the filters (inserting elements), I expect many duplicate elements. Since the FP rate only increases with insertion of unique elements, the a priori estimate is likely an overestimation. If I understand correctly, this is a simple matter of counting 1-bits in the array, and then taking the proportion of set bits ('b', say) to the power of (number of hash functions - 'h', say). Calculating b is easily done, but I don't know how to get at the number of hash functions. The Bloom filter data structure contains data Bloom a = B { hashB :: !(a -> [Hash]) , shiftB :: !Int , maskB :: !Int , bitArrayB :: !(UArray Int Hash) } I'm not sure how shiftB/maskB work, but I do have a function hashB that for any a will generate the list of hashes, i.e., I want the length of this list (which is constant for any a). But I need an 'a' to feed to it, and I don't see exactly how to do that. I notice that Neil's cmdargs have a value 'def', which seems to produce a "default" value, probably using some Typeable or Dynamic magic. Is that something I could leverage for my purposes? -k -- If I haven't seen further, it is by standing in the footprints of giants

1 0

Re: [Haskell-cafe] ANNOUNCE: iterIO-0.1 - iteratee-based IO with pipe operators
by John Lato 11 May '11

11 May '11

> > From: dm-list-haskell-cafe(a)scs.stanford.edu > > At Fri, 6 May 2011 10:10:26 -0300, > Felipe Almeida Lessa wrote: > > > So, in the enumerator vs. iterIO challenge, the only big differences I > see are: > > > > a) iterIO has a different exception handling mechanism. > > b) iterIO can have pure iteratees that don't touch the monad. > > c) iterIO's iteratees can send control messages to ther enumerators. > > d) iterIO's enumerators are enumeratees, but enumerator's enumerators > > are simpler. > > e) enumerator has fewer dependencies. > > f) enumerator uses conventional nomenclature. > > g) enumerator is Haskell 98, while iterIO needs many extensions (e.g. > > MPTC and functional dependencies). > > > > Anything that I missed? > > > > The bottomline: the biggest advantage I see right now in favor of > > iterIO is c), > > I basically agree with this list, but think you are underestimating > the value of a. I would rank a as the most important difference > between the packages. (a also is the reason for d.) > 'a' is important, but I think a lot of people underestimate the value of 'c', which is why a control system was implemented in 'iteratee'. I would argue that iteratee's control system is more powerful than you say. For example, the only reason iteratee can't implement tell is because it doesn't keep track of the position in the stream, it's relatively simple for an enumerator to return data to an iteratee using an IORef for example. And adding support to keep track of the stream position would be a pretty simple (and possibly desirable) change. But it's definitely not as sophisticated as IterIO, and probably won't become so unless I have need of those features. I like the MonadTrans implementation a lot. The vast majority of iteratees are pure, and GHC typically produces more efficient code for pure functions, so this is possibly a performance win. Although it makes something like the mutable-iter package very difficult to implement... John Lato

2 1