- Libraries - Haskell.org

Data.HashTable and duplicate keys
by Einar Karttunen 28 Sep '04

28 Sep '04

Hello I recently noticed that Data.HashTable silently accepts duplicate keys and keeps all the values. This is very counterintuitive from the interface and makes updating a hashtable quite tedious (lookup + delete + insert). Mentioning the feature in the documentation and providing an update function would be very nice. e.g. update :: HashTable k v -> k -> (v -> v) -> IO Bool or update :: HashTable k v -> k -> (v -> (v, w)) -> IO (Maybe w) with the result marking whether the key was present in the hashtable. On the other hand, if it is a bug I hope it will be solved quickly. The behaviour can be demonstrated with main = do ht <- new (==) hashInt insert ht 1 1 insert ht 1 2 toList ht >>= print - Einar Karttunen

2 1

new HsDNS version available
by Peter Simons 26 Sep '04

26 Sep '04

In case anyone is using my Haskell bindings to the GNU ADNS library, you might be interested to know that a new version of the package is available here: http://cryp.to/hsdns/ There have been quite a few significant improvements recently, most of which concern exception-safety, efficiency, and documentation. PollResolver.hs, in particular, has been cleaned up a lot. Peter

1 0

Benchmarking (again:-)
by Adrian Hey 11 Sep '04

11 Sep '04

Hello, I enclose a copy of some results I posted in a c.l.f thread FYI.. > Adrian Hey wrote: > >> It would be nice to have some data for other tree types too, like >> red-black trees maybe. > > Malcolm Wallace sent me some code for red-black and 234 trees which is > used in nhc98 compiler. It contains no set operations, or even delete, but > I thought it would be interesting to see how these compared with my own > AVL implementation and DData.Set (weight balanced) for simple insert, > lookup (and delete if available). > > So here are my results for trees of 500000 Int elements (execution times > and comparison counts) for ordered data and random data. > > Ordered Data (times in mS) > AVL DData.Set RedBlack 234 > ------------------------------------------- > Insert 150 366 217 255 > Lookup 53 76 116 114 > Delete 126 135 --- --- > > Ordered Data (Comparisons) > AVL DData.Set RedBlack 234 > ---------------------------------------------- > Insert 8975713 15689425 12668235 13167977 > Lookup 8975732 9166555 9132570 9132601 > Delete 6785282 6612512 --- --- > > Random Data (times in mS) > AVL DData.Set RedBlack 234 > ------------------------------------------- > Insert 763 1003 815 852 > Lookup 153 181 224 215 > Delete 803 ??? --- --- > > Random Data (Comparisons) > AVL DData.Set RedBlack 234 > ---------------------------------------------- > Insert 8953286 9155823 9104153 9106882 > Lookup 9184653 9418309 9331310 9332922 > Delete 8229843 8405601 --- --- > > Notes: > * These figures are for the entire test (not per element). > The timing measurements are averaged over 10 runs (same > test data each run). > * The Insert test constructs a tree by inserting a list of > Ints into an empty tree. > * The Lookup test checks each Int in the original list is > a member of the set (in the same order that they appear > in the list). > * The Delete test deletes each element from the set > successively, resulting in an empty set (in the order > they appear in the original list). > * There are no results for deletion from RedBlack or 234 > trees (because these functions don't exist :-) > * There is no timing result for deletion of random data from > DData.Set because the test segfaults???. But only with > random data and only when I try to time it, not with ordered > data and not if I just count comparisons. Ermm.. > > The actual execution times may be suspect (a lot will depend on > implementation details, so they don't necessarily reflect on the > algorithm). > > But the comparison counts tell us something. DData.Set, RedBlack, and > 234 all seem to be struggling with insertion of ordered data, but for AVL > it makes virtually no difference. I think my earlier remark about the > AVL algorithm being difficult to improve on is justified by these results. > > So I still say AVL is a darned good algorithm that takes a lot of beating > in practice. But I'd still be interested in being proven wrong :-) Regards -- Adrian Hey

1 0

Pairs of identifiers
by Lemming 25 Aug '04

25 Aug '04

As a guideline for future libraries I would like to have some agreed list of common pairs of identifiers. This can be useful both for designing function names and for easy guessing of the counterpart of some function. E.g. I think the names 'read' and 'show' aren't a good choice because they are a natural pair but this isn't reflected by their names. Even more 'read' and 'show' sound like some I/O operations which they are not. The choice for the Modula-3 libraries (Lex and Fmt) seems to be more suitable. I've collected some pairs of identifiers I stumbled on in AmigaOS, MUI, Modula-3, Haskell libraries, and C++ STL. This could be a basis for further discussion. I could also make a HaWiki page of this list to simplify the discussion. It would be nice if one could throw out some of the duplicates. Create Delete New Dispose Construct Destruct Alloc Free Obtain Release Attempt Lock UnLock Procure Vacate Forbid Permit Disable Enable Put Get Set Get Write Read Poke Peek Open Close Save Load Load UnLoad Init Exit Setup Cleanup Show Hide Insert Remove Add Rem Push Pull Push Pop Start Stop Size Begin End Length First Last Number Head Tail Front Back Top Bottom Fmt Lex Input Output

