July 2012 - Libraries

Proposal: Add hasBitSize to Data.Bits.Bits
by Edward Kmett 27 Jul '12

27 Jul '12

There is currently no way to know whether or not calling Data.Bits.bitSizewill crash your program. I propose extending the Bits class to include: hasBitSize :: Bits b => b -> Bool such that it returns False for Integer and True for the other instances since the vast majority of instances are finite, it may be reasonable to set the default definition to hasBitSize _ = False Discussion Period: 2 weeks

2 2

Haskell platform proposal: split package
by Brent Yorgey 25 Jul '12

25 Jul '12

Hello everyone, This is a proposal for the split package [1] to be included in the next major release of the Haskell platform. Everyone is invited to review this proposal, following the standard procedure [2] for proposing and reviewing packages. Review comments should be sent to the libraries mailing list by August 20 (arbitrarily chosen; there's plenty of time before the October 1 deadline [3]). The Haskell Platform wiki will be kept up-to-date with the results of the review process: http://trac.haskell.org/haskell-platform/wiki/Proposals/split [1] http://hackage.haskell.org/package/split [2] http://trac.haskell.org/haskell-platform/wiki/AddingPackages [3] http://trac.haskell.org/haskell-platform/wiki/ReleaseTimetable Credits ======= Proposal author and package maintainer: Brent Yorgey <byorgey at cis.upenn.edu> Abstract ======== The Data.List.Split module contains a wide range of strategies for splitting lists with respect to some sort of delimiter, mostly implemented through a unified combinator interface. The goal is to be a flexible yet simple alternative to the standard 'split' function found in some other mainstream languages. Documentation and tarball from the hackage page: http://hackage.haskell.org/package/split Development repo: darcs get http://code.haskell.org/~byorgey/code/split Rationale ========= Splitting a list into chunks based on some sort of delimiter(s) is a common need, and is provided in the standard libraries of several mainstream languages (e.g. Python [4], Ruby [5], Java [6]). Haskell beginners routinely ask whether such a function exists in the standard libraries. For a long time, the answer was no. Adding such a function to Haskell's standard libraries has been proposed multiple times over the years, but consensus was never reached on the design of such a function. (See, e.g. [7, 8, 9].) [4] http://docs.python.org/py3k/library/stdtypes.html?highlight=split#str.split [5] http://www.ruby-doc.org/core-1.9.3/String.html#method-i-split [6] http://docs.oracle.com/javase/7/docs/api/java/lang/String.html#split(java.l… [7] http://www.haskell.org/pipermail/libraries/2006-July/005504.html [8] http://www.haskell.org/pipermail/libraries/2006-October/006072.html [9] http://www.haskell.org/pipermail/libraries/2008-January/008922.html In December 2008 the split package was released, implementing not just a single split method, but a wide range of splitting strategies. Since then the split package has gained wide acceptance, with almost 95 reverse dependencies [10], putting it in the top 40 for number of reverse dependencies on Hackage. [10] http://packdeps.haskellers.com/reverse/split The package is quite stable. Since the 0.1.4 release in April 2011 only very minor updates have been made. It has a large suite of QuickCheck properties [11]; to my recollection no bugs have ever been reported. [11] http://code.haskell.org/~byorgey/code/split/Properties.hs API === For a detailed description of the package API and example usage, see the Haddock documentation: http://hackage.haskell.org/packages/archive/split/0.1.4.3/doc/html/Data-Lis… Design decisions ================ Most of the library is based around a (rather simple) combinator interface. Combinators are used to build up configuration records (recording options such as whether to keep delimiters, whether to keep blank segments, etc). A configuration record is finally handed off to a function which performs a generic maximally-information-preserving splitting algorithm and then does various postprocessing steps (based on the configuration) to selectively throw information away. It is probably not the fastest way to implement these methods, but speed is explicitly not a design goal: the aim is to provide a reasonably wide range of splitting strategies which can be used simply. Blazing speed (or more complex processing), when needed, can be obtained from a proper parsing package. Open issues =========== Use of GHC.Exts --------------- At the request of a user, the 0.1.4.3 release switched from defining its own version of the standard 'build' function, to importing it from GHC.Exts. This allows GHC to do more optimization, resulting in reported speedups to uses of splitEvery, splitPlaces, and splitPlacesBlanks. However, this makes the library GHC-specific. If any reviewers think this is an issue I would be willing to go back to defining build by hand, or use CPP macros to select between build implementations based on the compiler. Missing strategies ------------------ The specific way that the generic splitting algorithm is implemented does preclude some imaginable splitting strategies. For example, a few years ago I tried adding a strategy that used a predicate on pairs of elements, splitting down the middle of any pairs that satisfy the predicate, but gave up because it simply did not fit.

13 29

Data.ByteString.packCStringLen for Ptr Word8
by Henning Thielemann 25 Jul '12

25 Jul '12

I want to copy a piece of memory addressed by a Ptr Word8 into a ByteString. I only found packCStringLen for that purpose but it expects a Ptr CChar as input. Since ByteString represents a sequence of Word8 I thought that the most natural input for packCStringLen should be (Ptr Word8). Of course I can use castPtr but that always looks like a hack.

1 0

split package HP proposal, round 2
by Brent Yorgey 23 Jul '12

23 Jul '12

Hello all, Thanks for the great feedback so far on the split package. I have updated the wiki page with the results of the discussion so far: http://trac.haskell.org/haskell-platform/wiki/Proposals/split In particular, I have made the following changes to the package as a result of the feedback: * Removed the GADTs extension; the package is now fully Haskell 2010. * Marked synonyms as deprecated, and excluded them from the Haddock output. Thus new users will not be confused by the synonyms anymore, and existing users will be notified that they are now deprecated, but existing code will not break since the synonyms are still exported from the package. * Many other minor cleanups and improvements to documentation etc. More details are on the wiki page. These changes are in the darcs repository but I have not released a new version to Hackage yet. * I am also looking into the possibility of using conditionals in the .cabal file to support both GHC and other compilers, by using GHC's primitive 'build' function only when GHC is the compiler, and otherwise using a generic one. More feedback on this is appreciated. Is it worth the effort/complication? Please continue responding to this thread (or the previous one) with additional feedback, upvotes, downvotes, etc. -Brent

1 0

Re: safe vs. unsafe (Was: Haskell Platform proposal: Add the vector package)
by Simon Marlow 20 Jul '12

20 Jul '12

On 13/07/12 21:18, Heinrich Apfelmus wrote: > Simon Marlow wrote: >> Hi Thomas, >> >> All these questions are answered by the Haskell Symposium paper, which >> we'll post very shortly. FYI, the FFI is mostly safe, as long as you >> declare foreign imports to have an IO result type (otherwise it's >> unsafePerformIO, and hence unsafe). Unsafety is not viral: as soon as >> you have a safe API, you can declare its implementation to be >> Trustworthy, and then it is usable from safe code. > > How strict are the requirements for Trustworthy code? For instance, my > reactive-banana library uses observable sharing, which is inherently > Unsafe. Of course, I think that my library is still Safe, but I have no > formal proof of this "fact". I have two options: > > 1. Mark my library as Trustworthy even though I don't have sufficient > proof. This severely weakens the guarantees of Safe Haskell. > 2. Mark my library as Unsafe. But then people can't use it to write Safe > code and will complain. > > The trouble is that I have a strong incentive to solve the problem > arising from 2 by doing 1. Oops. The idea is that you do (1). All your clients get to use Safe, and nobody is obliged to use your code in a security-critical setting unless they want to. (I could write a lot more, but I've written too much about this already today. Good night!) Cheers, Simon

6 8

Proposal: add an order-reversing newtype to Data.Ord
by ARJANEN Loïc Jean David 18 Jul '12

18 Jul '12

Hello all, I recently noticed that despite conversations about that in this mailing-list, there isn't an order-reversing newtype in Data.Ord. That newtype would be quite useful, e.g. for reverse-sorting a list or a set, so I propose we add a newtype defined thusly: newtype Reverse a = Reverse { fromReverse :: a } deriving (Eq) instance Ord a => Ord (Reverse a) where compare (Reverse x) (Reverse y) = compare y x I took the implementation from the Down newtype in GHC.Exts, so we could perhaps just re-export it. This will cause breakage to code already defining a type named Reverse, so I don't know if the damage will be important. Of course, the name and definition are open to discussion. Deadline: 12 July 2012. P.S. : A conversation about that took place here: http://haskell.1045720.n5.nabble.com/A-Down-newtype-in-Data-Ord-td5005373.h… -- ARJANEN Loïc Jean David http://blog.luigiscorner.com --- "Computer science is no more about computers than astronomy is about telescopes, biology is about microscopes, or chemistry is about beakers and test tubes. Science is not about tools. It is about how we use them, and what we find out when we do." Michael R. Fellows and Ian Parberry

9 12

Re: safe vs. unsafe (Was: Haskell Platform proposal: Add the vector package)
by John Lato 16 Jul '12

16 Jul '12

> On Sat, Jul 14, 2012 at 3:16 AM, Henning Thielemann < > lemming(a)henning-thielemann.de> wrote: > >> On Fri, 13 Jul 2012, Brandon Allbery wrote: >> >> And now I'm having a "so what's the point?" moment? All this effort so >>> we can just mark random stuff as >>> Trusted anyway? >>> >> >> Today we have 'unsafePerformIO'. So if we praise the merits of Haskell's >> strong type system and then mention 'unsafePerformIO' the audience will ask >> "so what's the point of type safety then?" Well, the point is that >> unsafePerformIO is strongly discouraged and every use of it should be >> considered carefully. >> > > We've just been told *not* to consider carefully for purposes of marking a > module as Trustworthy; an argument based on considering carefully is not > relevant. I think the idea here is that, as a package author, it's okay to just throw Trustworthy anywhere ghc can't infer Safe on its own. As a package user, if you care about Safe Haskell, it's your responsibility to audit/consider carefully to determine if Trustworthy code is something you're willing to include in your codebase. John L.

3 3

System.Posix.IO.ByteString types?
by Ben Gamari 11 Jul '12

11 Jul '12

Recently, I spent a fair amount of time tracking down an encoding issue[1] in the `serialport` package. As is often the case, `serialport` used Strings, which blew up quite nicely when working with a binary protocol. Delving into the code it eventually became fairly obvious that the problem was due to encoding and could be fixed by completely moving to ByteStrings. Unfortunately, while the unix package contains a System.Posix.IO.ByteString module, all of the functions within still appear to work with Strings[2]. While it appears that paths are handled a bit differently in the ByteString variant, but it seems like this is a fairly small consideration compared to the data itself. Have I stumbled across a bug? Is there anyway short of the non-Haskell Platform unix-bytestring package to get ByteStrings out of fds? If not, it seems this is a large hole in the interfaces exposed by unix. Is there any plan to remedy this? Cheers, - Ben [1] https://github.com/jputcu/serialport/issues/12 [2] http://hackage.haskell.org/packages/archive/unix/2.5.1.1/doc/html/System-Po…

4 3

ANN: unification-fd 0.8.0
by wren ng thornton 11 Jul '12

11 Jul '12

-------------------------------------------- -- unification-fd 0.8.0 -------------------------------------------- The unification-fd package offers generic functions for single-sorted first-order structural unification (think of programming in Prolog, or of the metavariables in type inference)[1][2]. The library *is* sufficient for implementing higher-rank type systems a la [Peyton Jones, Vytiniotis, Weirich, Shields], but bear in mind that unification variables are the metavariables of type inference--- not the type-variables. As of this version, the library is also sufficient for implementing (non-recursive) feature structure unification. An effort has been made to make the package as portable as possible. However, because it uses the ST monad and the mtl-2 package it can't be H98 nor H2010. However, it only uses the following common extensions which should be well supported[3]: Rank2Types MultiParamTypeClasses FunctionalDependencies -- Alas, necessary for type inference FlexibleContexts -- Necessary for practical use of MPTCs FlexibleInstances -- Necessary for practical use of MPTCs UndecidableInstances -- For Show instances due to two-level types -------------------------------------------- -- Changes (since 0.7.0) -------------------------------------------- This release is another API breaking release, though hopefully minor. In particular, the type of the zipMatch method for Unifiable has changed from: zipMatch :: t a -> t b -> Maybe (t (a, b)) to: zipMatch :: t a -> t a -> Maybe (t (Either a (a, a))) With the new type each of the unification subproblems can be declared as fully resolved (Left xy) or as still pending solution (Right (x,y))--- whereas the previous type only allowed the latter. This extension is necessary for implementing unification of feature structures (e.g., t ~ Map k). Given two feature structures which do not fully overlap, we can now declare that the non-intersecting parts have been unified and only require further unification for the parts which intersect--- whereas previously we would've been forced to declare the non-intersecting parts as requiring unification with themselves, which will always succeed and introduces extra work. This feature is one I had available in earlier unpublished versions of the code, but errantly removed it when simplifying things for publishing on Hackage. To fix extant Unifiable instances, just wrap each tuple with Right. For those who care about such things, I have not been able to discern any noticeable difference in performance between the two versions. If you can provide benchmarks demonstrating otherwise, I'd be pleased to look at them. In addition, the Show instance for Fix has been adjusted to use showsPrec in lieu of show, correcting some infelicities with the output. -------------------------------------------- -- Description -------------------------------------------- The unification API is generic in the type of the structures being unified and in the implementation of unification variables, following the two-level types pearl of Sheard (2001). This style mixes well with Swierstra (2008), though an implementation of the latter is not included in this package. That is, all you have to do is define the functor whose fixed-point is the recursive type you're interested in: -- The non-recursive structure of terms data S a = ... -- The recursive term type type Term = Fix S And then provide an instance for Unifiable, where zipMatch performs one level of equality testing for terms and returns the one-level spine filled with pairs of subterms to be recursively checked, or Nothing if this level doesn't match. Each subterm can be separately marked as being resolved, Left xy, or as requiring further unification, Right(x,y). class (Traversable t) => Unifiable t where zipMatch :: t a -> t a -> Maybe (t (Either a (a, a))) The choice of which variable implementation to use is defined by similarly simple classes Variable and BindingMonad. We store the variable bindings in a monad, for obvious reasons. In case it's not obvious, see Dijkstra et al. (2008) for benchmarks demonstrating the cost of naively applying bindings eagerly. There are currently two implementations of variables provided: one based on STRefs, and another based on a state monad carrying an IntMap. The former has the benefit of O(1) access time, but the latter is plenty fast and has the benefit of supporting backtracking. Backtracking itself is provided by the logict package and is described in Kiselyov et al. (2005). In addition to this modularity, unification-fd implements a number of optimizations over the algorithm presented in Sheard (2001)--- which is also the algorithm presented in Cardelli (1987). * Their implementation uses path compression, which we retain. Though we modify the compression algorithm in order to make sharing observable. * In addition, we perform aggressive opportunistic observable sharing, a potentially novel method of introducing even more sharing than is provided by the monadic bindings. Basically, we make it so that we can use the observable sharing provided by the modified path compression as much as possible (without introducing any new variables). * And we remove the notoriously expensive occurs-check, replacing it with visited-sets (which detect cyclic terms more lazily and without the asymptotic overhead of the occurs-check). A variant of unification which retains the occurs-check is also provided, in case you really need to fail fast. * Finally, a highly experimental branch of the API performs *weighted* path compression, which is asymptotically optimal. Unfortunately, the current implementation is quite a bit uglier than the unweighted version, and I haven't had a chance to perform benchmarks to see how the constant factors compare. Hence moving it to an experimental branch. These optimizations pass a test suite for detecting obvious errors. If you find any bugs, do be sure to let me know. Also, if you happen to have a test suite or benchmark suite for unification on hand, I'd love to get a copy. -------------------------------------------- -- Notes and limitations -------------------------------------------- [1] At present the library does not appear amenable for implementing higher-rank unification itself; i.e., for higher-ranked metavariables, or higher-ranked logic programming. To be fully general we'd have to abstract over which structural positions are co/contravariant, whether the unification variables should be predicative or impredicative, as well as the isomorphisms of moving quantifiers around. It's on my todo list, but it's certainly non-trivial. If you have any suggestions, feel free to contact me. [2] At present it is only suitable for single-sorted (aka untyped) unification, a la Prolog. In the future I aim to support multi-sorted (aka typed) unification, however doing so is complicated by the fact that it can lead to the loss of MGUs; so it will likely be offered as an alternative to the single-sorted variant, similar to how the weighted path-compression is currently offered as an alternative. [3] With the exception of fundeps which are notoriously difficult to implement. However, they are supported by Hugs and GHC 6.6, so I don't feel bad about requiring them. Once the API stabilizes a bit more I plan to release a unification-tf package which uses type families instead, for those who feel type families are easier to implement or use. There have been a couple requests for unification-tf, so I've bumped it up on my todo list. -------------------------------------------- -- References -------------------------------------------- Luca Cardelli (1987) /Basic polymorphic typechecking/. Science of Computer Programming, 8(2):147--172. Atze Dijkstra, Arie Middelkoop, S. Doaitse Swierstra (2008) /Efficient Functional Unification and Substitution/, Technical Report UU-CS-2008-027, Utrecht University. <http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-027.pdf> Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark Shields /Practical type inference for arbitrary-rank types/, to appear in the Journal of Functional Programming. (Draft of 31 July 2007.) Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry (2005) /Backtracking, Interleaving, and/ /Terminating Monad Transformers/, ICFP. <http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf> Tim Sheard (2001) /Generic Unification via Two-Level Types/ /and Paramterized Modules/, Functional Pearl, ICFP. <http://web.cecs.pdx.edu/~sheard/papers/generic.ps> Tim Sheard & Emir Pasalic (2004) /Two-Level Types and/ /Parameterized Modules/. JFP 14(5): 547--587. This is an expanded version of Sheard (2001) with new examples. <http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps> Wouter Swierstra (2008) /Data types a la carte/, Functional Pearl. JFP 18: 423--436. <http://www.cs.ru.nl/~wouters/Publications/DataTypesALaCarte.pdf> -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/unification-fd Darcs: http://community.haskell.org/~wren/unification-fd Haddock (Darcs version): http://community.haskell.org/~wren/unification-fd/dist/doc/html/unification… -- Live well, ~wren

1 0

Proposal: Control.Concurrent.Async
by Simon Marlow 10 Jul '12

10 Jul '12

I'd like to add a higher-level concurrency API to the base package. This API has grown while I've been working on examples for my book, and I'm convinced that we should have something like this in the standard libraries. Here's the API I propose: http://community.haskell.org/~simonmar/async-stm/Control-Concurrent-Async.h… In fact it already exists in at least two packages on Hackage: 'async' and 'threads'. My version is a superset of both of these, except for a few small differences (which are up for discussion, of course). One good reason to have this package is that it avoids some common pitfalls, such as forgetting to handle exceptions in your child threads. In the Async API, you get to choose whether to (a) receive the result as 'Either SomeException a', or (b) have the exception re-thrown in the waiting thread. You don't get to ignore it altogether. Another common pitfall avoided by this library is accidentally leaving threads running in the background. This is handled by withAsync: withAsync :: IO a -> (Async a -> IO b) -> IO b the child thread is always cancelled (i.e. killed) when the second argument returns or throws an exception, if it hasn't finished already. I'm opening this up for discussion so that we can tidy up any inconsistent details and add any functions that people feel are missing. Naming is obviously up for discussion too. Cheers, Simon

18 48