- Libraries - Haskell.org

Proposal: Add an analogue of $! to deepseq
by Ivan Lazar Miljenovic 14 Jul '11

14 Jul '11

I propose we add a operator - tentatively labelled $!! (and which Hayoo reports isn't currently exported by a Hackage package) - as a deepseq analogue $! to the deepseq library: ($!!) :: (NFData a) => (a -> b) ->a -> b f $!! x = x `deepseq` f x infixr 0 $!! As a sub-proposal, I also propose that we add a "force" function (the name of which also seems to be unused) to make it easier to test forcing of values: force :: (NFData a) => a -> a force x = x `deepseq` x Discussion time: 2 weeks -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

6 7

Changes to Data.Typeable
by Simon Marlow 14 Jul '11

14 Jul '11

Hi folks, In response to this ticket: http://hackage.haskell.org/trac/ghc/ticket/5275 I'm making some changes to Data.Typeable, some of which affect the API, so as per the new library guidelines I'm informing the list. The current implementation of Typeable is based on mkTyCon :: String -> TyCon which internally keeps a table mapping Strings to Ints, so that each TyCon can be given a unique Int for fast comparison. This means the String has to be unique across all types in the program. Currently derived instances of typeable use the qualified original name (e.g. "GHC.Types.Int") which is not necessarily unique, is non-portable, and exposes implementation details. The String passed to mkTyCon is returned by tyConString :: TyCon -> String which lets the user get at this non-portable representation (also the Show instance returns this String). So the new proposal is to store three Strings in TyCon. The internal representation is this: data TyCon = TyCon { tyConHash :: {-# UNPACK #-} !Fingerprint, tyConPackage :: String, tyConModule :: String, tyConName :: String } the fields of this type are not exposed externally. Together the three fields tyConPackage, tyConModule and tyConName uniquely identify a TyCon, and the Fingerprint is a hash of the concatenation of these three Strings (so no more internal cache to map strings to unique Ids). tyConString now returns the value of tyConName only. I've measured the performance impact of this change, and as far as I can tell performance is uniformly better. This should improve things for SYB in particular. Also, the size of the code generated for deriving Typeable is less than half as much as before. === Proposed API changes === 1. DEPRECATE mkTyCon mkTyCon is used by some hand-written instances of Typeable. It will work as before, but is deprecated in favour of... 2. Add mkTyCon3 :: String -> String -> String -> TyCon which takes the package, module, and name of the TyCon respectively. Most users can just derive Typeable, there's no need to use mkTyCon3. In due course we can rename mkTyCon3 back to mkTyCon. Any comments? Cheers, Simon

4 11

Proposal: IntMap.differenceKeysSet for removing an IntSet of keys
by Liyang HU 13 Jul '11

13 Jul '11

Ticket: http://hackage.haskell.org/trac/ghc/ticket/5242 Currently, IntMap.difference ma mb removes all the keys in mb from ma, where the elements of the two IntMaps can be of different types; the elements of mb are not used. There is no efficient way to remove an IntSet of keys, however. These patches adds the IntMap.differenceKeysSet function—essentially a copy/paste of difference—that satisfies the following property: prop_DiffKeysSet :: Map Int -> Map () -> Bool prop_DiffKeysSet t1 t2 = difference t1 t2 == differenceKeysSet t1 (keysSet t2) Cons: Not so happy with the name. Code bloat. Thanks, /Liyang

5 11

Proposal for deepseq: Data.Sequence.Seq instance for NFData
by Alexey Karakulov 12 Jul '11

12 Jul '11

My proposal is qiute straightforward. The patch is attached and it's essence is in these lines: > instance NFData a => NFData (Data.Sequence.Seq a) where > rnf = rnf . Foldable.toList [Discussion part] I choosed toList method to keep the code style, but I'm not sure it's efficient to create cons'es when we could just fold: > rnfFoldable :: (NFData a, Foldable f) => f a -> () > rnfFoldable = Foldable.foldMap rnf Or it's better to do this with foldl (while not so nice at is was with using () as monoid): > rnfFoldable = Foldable.foldl (const rnf) () There was a proposal to add strict folds to Foldable type class, so we can use foldl' there. My proposal is to add the instance in either way.

1 1

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

12 Jul '11

-------------------------------------------- -- unification-fd 0.5.0 -------------------------------------------- The unification-fd package offers generic functions for first-order structural unification (think Prolog programming or Hindley--Milner type inference). I've had this laying around for a few years, so I figured I might as well publish it. An effort has been made to try to make this 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[1]: Rank2Types MultiParamTypeClasses FunctionalDependencies FlexibleContexts FlexibleInstances UndecidableInstances [1] 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 it. 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. -------------------------------------------- -- 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 PureTerm = 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). class (Traversable t) => Unifiable t where zipMatch :: t a -> t b -> Maybe (t (a,b)) 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 previous optimization 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 for some reason. * 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. I haven't had a chance to fully debug these optimizations, though they pass some of the obvious tests. 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. -------------------------------------------- -- 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> 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

Re: Proposal for template-haskell: Make Q an instance of Applicative
by wren ng thornton 09 Jul '11

09 Jul '11

On 7/8/11 5:56 AM, Bas van Dijk wrote: > Hello, > > The Q type: > > newtype Q a = Q { unQ :: forall m. Quasi m => m a } > > currently has an instance for Monad and Functor. I would like to > propose adding an instance for Applicative as well. Note that this > also means that the Quasi class needs to get an Applicative > superclass: > > class (Monad m, Applicative m, Functor m) => Quasi m where ... > > Discussion period: 2 weeks. +1 for the march to Applicative. -- Live well, ~wren

1 0

unsafeLocalState = unsafeDupablePerformIO?
by Simon Marlow 08 Jul '11

08 Jul '11

We currently have Foreign.Marshal.Unsafe.unsafeLocalState :: IO a -> a unsafeLocalState = unsafePerformIO however, unsafePerformIO in GHC is rather expensive, because it tries to avoid the IO being executed more than once when there are multiple processors. However, for the cases that we claim unsafeLocalState is to be used for, it would be safe to use the cheaper unsafeDupablePerformIO instead. The only way to get at unsafeDupablePerformIO currently is from GHC.IO, this would give users a legitimate way to get at a cheaper unsafePerformIO. Or perhaps we should just export unsafeDupablePerformIO from System.IO.Unsafe? Thoughts? Cheers, Simon

2 2

Re: PROPOSAL: add tryFdSeek to unix
by wren ng thornton 30 Jun '11

30 Jun '11

On 6/29/11 3:18 PM, Simon Marlow wrote: > I think it would make sense to refactor the unix package into a very > thin "just the foreign imports" layer, and then the current unix as a > layer on top of that. Now that you mention it, I think that'd actually be really nice. On the one hand, a lot of unix is just hsc2hs code for accessing C-bits; on the other hand, a lot of unix is the various wrappers to provide a more Haskell-like interface to C. Speaking technically, the former is the hard part since it involves dealing with cross-platform and other compatibility issues. Though the latter is clearly more challenging as an aesthetic/ergonomic problem; which are too often overlooked in programming. It's very sensible to handle the different problems in different packages. > It doesn't make a great deal of sense to do this for just one function, > though. It would stick out like a sore thumb in the API. True. FWIW, the String-based API in System.Posix.IO already exposes some relatively raw wrappers to C. But even System.Posix.IO is just one module, which would still stick out considering how many modules unix has. -- Live well, ~wren

1 0

Re: PROPOSAL: add tryFdSeek to unix
by John Lato 29 Jun '11

29 Jun '11

> > I'd like to propose adding a variant of fdSeek which returns errors > > directly instead of throwing an exception. > > > > Why wouldn't you just wrap it in Control.Exception.try instead? And what's > so special about seeking that suggests that it needs an alternate entry > point? > (Disclosure: I'm one of the people who requested this originally) Wrapping a function like `fdSeek` in a `try` to get a non-exception variant is wasteful. Exceptions are a Haskell layer on top of the more fundamental library call, and people who want access to that call directly shouldn't have to unwrap extra cruft to do so. Nor should they have to re-implement basic functionality because the library doesn't expose it. fdSeek just happens to be a current need of mine. I would hope that this approach would be adopted across the board. > > (In other words, I'm opposed to this proposal.) > I'm opposed to exceptions, but there's no way to avoid them because the library doesn't expose a direct interface. John

4 4

Error in documentation for Control.Exception (base-4.*)
by Ivan Lazar Miljenovic 29 Jun '11

29 Jun '11

This was caught by mbuf on #haskell: the example for the Exception class in Control.Exception as of base-4 needs some extra escaping for Haddock markup. It currently has: @ *Main> throw ThisException `catch` \e -> putStrLn (\"Caught \" ++ show (e :: MyException)) Caught ThisException @ It should be (untested; I'm not sure of the backticks but I think it'll work): @ *Main> throw ThisException \`catch\` \\e -> putStrLn (\"Caught \" ++ show (e :: MyException)) Caught ThisException @ It may even be better to use the new support for examples in Haddock (section 3.8.5 of http://www.haskell.org/haddock/doc/html/ch03s08.html ): @ >>> throw ThisException \`catch\` \\e -> putStrLn (\"Caught \" ++ show (e :: MyException)) Caught ThisException @ -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

2 1