1 0

RE: Remaining bugs in Cabal under Windows
by Simon Marlow 18 Aug '04

18 Aug '04

On 18 August 2004 11:05, Krasimir Angelov wrote: > --- Simon Marlow <simonmar(a)microsoft.com> wrote: > >> While writing docs for getHomeDirectory / >> getAppUserDataDirectory, it >> occurred to me that we should probably have >> getUserDocumentsDirectory >> too. Thoughts? > > This is easy for Windows but I don't know the right > Linux convention. Mandrake uses > /home/<user name>/Documents. $HOME is fine. It would be used as the default directory in a "Save As..." dialog box, for example. Cheers, Simon

1 0

RE: Remaining bugs in Cabal under Windows
by Simon Marlow 18 Aug '04

18 Aug '04

While writing docs for getHomeDirectory / getAppUserDataDirectory, it occurred to me that we should probably have getUserDocumentsDirectory too. Thoughts? Cheers, Simon

2 1

RE: Filename handling
by Graham Klyne 17 Aug '04

17 Aug '04

At 14:04 17/08/04 +0100, Simon Marlow wrote: >On 17 August 2004 12:44, Graham Klyne wrote: > > > Anyway, I'd like to see the common library functions provide at least > > minimal capabilities to allow multi-platform applications to do the > > right > > thing when handling filenames. I'm pretty agnostic about what they > > actually look like, but as an example I've found the Python and/or > > Java > > libraries to be pretty usable in this respect. > >I think there's general agreement that this would be a good thing, but >discussion never seems to reach a conclusion. Anyone like to whip up a >concrete proposal? This may be a bit radical, but I'll float it anyway: pathToUri :: String -> String -- convert filename to a file: URI according to local system conventions uriToPath :: String -> String -- convert a file: URI to filename according to local system conventions Hmmm... to preserve referential transparency, I suppose that should be: pathToUri :: String -> IO String uriToPath :: String -> IO String The rationale here is that these two functions can be used to get any filename on any system into a form with well-defined syntax and properties and back again, allowing the other filename processing requirements (splitting apart, putting together, relative path evaluations, etc.) to be performed with the common form. Of course, this doesn't deal with operations that need to actually access the file system (directory scanning, etc.), but many of these seem pretty well catered for in any case (cf. Directory library functions). ... Failing this, I'd say that Isaac's module [1] has some pretty reasonable functions. I'd pick out: splitLastComp :: FilePath -> (FilePath,FilePath) isAbsolute :: FilePath -> Bool splitExt :: FilePath -> (FilePath, String) The next function would be useful, but I'd be reluctant to include it until we're confident of having consistent regex support on all platforms: matchPath :: String -- ^RegExp -> IO [FilePath] -- ^IO because it must look to see what exists An alternative, avoiding regex dependence, might be: matchPath :: (FilePath -> Bool) -> IO [FilePath] And a very important (IMO) function that I don't see in Isaac's module would be something like: relativeTo :: FilePath -> FilePath -> FilePath In my URI processing code, I've also added a complementary function: relativeFrom :: FilePath -> FilePath -> FilePath which returns a relative path such that: (path `relativeFrom` base) `relativeTo` base == path noting that the result relativeFrom is not always uniquely determined. Maybe it's better to leave this out. I think that a function like: isDirectory :: FilePath -> IO Bool may also be needed when performing directory scanning operations. [1] http://www.syntaxpolice.org/darcs_repos/OS.Path/Path.hs ... Some related questions to consider: - should we take seriously the point I make above about using IO so that referential transparency is rigorously preserved? If so, all of the above functions should return IO values, as the result may vary depending on the environment in which the program runs. - do we care about legacy operating systems like VAX/VMS? (that would require version number support, and doesn't work well with interfaces that assume a single path separator character). - how does the interface work with forthcoming systems like Microsoft's Longhorn. I hear that the directory tree concept is being replaced by file "attributes". Which leads me to think of... - how does the interface work with WebDAV, which builds a file system like interface over HTTP, and adds property lists to the resources identified. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: Filename handling (was: Remaining bugs in Cabal under Windows)
by Simon Marlow 17 Aug '04

17 Aug '04

