- Libraries - Haskell.org

Re: new Library Infrastructure spec.
by S. Alexander Jacobson 08 Jun '04

08 Jun '04

Isaac, > I don't think the "runhugs" bit is a requirement. You can execute the > setup script however you like. Any reason we can't simplify Joe's interface to: ghc --install http://url/of/some.pkg --or-- hugs --install /path/to/some.pkg Where some.pkg is some combination of tarball and setup specification. The install system of the compiler/interpreter would retrieve some.pkg from the specified location, and use the setup spec to compile it and put it in the appropriate locations such that Joe can use it from his Haskell program or perhaps invoke it as an executable in whatever manner is appropriate to his local OS (mouse-click or command-line). The open question is what this setup specification should look like. There is an obvious tradeoff between the interests of Joe and Angela on the one hand and Marcus on the other. Marcus creates packages that require some combination of GCC and Perl and perhaps some random Perl libs from CPAN to build. There is really no way to make installation of systems he creates simple and generic. My feeling is that we shouldn't even bother to try. Marcus and Sam both know enough to communicate effectively to make it happen and neither of them is going to be happy trusting some generic install script to get it right on their totally customized systems! Angela OTOH knows little about platform dependencies and other stuff and simply wants to make a couple of Haskell libraries available with minimum hassle. Angela would almost certainly prefer a system in which the compiler can guarantee her that her package will install correctly on all conforming Haskell compilers to a system where she has the full freedom to script arbitarily complex installation and make arbitrarily obscure mistakes on any system. I don't know whether the setup spec should be a static data structure or Arie's setup monad, but I'm pretty sure that Angela would prefer either one to generic IO. -Alex- PS I am dropping the issue of malware here to focus on making things as easy as possible for Joe and Angela. PPS I realize that you really want to suport Marcus as well. Perhaps it might make sense to separate hc-pkg from the rest of the document? ___________________________________________________________________ S. Alexander Jacobson Check out my new blog!!! 1-917-770-6565 voice http://alexjacobson.com

4 7

RE: new Library Infrastructure spec.
by Simon Peyton-Jones 07 Jun '04

07 Jun '04

| > I like the simplicity but would also like the spec | > to make it easy for me to guarantee that that I | > don't end up running/installing malware. | > | > I think Haskell's typesystem and purity should | > make it relatively easy to make sure that: I don't think so, alas. The IO monad lets you do *anything*, and of course Setup.lhs runs in the IO monad, else it would not be able to move files or run a compiler. So I'm not optimistic. Perhaps a package whose Setup.lhs did nothing but import Distribution.Simple (which you perhaps trust) would be more trustworthy than a big pile of goop. But remember that you are installing a library that you will later (presumably) run, and that might be bad too. I'm not optimistic here. Simon

5 11

FunctorM
by John Meacham 04 Jun '04

04 Jun '04

Pretty simple, and quite useful. perhaps it could be added as Control.FunctorM ? just as Functor generalises 'map', FunctorM generalises 'mapM'. there are probably some instances I missed. note that unlike Functor, an instance for IO cannot be written for FunctorM. module FunctorM where import Array class FunctorM f where fmapM :: Monad m => (a -> m b) -> f a -> m (f b) instance FunctorM [] where fmapM f xs = mapM f xs instance FunctorM Maybe where fmapM _ Nothing = return Nothing fmapM f (Just x) = f x >>= return . Just instance Ix i => FunctorM (Array i) where fmapM f a = sequence [ f e >>= return . (,) i | (i,e) <- assocs a] >>= return . array b where b = bounds a -- John Meacham - ⑆repetae.net⑆john⑈

3 3

DiffArray deadlock
by Lauri Alanko 03 Jun '04

03 Jun '04

