- Libraries - Haskell.org

A Random Strawman
by Dominic Steinitz 06 Apr '15

06 Apr '15

Hello All, Having skimmed the literature, run some tests and benchmarks: The current System.Random is broken: https://github.com/haskell/random/issues/25#issuecomment-87423142. Furthermore, this is recorded in at least two published papers: http://dl.acm.org/citation.cfm?id=2660195 and http://publications.lib.chalmers.se/records/fulltext/183348/local_183348.pdf. The tf-random package does not have this breakage and is based on good theoretical foundations. In my tests tf-random performs better than System.Random. As a result of which, I am very much inclined to suggest we replace the code in System.Random with tf-random. Before doing any more work on this, I’d like to understand what the next steps should be. How much review should be carried out? I have no reason to doubt the implementors have done a great job but should someone (who?) review the code more formally. If so what would the process / tools be? Tests in packages / applications may now fail as the (pseudo) random numbers will be different with this change. What should we do here? Alert folks (who and how?) that the may have to rebase their tests? Tell folks that 1.1 is deprecated and they should move to 2.0 (I think it’s right to indicate this is a completely new version)? Are there any other steps? FYI: I did look at Guy Steele et al. but I don’t believe there is currently a Haskell implementation of it, probably ruling it out as possible solution in the medium term. Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com

3 3

Stable location for monomorphic foldr?
by Joachim Breitner 02 Apr '15

02 Apr '15

Hi, I just stumbled over a FTP breakage: A RULES with "foldr" on the left hand side would no longer fire, because it would refer to Foldable.foldr, and not the monomorphic foldr. Adding #if MIN_VERSION_base(4,8,0) import Prelude hiding (foldr) import GHC.OldList (foldr) #endif to the file solved the problem for now, but GHC.OldList is supposed to go away eventually, so I believe we need a permanent location for the monomorphic foldr. Or will we simply not get rid of GHC.OldList at all? (One could argue that "foldr" on the left-hand-side of a RULE should work and that this is a GHC bug, though.) Greetings, Joachim -- Joachim “nomeata” Breitner mail(a)joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata(a)joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata(a)debian.org

2 2

An Easy Solution to PVP Bounds and Cabal Hell
by Gershom B 01 Apr '15

01 Apr '15

Recently there has been some discussion about how we can fix the problem of “Cabal Hell”. Some people advocate restrictive upper bounds, to prevent packages from being broken by new updates. Some other people point out that too-restrictive bounds can lead to bad install plans, since some packages might want newer versions of some dependencies, and others older versions. Still other people say that we can _retroactively_ fix upper bounds (in either direction) by modifying cabal files using the new features in Hackage. Some people think this is a terrible idea because it looks like we are mutating things, and this confuses hashes. In turn, these people support either nix or a nix-like approach by which packages have hashes that encompass the full versions of all their transitive dependencies. With that in hand, we can cache builds and mix-and-match to build the precise environment we want for each package while reducing redundant computation. However, the cache of all the various binary combinations may still grow large! And none of this fully begins to address the dreaded “diamond dependency” problem. Here is a chart of some such solutions: http://www.well-typed.com/blog/aux/images/cabal-hell/cabal-hell-solutions.p… One way to look at a particular build is in an n-dimensional state space (of the Hilbert sort) determined by all its dependencies, not least the compiler itself. The solver acts as a particle traversing this space. But this description is too simple. Our state of dependencies and constraints itself varies and grows over time. So another approach is to think of the dependencies as a transitive graph, where each node may vary along a time axis, and as they slide along the axis, this in turn affects their children. We now have not just one Hilbert space, but a collection of them related by branching trees as authors locally modify the dependencies of their packages. If we keep this simple model in mind, it is easy to see why everyone is always having these debates. Some people want to fix the graph, and others want to simplify it. Some people want an immutable store, and some people want to rebase. But we can’t “really” rebase in our current model. Bearing in mind our model of a space-time continuum of hackage dependences, the solution emerges — enforce immutability, but allow retroactive mutation. For instance, suppose Fred tries to install package Foo on Friday evening, but discovers that it depends on version 1.0 of Bar (released the previous Friday) that in turn depends on version 0.5 of Baz but Foo also depends on version 0.8 of Baz. So Fred branches Bar and changes the dependency, which in turn informs Betty, that there is also a 1.0 of Bar with different dependencies and we have forked our package timeline. On getting this message on Monday, Betty can merge by pushing with --force-rewrites and this goes back in the timeline and makes it so that Baz retroactively had the right dependencies and now Fred, as of the previous Friday, no longer has this problem. (That way he still has the weekend). Now the failed build is cut off temporarily into a cycle in the package timeline that is disconnected from the rewrite. We stash it with “hackage stash” until Monday at which time the dependency graph is 100 percent equalized and primed for new patches. At this point we unstash Foo as of Friday and it is replaced by the Foo from the new timeline. Friday Fred needs to remain stashed lest he run into himself. The longer he can be avoided by his Monday self the better. Future work could include bots which automate pruning of artifacts from redundant branches. If this description was too abrupt, here is a diagram with a fuller description of the workflow: http://bit.ly/15IIGac I know there are some new ideas to take in here, and there is a little technical work necessary to make it feasible, but in my opinion if you can understand the current cabal situation, and you can understand how git and darcs work, then you should be able to understand this too. Hopefully by this time next year, we’ll be able to say that our problems with cabal have been truly wiped from our collective memory. HTH, HAND. Gershom

