June 2005 - Libraries

Trie implementation
by Keith Wansbrough 10 Mar '06

10 Mar '06

Hi... I was writing some code yesterday to walk over a directory tree, and needed a Trie. Not seeing one around, I wrote a basic implementation of the functions I needed (attached below). Has anyone else done this? Should I polish it up and offer it for inclusion in Data? --KW 8-)

7 8

Network library: getting host address
by Manuel M T Chakravarty 03 Jul '05

03 Jul '05

Is there any good reason why I can get a bound socket's port with getPortSocket, but cannot get its host address (ie, IP number)? Sure, this makes only sense for ip sockets, but there it is sometimes crucial to get at this information. I can get the information using the lower-level Network.Socket using > SockAddrInet _ hostAddr <- getSocketName socket > host <- inet_ntoa hostAddr but I think that this is the kind of information that needs to be available in the high-level interface, too. BTW, shouldn't Network also reexport constants, such as aNY_PORT and iNADDR_ANY. Manuel

1 1

RE: package mounting
by Simon Marlow 29 Jun '05

29 Jun '05

On 23 June 2005 10:14, Frederik Eaton wrote: > It looks like there's been a bit of recent discussion regarding module > and package namespaces. There is a certain possible design feature > that I don't think has been mentioned yet, that I think would be very > helpful, so I thought I should at least bring it up. This idea has been raised before, but it was a while back, and we called it "grafting". Here's the start of the thread, which went on for quite some time: http://www.haskell.org/pipermail/libraries/2003-August/001310.html I suspect that various opinions raised in that thread have now changed (mine included). I'm not sure I can succinctly describe why the idea wasn't adopted - I think it is a combination of the complexity it introduces in the implementations, the feeling that the power to weight ratio is a little too low, and the fact that at the time there were many other issues to resolve in the packaging system without considering grafting. As I said, opinions may have changed, and it might be worthwhile to discuss this again. Cheers, Simon

4 4

RE: package mounting
by Simon Marlow 29 Jun '05

29 Jun '05

On 29 June 2005 12:56, Benjamin Franksen wrote: > On Tuesday 28 June 2005 11:30, Simon Marlow wrote: >> So our story for portability is that code which is intended to >> compile on more than one system must travel with its dependencies, >> where those dependencies include which packages (and versions) the >> code requires and which compiler options are required to compile it. >> All this information is stored in the .cabal file, so code is >> portable if it is a Cabal package. Grafting locations fit into this >> scheme nicely. > > Yes. Nevertheless, I agree with Frederik that the package should only > provide a default location in the module name space. I want to be able > to override this default with a compiler flag, and possibly also in > the .cabal file for the client application. Absolutely - sorry for introducing unnecessary confusion. In the paragraph you quoted above, I was referring to the grafting locations of the *dependencies*, not the package itself. Cheers, Simon

1 0

RE: package mounting
by Simon Marlow 29 Jun '05

29 Jun '05

On 28 June 2005 07:34, Frederik Eaton wrote: >> And for the same reason we have "exposed" packages, it makes sense to >> have a default set of grafting locations per user/system (this is >> debatable; indeed sometimes I think we should remove "exposed" >> completely and force non-Cabal users to write -package flags). > > I'm not sure what this "same reason" is - exposed packages are a > reason to require a faithful module namespace, and default grafting > locations would help provide that, is this it? The only reason to have "exposed" packages is so that you don't have to specify a bunch of -package options when invoking GHC or GHCi. It's convenient to be able to just import a hierarchical module without having to say which package it comes from. However, exposed packages are evil because there's no guarantee that different systems will have the same set of exposed packages, so code that compiled on one system may not compile on another. But this is no worse than the non-portability caused by different systems having different packages installed, or different versions of packages, or indeed different compilers. So our story for portability is that code which is intended to compile on more than one system must travel with its dependencies, where those dependencies include which packages (and versions) the code requires and which compiler options are required to compile it. All this information is stored in the .cabal file, so code is portable if it is a Cabal package. Grafting locations fit into this scheme nicely. Cheers, Simon

2 1

Re: Haskell Matrix Library
by Keean Schupke 29 Jun '05

29 Jun '05

Must be the season for matrix-libraries... Alberto Ruiz has just posted bindings to the GSL library on the haskell-cafe which seems to do more or less what I need from a matrix library - and more efficiently than doing it in Haskell. I'm going to give this a go and see if it does what I need. Keean.