On 17 August 2004 12:44, Graham Klyne wrote: > Anyway, I'd like to see the common library functions provide at least > minimal capabilities to allow multi-platform applications to do the > right > thing when handling filenames. I'm pretty agnostic about what they > actually look like, but as an example I've found the Python and/or > Java > libraries to be pretty usable in this respect. I think there's general agreement that this would be a good thing, but discussion never seems to reach a conclusion. Anyone like to whip up a concrete proposal? Cheers, Simon

2 1

RE: Remaining bugs in Cabal under Windows
by Simon Marlow 17 Aug '04

17 Aug '04

On 16 August 2004 19:20, Krasimir Angelov wrote: > There still exists some bugs in Cabal when it is > used under Windows. > > - The platform dependent places in the code are > marked with #ifdef mingw32_TARGET_OS but this macro is > never defined ever under Windows. You must add > -Dmingw32_TARGET_OS to the command line while building > setup.exe and also add -Dmingw32_TARGET_OS to > options-ghc field in Setup.description. I'll fix this. Isaac: is it ok for me to commit fixes to the repository? I have a couple of other things I found when building Cabal on Windows recently, and Krasimir has sent me a large patch to fix a number of problems. > - When Cabal is used to build library package then > it fails to find ar.exe in the path. This isn't a > problem when in the build is run from cygwin or mingw > environment but is painful on plain Command prompt. Agreed - one of the goals of Cabal is that it should work with a plan GHC installation, no cygwin required. I think ar.exe should be packaged with GHC in the same directory as ghc.exe, so that it'll be available in the PATH. This is easier than providing ar functionality from GHC itself, which would perhaps be nice but is more work and is GHC-specific, you still have to invoke ar for other compilers. > - The package uses (getEnv "HOME") to get the path > to home directory. The variable isn't present in plain > Command prompt under Windows. Agreed. I need to know the equivalent of $HOME for GHC too, so that GHC can keep a per-user package database. > - The default installation prefix under Windows is > "C:\Program Files" but it is known that some times GHC > doesn't work very well with paths which have spaces. I > don't know whether this can be fixed or this depends > from gcc and ld GHC itself doesn't have problems with pathnames with spaces in; GHC's build system does, though. I claim: it should be a goal to make everything work for pathnames containing spaces. > To fix third bug I tried to use > SHGetFolderPathAndSubDir function to retrieve the > "Application Data" folder for current user. > This is: > > "C:\Documents and Settings\kr_angelov\Application > Data" > > on my PC. The trouble here is that to do that I need > to add shell32 to extra-libs field in package > description. I don't have a way to preprocess > Setup.description so I can't add shell32 > conditionally. > I would like to have a collection of functions like: > > getCurrentDirectory we already have that > getAppUserDataDirectory > getHomeDirectory Maybe - although the conventions still differ between Unix and Windows. On Unix, to store per-user data you would use <homedir>/.<app> whereas on Windows you use <homedir>/<app>. So I think the win32 library should provide access to getAppUserDataDirectory, and the app code still needs to be conditionally compiled. Cheers, Simon

4 3

RE: Remaining bugs in Cabal under Windows
by Simon Marlow 17 Aug '04

17 Aug '04

On 17 August 2004 13:44, Krasimir Angelov wrote: > {-# OPTIONS -cpp #-} > #ifdef mingw32_TARGET_OS > {-# OPTIONS -#include "shlobj.h" #-} > #endif > > #ifdef mingw32_TARGET_OS > import Foreign > import Foreign.C > #else > import System.Environment > #endif > > getHomeDirectory :: IO FilePath > getHomeDirectory = > #ifdef mingw32_TARGET_OS > allocaBytes 1024 $ \pPath -> do > r <- c_SHGetFolderPath nullPtr 0x28 nullPtr 0 > pPath > if (r < 0) > then c_SHGetFolderPath nullPtr 0x05 nullPtr 0 > pPath > else return 0 > peekCString pPath > #else > getEnv "HOME" > #endif > > getAppUserDataDirectory :: String -> IO FilePath > getAppUserDataDirectory appName = do > #ifdef mingw32_TARGET_OS > allocaBytes 1024 $ \pPath -> do > r <- c_SHGetFolderPath nullPtr 0x1A nullPtr 0 > pPath > s <- peekCString pPath > return (s++'\\':appName) > #else > path <- getEnv "HOME" > return (path++'/':'.':appName) > #endif I'm happy for these functions to go into System.Directory, unless anyone disagrees. Instead of using the manifest constants (0x28, 0x05, 0x1A) use another method to get the constants in - for libraries/base the technique we use is to define an inline function in HsBase.h. If you commit the code, I'll add Haddock comments. Cheers, Simon

1 0