3 2

Re: traverse_
by Fumiaki Kinoshita 31 Mar '15

31 Mar '15

> Hi, > I have just installed GHC 7.10.1. I'm a little bit surprised because > 'traverse_' is not exported from Prelude. But 'traverse' is exported. > Is this intentional? > I expected that I can forget xxxM, xxxM_, xxxA, and xxxA_ functions > with GHC 7.10.1. I want to use 'traverse_' instead of 'mapM_'. > --Kazu I found out that (<>) (in Data.Monoid) is missing, also. It would be nice to reexamine Prelude to export things we want to export.

6 13

Hackage trustee proposal: Curating the Hackage package collection
by Adam Bergmark 31 Mar '15

31 Mar '15

Dear Haskell Community, For some time Hackage has contained a user group called "Trustees", http://hackage.haskell.org/packages/trustees/ . Description: The role of trustees is to help to curate the whole package collection. Trustees have a limited ability to edit package information, for the entire package database (as opposed to package maintainers who have full control over individual packages). Trustees can edit .cabal files, edit other package metadata and upload documentation but they cannot upload new package versions." In short, making sure that packages keep building and filling the gap between unreachable maintainers and package take-overs. Up until now we have been very careful with changes since we haven't had a defined process. Spurred by SPJ and others we have been working on a proposal for how we should operate. You can find the proposal here: https://gist.github.com/bergmark/76cafefb300546e9b90e We would now like your feedback! Some specific things from the proposal that we'd like your opinion on: * Section 1: No opt-out for restricting bounds * Section 2: Opt-out rather than opt-in procedure for loosening version constraints * Section 2: Do you care whether you are notified before or after a version constraint is loosened? * Section 3: The time frame for publishing simple source changes * Section 3: What exactly should constitute a "simple source change" We also have a github repository where YOU can file issues about broken packages, you can start doing this right now! https://github.com/haskell-infra/hackage-trustees/ Please share this with as many people as possible. We are looking forward to hear your thoughts! Sincerely, Adam Bergmark

2 1

Library_submissions and Call for Maintainers
by Edward Kmett 30 Mar '15

30 Mar '15