The following program gets stuck in ghci, and when compiled with ghc and run, fails with "Fail: thread blocked indefinitely". import Data.Array.Diff main = print (a // [((a ! 0, 1))] ! 0) where a = array (0,0) [(0,0)] :: DiffArray Int Int When DiffArray is replaced with Array, it just prints out "1" as it should. Apparently there is some kind of a deadlock internally, with the update operation holding the lock already before the lookup operation is evaluated. I think the solution is to evaluate all the indices in the argument to replaceDiffArray _before_ obtaining the lock. Changing a single line in Diff.hs gives a partial quick fix: @@ -287 +287 @@ -a `replaceDiffArray` ies = do +a `replaceDiffArray` ies = sum (map fst ies) `seq` do However, in DiffUArray, when the underlying imperative array is unboxed, the operation is strict also in the elements, and then (and _only_ then) the elements, too, need to be evaluated before the MVar is taken, or otherwise their evaluation may lead to a deadlock. I'm not really sure what would be the neatest solution. Lauri Alanko la(a)iki.fi

1 0

sequences
by Ross Paterson 03 Jun '04

03 Jun '04

I've done some crude benchmarking of different implementations of sequences: (ghc -O, times in microseconds) test cases Stack Queue Deque Append Index Update ------------------------------------------------------------- [] 5399 - - - - - JoinList 8498 17897 18197 35194 - - SimpleQueue 9198 12298 - - - - RealtimeQueue 64290 72389 - - - - BootQueue 17997 22896 - - - - BankersQueue 12098 21196 - - - - BankersDeque 16997 70589 22496 - - - Catenable 41593 123881 - 77788 - - CatDeque 57791 145477 62790 132879 - - RandList 11598 - - - 13498 29895 FingerTree 24996 33894 32994 45293 - - FingerTreeS 28995 44693 37894 68689 37094 37994 Test cases: Stack: 100000 random stack operations on a sequence of 2000 elements Queue: 100000 random queue operations on a sequence of 2000 elements Deque: 100000 random deque operations on a sequence of 2000 elements Append: building a sequence of fib 25 elements using appends Index: 100000 accesses at random indices on a sequence of 2000 elements Update: 10000 updates at random indices on a sequence of 2000 elements Implementations: [] you know; the rest are from Edison or Chris's book (RandList is skew binary random access lists), except for the last two: - an implementation using 2-3 finger trees, giving constant time access to the ends and O(log n) append. - a variant annotated with size information to support index, update and split in time O(log(min(i,n-i)). Conclusions: - Cute though the real-time queue is, the Banker's version is much better. - No implementation is clearly superior. A library would need [], JoinList, BankersQueue, BankersDeque, RandList and at least one with efficient append. (I've discounted SimpleQueue because it performs badly in a shared context.) I've argued before that the best way to express their commonality is using a Haskell 98 constructor class (albeit a fairly big one). - Catenable lists and catenable deques are still behind finger trees at these sizes, though eventually their constant time append will win out. - Finger trees with sizes look like a reasonable general purpose sequence implementation. They're not too far behind on every operation, and they also support split efficiently. Their main weakness is the O(log n) bound on append. There's a structure by Kaplan and Tarjan that improves that to O(log(log n)) while keeping the others, but it looks very complicated (and thus may have large constant factors). The code is at http://www.soi.city.ac.uk/~ross/seq.tar.gz docs are at http://www.soi.city.ac.uk/~ross/seq/

1 0

FTP library
by Keith Wansbrough 03 Jun '04

03 Jun '04

Hi all... is there an FTP client library for Haskell? I just looked through the GHC libs, haskell.org, and a quick Google, without finding anything. --KW 8-)

3 3

RE: new Library Infrastructure spec.
by Simon Marlow 02 Jun '04

02 Jun '04

On 02 June 2004 11:20, Keith Wansbrough wrote: >> We would welcome your feedback, either as a potential library or tool >> author, or as a potential consumer, or both. The specification isn't >> complete in every detail, but it seems better to post it before >> investing in details that may be rendered void by subsequent >> discussion. > > This looks great! A few comments: > > 1. In the document, Angela uses `#! runhugs' or `#! runghc' at the top > of her Setup.lhs. But Joe is running an nhc install. Angela can't > know which compiler Joe is using, and so she shouldn't have to > specify at the top of Setup.lhs. I propose that she write `#! > runhs' instead, and the compiler writers all provide a `runhs' > script (or symlink) as appropriate. Probably better than a symlink is to have a 'runhaskell' program that dynamically looks for a compiler to run, based on an order of preference. Then runhaskell can be distributed separately, and there's no retargetting of symlinks required when compilers are installed or uninstalled. This is like the runghc I wrote recently: it searches for a ghc binary in the path, so that I don't have to wire in the path to ghc when runghc is built. > 2. In section 4.1, the syntax for pkg.desc is discussed. I think the > simplest and least surprising syntax to use would be the RFC-2822 > email message header syntax (specifically sections 2.2 and 2.2.3). > That is, each field is first written as > > <fieldname> ":" <fieldbody> > > ; then long lines may be "folded" by breaking them anywhere > <whitespace> is allowed, by inserting <newline><whitespace>. > > To read this format back, first "unfold" by replacing all > <newline><whitespace> pairs with <whitespace>; then expect > <fieldname> ":" at the start of each line, with the remainder being > <fieldbody>. I like this. Cheers, Simon

