Elsevier: Die die die!

For those readers of an academic nature who haven't heard yet, there's a general boycott of Elsevier going on, which I encourage you all to join. For anyone unacquainted with the evil practices of Elsevier check out Cosma Shalizi's links or the links on n-Category Cafe. While this is a general boycott, you can specify separately whether you (1) won't publish with them, (2) won't referee for them, and/or (3) won't do editorial work for them. For the young academics, there's also some discussion on silmaril's LJ crosspost about the potential costs of joining such a boycott. While it is a non-trivial commitment, I do encourage you to join us.

For those who believe in the public sharing of knowledge, there's also a more general pledge, Research Without Walls, to only do business with journals who provide their articles online and without paywalls. I wholeheartedly support this cause, for many of the same reasons that I support F/OSS. If you notice my name isn't on the pledge yet, it's because I need to do a little more research on which conferences and publications this would bar me from before making a public commitment to prohibit myself from (rather than merely disprefer) venues which do not support the freedom of knowledge.

ANN: pointless-fun

pointless-fun 1.1.0

The pointless-fun package offers some common point-free combinators (common for me at least).

Description

Perhaps the most useful is that it packages up Matt Hellige's classic multicomposition trick[1]. These combinators allow you to easily modify the types of a many-argument function with syntax that looks like giving type signatures. For example,

    foo    :: A -> B -> C
    
    albert :: X -> A
    beth   :: Y -> B
    carol  :: C -> Z
    
    bar :: X -> Y -> Z
    bar = foo $:: albert ~> beth ~> carol

I've found this to be especially helpful for defining non-derivable type class instances for newtypes since it both abstracts away the plumbing and also makes explicit what you mean.

Other prevalent combinators include, (.:) for binary composition:

    (f .: g) x y = f (g x y)
    -- or,
    f .: g = curry (f . uncurry g)

This is the same as the common idiom (f .) . g but more easily extended to multiple uses, due to the fixity declaration.

And (.!) for function composition which calls the right-hand function eagerly; i.e., making the left-hand function strict in its first argument.

    (f .! g) x = f $! g x

This defines the composition for the sub-category of strict Haskell functions. If the Functor class were parameterized by the domain and codomain categories (e.g., a regular Functor f would be CFunctor (->) (->) f instead) then this would allow us to define functors CFunctor (->) (!->) f where fmap f . fmap g = fmap (f .! g)

[1] http://matt.immute.net/content/pointless-fun

Links

• Homepage: http://code.haskell.org/~wren/
• Hackage: http://hackage.haskell.org/package/pointless-fun
• Darcs: http://community.haskell.org/~wren/pointless-fun
• Haddock: Darcs version

ANN: data-or

data-or 1.0.0

The data-or package offers a data type for non-exclusive disjunction. This is helpful for things like a generic merge function on sets/maps which could be union, mutual difference, etc. based on which Or value a function argument returns. Also useful for non-truncating zips (cf. zipOr) and other cases where you sometimes want an Either and sometimes want a pair.

Links

• Homepage: http://code.haskell.org/~wren/
• Hackage: http://hackage.haskell.org/package/data-or
• Darcs: http://community.haskell.org/~wren/data-or
• Haddock: Darcs version

ANN: exact-combinatorics

exact-combinatorics 0.2.0

The exact-combinatorics package offers efficient exact computation of common combinatorial functions like the binomial coefficients and factorial. (For fast approximations, see the math-functions package instead.)

Description

Math.Combinatorics.Exact.Primes

Provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.)

Math.Combinatorics.Exact.Binomial

Offers a fast computation of the binomial coefficients based on the prime factorization of the result. As it turns out, it's easier to compute the prime factorization of the answer than it is to compute the answer directly! And you don't even need the factorial function to do so. Albeit, with a fast factorial function, the naive definition of binomial coefficients gives this algorithm a run for its money.

Math.Combinatorics.Exact.Factorial

Offers a fast computation of factorial numbers. As Peter Luschny comments, the factorial function is often shown as a classic example of recursive functions, like addition of Peano numbers, however that naive way of computing factorials is extremely inefficient and does a disservice to those learning about recursion. The current implementation uses the split-recursive algorithm which is more than sufficient for casual use. I'm working on implementing the parallel prime-swing algorithm, which should be a bit faster still.

Links

• Homepage: http://code.haskell.org/~wren/
• Hackage: http://hackage.haskell.org/package/exact-combinatorics
• Darcs: http://community.haskell.org/~wren/exact-combinatorics
• Haddock: Darcs version

ANN: bytestring-lexing 0.3.0

bytestring-lexing 0.3.0

The bytestring-lexing package offers efficient reading and packing of common types like Double and Integral types.

Administrative Changes (since 0.2.1)

Change of maintainer. Don Stewart handed maintainership of the package over to myself when I voiced interest.

Change of repo type. The old repo for the package used Darcs-1 style patches. I've converted the repository to Darcs-2 hashed. This means that the new repository cannot exchange patches with the old Darcs-1 repo (or any other Darcs-2 conversions that may be floating around out there). So anyone who's interested in contributing should scrap their local copies and get the new repo.

Code Changes (since 0.2.1)

Added Data.ByteString.Lex.Integral which provides efficient implementations for reading and packing/showing integral types in ASCII-compatible formats including decimal, hexadecimal, and octal.

The readDecimal function in particular has been highly optimized. The new version is wicked fast and perfectly suitable for hot code locations like parsing headers for HTTP servers like Warp. In addition, attention has been paid to ensuring that parsing is efficient for larger than native types like Int64 on 32-bit systems (including 64-bit OS X), as well as Integer. The optimization of this function was done in collaboration with Erik de Castro Lopo, Vincent Hanquez, and Christoph Breitkopf following a blog post by Erik and ensuing discussion on Reddit.

A Criterion report is available for 64-bit Intel OS X running 32-bit GHC 6.12.1. The benchmark is included in the repo and has also been run on 64-bit GHC 7 systems, which differ primarily in not showing slowdown for Int64 vs Int (naturally). If you're curious about the different implementations:

• readIntBS / readIntegerBS --- are the readInt and readInteger functions in Data.ByteString
• readDecimalOrig (correct) --- was my original implementation, prior to collaboration with Erik, Vincent, and Christoph.
• readIntegralMH (buggy) --- or rather a non-buggy version very much like it, is the implementation currently used in Warp.
• readDecimal (current) --- is the current implementation used in this package.

Links

• Homepage: http://code.haskell.org/~wren/
• Hackage: http://hackage.haskell.org/package/bytestring-lexing
• Darcs: http://community.haskell.org/~wren/bytestring-lexing
• Haddock: Darcs version