We've had a lot of feedback over the last few months trying to get clarification on the role of the core libraries committee, and on the libraries@ process in general. In particular, Simon Peyton Jones asked us in his own rather inimitable manner to make sure that we sat down and started documenting things. After all, we've now been at this for almost a year and a half, and have started to figure out what is working and what isn't. In response to that feedback, we've recently taken the time to go through and update the Library_submissions <https://wiki.haskell.org/Library_submissions> page rather extensively to better describe and refine the libraries@ process and better define the role of the core libraries committee. Changes of note: * Up until now we've been using the rather ad hoc definition of "core libraries" as libraries that come with the Haskell Platform and which are subject to the libraries@ proposal process. We've recently taken it upon ourselves to clarify this further. To that end we've updated the Library_submissions <https://wiki.haskell.org/Library_submissions> page with a detailed summary of what libraries are considered "core" and why. * It was brought to our attention that figuring out even where to file a bug report or feature request for a given library was a tricky concern. To that end we've added information on how to find the appropriate issue tracker to the form. Communication: There are two forms of potential communication breakdowns that we'd like to address. We're still working on figuring out a more effective way to communicate what changes are happening in the background out to the community, lest we wind up with another situation like the Foldable/Traversable Proposal, where it caught an appreciable segment of the community unaware. We've started at least tracking issues that impact modules defined in the Haskell report in GHC trac with "report-impact", but we still have a lot more to do on this front. We have also been asked to help clarify what happens to a proposal once it leaves the libraries@ mailing list, assuming that the proposal is accepted by the maintainer. The issue was raised that it wasn't clear when an issue had been dropped on the floor, and who has responsibility to carry it forward at each stage along the way. To that end, we've posted some basic responsiveness guidelines <https://wiki.haskell.org/Library_submissions#Responsiveness> to help. We're not looking for a way to hold someone's feet to the fire, but merely for a way to keep proposals from getting stuck in limbo as they transition out of the libraries mailing list and into the hands of the maintainers. Maintainership: In an effort to maintain a greater level of throughput on issues that come along, we're trying to increase the number of projects that have active maintainers. Some of these aren't necessarily core libraries, but they are libraries that have been handed to the core libraries committee for maintenance. A couple of weeks back we sought out an active maintainer for the directory package, as it had accumulated several months worth of backlogged tickets, most of which just needed a clear head to make an informed decision about how to proceed. Phil Ruffwind and Elliot Robinson stepped up to fill this gap, and have been making a rather exciting amount of headway in clearing out the issue backlog, while managing to give those issues the consideration they are due. Emboldened by this success, we have a few other packages with which we'd like to do the same: * random We've had some truly excellent work done over the last couple of years on how to deal with "splitting" a random number generator in a cryptographically sound manner. I spent some time cleaning up a few outstanding issues for this package personally over the summer, but have not had nearly enough time to devote to the issue of how to integrate the outcome of the recent research on splitting, while simultaneously caring about performance and soundness. * unix We've had a number of issues accrete over time, particularly issues that have to do with portability to lesser used platforms such as OpenBSD. We've also had a lot of cooks in the kitchen, so the documentation style for this library is all over the place. We could use a solid maintainer for this package who is deeply familiar with unix internals, and who, preferably would like to deal with bringing some order to these cross platform concerns. * Win32 None of us on the current core libraries committee are *particularly* well versed in current windows issues. We have a new "windows task force" as well. Would the task force -- or someone involved or who would like to be involved in it -- be willing to pick this up and carry the torch? * old-time, old-locale, haskell98 and haskell2010 The old-time and old-locale libraries are primarily maintained because their contents are mentioned in the Haskell Report, which is/was (mostly) implemented in the haskell98 and haskell2010 packages. Three months ago, we determined to stop shipping these as boot libraries with the GHC as a consequence of the Applicative-Monad Proposal. (Issue #9590 <https://ghc.haskell.org/trac/ghc/ticket/9590>) While Herbert Valerio Riedel recently started working on a "fully compliant" version of the Haskell 2010 report, there is a reasonably large design surface in that area, balancing between perfect compatibility and pragmatic compatibility with other libraries. These libraries could use a more active official maintainer. Thank you for your time. Please do not hesitate to contact me (or reply) with questions, concerns, or thoughts. -Edward Kmett

10 17

Hidden Markov Models
by Dominic Steinitz 30 Mar '15

30 Mar '15