1 0

Are new sequences really O(1)?
by Adrian Hey 28 Jun '05

28 Jun '05

Hello, Just been trying a few simple benchmarks to compare the new sequences with AVL trees for simple deque operations and I'm getting some strange results. Code for both is attached at the end of this post, but basically the test in each case is: 1- Build a sequence of sz elements by pushing them one by one on the right. 2- Rotate the sequence right sz times, each rotation pops the rightmost element and pushes it on the left. 3- Empty the sequence by popping the leftmost element sz times. With ghc-6.4, results are (time in no particular units) sz AVL Sequence ---------------------- 2^10 0.278 0.177 2^11 0.666 0.425 2^12 1.464 0.958 2^13 3.112 2.214 2^14 6.664 5.525 2^15 14.18 12.18 2^16 30.16 27.31 2^17 62.14 60.6 2^18 130.4 142.6 2^19 269.3 365.1 2^20 564.4 ***** The AVL figures seem to show roughly the kind of n*(log n) growth I would expect. The Sequence figures start out promisingly enough, but seem to get progressively worse until it's actually slower than AVL. This isn't what I'd expect from an algorithm advertised as having O(1) asymptotic complexity for pushing/popping. It seems more like O(log n) or worse? Also there are no figures for 2^20 for Sequence because I get a stack overflow at this point. So any idea whether this is a bug in my understanding?, or a bug in the theory?, or a bug in the code perhaps? Maybe it's being excessively lazy somewhere (often the cause of stack overflows IME). Regards -- Adrian Hey Code follows: {-# OPTIONS -fno-cse -fno-full-laziness #-} module Main (main) where import Data.Sequence import System.CPUTime(getCPUTime,cpuTimePrecision) import System.Mem(performGC) result :: Int -> Seq () result sz = rep pop $ rep rot $ rep push empty where rep = rep' sz rep' 0 f x = x rep' n f x = let x' = f x in x' `seq` rep' (n-1) f x' push sq = sq |> () rot sq = case viewR sq of sq' :> x -> x <| sq' EmptyR -> empty pop sq = case viewL sq of _ :< sq' -> sq' EmptyL -> undefined test :: (Int,Int) -> IO () test (n,sz) = do performGC t0 <- getCPUTime rep n t1 <- getCPUTime putStr $ show sz ++ " : " putStrLn $ show $ (fromIntegral ((t1-t0) `div` cpuTimePrecision)) / (fromIntegral n) where rep 0 = return () rep m = (result sz) `seq` rep (m-1) main :: IO () main = mapM_ test [(10*2^(maxP-p), 2^p) | p <- [10..maxP]] where maxP = 20 ---------------------------------------------------------------- {-# OPTIONS -fno-cse -fno-full-laziness #-} module Main (main) where import Data.Tree.AVL import System.CPUTime(getCPUTime,cpuTimePrecision) import System.Mem(performGC) result :: Int -> AVL () result sz = rep pop $ rep rot $ rep push empty where rep = rep' sz rep' 0 f x = x rep' n f x = let x' = f x in x' `seq` rep' (n-1) f x' push sq = pushR sq () rot sq = case popR sq of (sq', x ) -> pushL x sq' pop sq = case popL sq of (_ , sq') -> sq' test :: (Int,Int) -> IO () test (n,sz) = do performGC t0 <- getCPUTime rep n t1 <- getCPUTime putStr $ show sz ++ " : " putStrLn $ show $ (fromIntegral ((t1-t0) `div` cpuTimePrecision)) / (fromIntegral n) where rep 0 = return () rep m = (result sz) `seq` rep (m-1) main :: IO () main = mapM_ test [(10*2^(maxP-p), 2^p) | p <- [10..maxP]] where maxP = 20

14 45

RE: package mounting
by Simon Marlow 28 Jun '05

28 Jun '05

[ moved to the libraries list; replies here please ] On 24 June 2005 16:22, Frederik Eaton wrote: > (By the way, sorry about cross-posting again. People have already > replied to just 'haskell@' and just 'libraries@' but I'll try to stick > to 'libraries@' after this since it seems that some users' mail > clients show them two copies otherwise) > >> This idea has been raised before, but it was a while back, and we >> called it "grafting". Here's the start of the thread, which went on >> for quite some time: >> >> http://www.haskell.org/pipermail/libraries/2003-August/001310.html > > Actually it looks like that is slightly different from my idea, > perhaps I should have expounded a bit more in my original post. > Correct me if I'm wrong, but in my proposal: > > - grafting/mounting would be done per compilation unit. In yours it > seems it would be done per (user, system). > > - configuration of graft/mount points would be done at compile time, > zero or one times per package import option. In yours it would be at > package install time. Technologically it makes no difference; the key point from an implementation point of view is that the grafting point is not specified when a package is compiled, it is specified at some later time, and without modifying the contents of the package itself. The rest is "just" the user interface. > I think my proposal is better. In it there would be no cross-system > compatibility issues: since each program would specify where its > imported packages get mounted itself, you could write a Haskell > program on one system and be assured that someone else could use it on > another system without problems. I think this is a rather important > property and we shouldn't allow it to be broken Plain Haskell source code is already not portable, because it doesn't contain packaage dependencies. Also, "exposed" and "hidden" packages break portability, which is why Cabal now explicitly hides all packages. Our story for portability is that the extra information needed to ensure portability of your source code is contained in the Cabal package: you can't necessarily move plain Haskell source from one system to another and expect it to compile, but you *can* move a Cabal pacakge. If we had grafting/mounting, I think it would be most naturally exposed as a straightforward extension of Cabal's build-depends field, where a grafting location would be listed with each package dependency. Of course, there would be equivalent command-line options for raw use of the compiler. And for the same reason we have "exposed" packages, it makes sense to have a default set of grafting locations per user/system (this is debatable; indeed sometimes I think we should remove "exposed" completely and force non-Cabal users to write -package flags). Cheers, Simon

2 1

Dummy export for Text.Show.Functions
by Thomas Jäger 27 Jun '05

27 Jun '05

Greetings list, The module Text.Show.Functions only defines a Show instance for function types, and thus exports nothing. This is annoying when -Wall is used, as ghc can't check whether the instance is actually used in the program and always issues a warning. > Warning: Module `Text.Show.Functions' is imported, but nothing from it is used > (except perhaps instances visible in `Text.Show.Functions') Would it be possible for Text.Show.Functions to (re)export a dummy entity, preferably Show(..), since most modules that use this module will call show anyway? Thomas

2 1

AVL library update available.
by Adrian Hey 26 Jun '05

26 Jun '05

Hello, At.. http://homepages.nildram.co.uk/~ahey/HLibs/Data.Tree.AVL/ ..you can find the another release of the Data.Tree.AVL library. A few notes about this release: The library is not intended to provide an elegant api or to be a model of what general purpose collection classes should look like. It just aims to provide raw AVL operations as efficiently and flexibly as possible. This version and the Data.COrdering library have had a major purge of 1 line trivia (which I decided were really little more than name space pollution in practice). I'm sure that anybody using it is quite capable of writing whatever trivia they need so I decided to try and restrict myself to the stuff you really don't want to have to write yourself if you can avoid it. So the Map module has been removed completely. This release has also had a Zipper module added, which should be useful for implementing many of those awkward operations not covered by the main library. Earlier (on the libraries list I think), I said I would also include AVL tree based clones of Data.Set and Data.Map. I did start on this but then stopped as I don't think there's any point. The native AVL api is more useful (in my completely biased and not at all humble opinion :-). But these clones are about 75% complete so if somebody really wants them finished I might be persuaded to do this. In the meantime there's are some conversion utilities to convert between AVL trees and Data.Set, Data.Map. The library is not yet cabalised as there are apparently some difficulties using cabal with the ghc -split-objs option (which I use to reduce the bloat of executables). But the makefile enclosed should work OK on *nix environments for ghc 6.4 only (it uses new package descriptions so won't work with earlier ghc versions). The source code should be OK with other Haskells too, but the makefile assumes ghc. I haven't tried building under windows (shouldn't be too hard but makefile would probably need some hacking). I'd like to think this is reasonably complete (and stable) now, but it almost certainly isn't complete. So if anybody has any feature requests please let me know. I've marked the modules as being "stable", so I promise not to introduce any radical api changes or disappearances in future releases. Regards -- Adrian Hey

1 0