1 0

RE: Tree Wars, IntMap strikes back.
by Simon Marlow 01 Jun '04

01 Jun '04

On 28 May 2004 13:59, JP Bernardy wrote: > --- Simon Marlow <simonmar(a)microsoft.com> wrote: > >> Interesting, I get pretty much the same results as >> you, except that >> DData.Map is now quicker on the lookup test than >> both FiniteMap and AVL >> (0.120 vs. 0.134 and 0.138 respectively). > > Ok, so that means that I should merge in the last > change by Daan (and in IntSet too)? I wasn't using that patch for my measurements. Cheers, Simon

2 1

RE: Tree Wars (latest round :-)
by Simon Marlow 28 May '04

28 May '04

On 27 May 2004 17:18, Adrian Hey wrote: > On Wednesday 26 May 2004 10:53 am, Adrian Hey wrote: >> I can post the test code to anyone who wants it. > > I've put the test code here.. > http://homepages.nildram.co.uk/~ahey/HLibs/TreeWars.tar.gz Interesting, I get pretty much the same results as you, except that DData.Map is now quicker on the lookup test than both FiniteMap and AVL (0.120 vs. 0.134 and 0.138 respectively). I'm not going to investigate this any further, because it'll take forever to get to the bottom of. I think we've arrived at a reasonable conclusion, that the old FiniteMap is definitely superceded but there isn't a clear choice between the others, so we should provide them all. How about the following modules: Data.Map -- a default implementation of maps, eg. DData.Map Data.Map.AVL -- same interface, based on AVL trees Data.Map.Int -- current DData.IntMap Cheers, Simon

3 2

Re: Tree Wars (latest round :-)
by Daan Leijen 27 May '04

27 May '04

On Wed, 26 May 2004 10:53:54 +0100, Adrian Hey <ahey(a)iee.org> wrote: > I got these results: > > For 500,000 random elements > Insert Lookup Delete > Data.Tree.AVL 0.923 0.203 0.798 > Data.FiniteMap 1.150 0.203 1.259 > DData.Map 1.177 0.205 1.084 > DData.IntMap 0.648 0.163 0.627 > > > For 500,000 ordered elements: > Insert Lookup Delete > Data.Tree.AVL 0.210 0.060 0.117 > Data.FiniteMap 0.473 0.076 0.137 > DData.Map 0.488 0.079 0.145 > DData.IntMap 0.108 0.039 0.054 Very cool results for AVL :-) > We still have no idea how well AVL trees perform for > set operations (haven't written the necessary code yet). Let me take this opportunity to remind us all of being careful when interpreting these numbers: most programs don't just insert and lookup in that order, but mix the operations in a lazy fashion which can lead to wildly different results. Furthermore, I tend to use "union" a lot -- I know/suspect from simple tests that DData.IntMap tends to outperform Data.Map by a wide margin on those kind of operations, etc. Btw. Given the good performance of AVL, maybe we should try to make the interface look like DData.Map (or maybe provide a seperate AVL.Map module to does that). This would allow one to use IntMap, AVL.Map or Map without changing (much) code. All the best, Daan. > > I can post the test code to anyone who wants it. > The mods to test287.hs are: > > Removed size calculation, as this O(n) for AVL trees but O(1) for > FiniteMap and DData.map and is irrelevant to insertion/deletion times. > > Increased testData size from 100,000 to 500,000. > > Used foldl' instead of foldr to prevent stack overflow. > > PerformGC at start of each test in test10 > > Had to swap args of Map.lookup in lookupsMap > > Changed the way results are displayed to be more comprehensible (to me:-) > > Regards > -- > Adrian Hey > > > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries >

2 1