> I am currently working on > http://hub.darcs.net/thielema/hmm-hmatrix > > It does not need log-numbers because it normalizes all temporary results. > This way I can use fast hmatrix operations. Would normalization also be a > solution for other probabilistic models? I assume these are models with finite state spaces? FYI I uploaded a Kalman filter https://github.com/idontgetoutmuch/Kalman which is also a HMM. I feel we should be able to abstract over the Markov transition kernel to describe the model without caring whether the state space is continuous or discrete but that it is about as much thinking I have done on the subject. Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com

1 0

Platform 2015.2.0.0 Alpha 2 for debian based systems
by Mark Lentczner 29 Mar '15

29 Mar '15

I've uploaded a build of *Haskell Platform 2015.2.0.0 Alpha 2* for generic debian linux systems. It includes GHC 7.10.2, using the generic linux bindist. This is a tarball, not a package. Installation instructions: cd / sudo tar xvf ...downloaded-tarfile... sudo /usr/local/haskell/ghc-7.10.1-x86-64/bin/activate-hs Notes: - Built on Ubuntu 14.04LTS - Needs the following packages installed: build-essential libbsd-dev libgmp-dev libtinfo-dev zlib1g-dev - The OpenGL packages need the OpenGL libs, which on a non-GUI system like a server can be gotten by installing: freeglut3-dev libgl1-mesa-dev libglu1-mesa-dev - Mark

1 1

ANN: unification-fd 0.10.0
by wren romano 29 Mar '15

29 Mar '15

-------------------------------------------- -- unification-fd 0.10.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.8.0 (2012-07-11) -------------------------------------------- * (0.8.1) Added Functor, Foldable, and Traversable instances for COntrol.Unification.Types.UnificationFailure. Thanks Graham Rogers. * (0.9.0) Changed the fundeps on BindingMonad and RankedBindingMonad so that things compule under GHC 7.8.2 * (0.9.0) eta-expanded the rewrite rules in Data.Functor.Fixedpoint so that GHC 7.8 no longer gives warnings about not firing due to (.) possibly being inlined first * Cleaned things up to compile cleanly for GHC 7.10 * For EitherK and MaybeK, liberalized the instances to only require Applicative instead of Monad wherever possible. * Completely revamped the old UnificationFailure data type as the new UFailure data type and Fallible type class. This was necessary to clean up some deprecation warnings about using Control.Monad.Error, to remove the hack of needing an UnknownError constructor, and to make the data type for representing failures more extensible. -------------------------------------------- -- 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

ANN: stm-chans 3.0.0.3
by wren romano 29 Mar '15

29 Mar '15

-------------------------------------------- -- stm-chans 3.0.0.3 -------------------------------------------- The stm-chans package offers a collection of channel types, similar to Control.Concurrent.STM.{TChan,TQueue} but with additional features. -------------------------------------------- -- Changes since 3.0.0 (2013-05-29) -------------------------------------------- Cleaned up the header gunk to compile cleanly under GHC 7.10. No actual code has been altered. -------------------------------------------- -- Long description -------------------------------------------- In particular stm-chans offers the following data types: * Control.Concurrent.STM.TBChan: Bounded FIFO channels. When the channel is full, writers will block/retry. This ensures that the writers do not get too far ahead of the readers, which helps to make sure that memory and cpu resources are used responsibly. * Control.Concurrent.STM.TMChan: Closeable FIFO channels. * Control.Concurrent.STM.TMQueue: Closeable FIFO queues. Like TChan (Maybe a) but with a monotonicity guarantee that once Nothing is returned all future reads will be Nothing as well. * Control.Concurrent.STM.TBMChan: Bounded Closeable FIFO channels. * Control.Concurrent.STM.TBMQueue: Bounded Closeable FIFO queues. Combines the capabilities of TBChan and TMChan. -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/stm-chans Darcs: http://community.haskell.org/~wren/stm-chans Haddock (Darcs version): http://community.haskell.org/~wren/stm-chans/dist/doc/html/stm-chans -- Live well, ~wren

1 0