May 2005 - Libraries - Haskell.org

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

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

Workaround for building profiling libs and apps with Cabal
by Satnam Singh 16 Jun '05

16 Jun '05

I recently tried to build a version of an application with Cabal to use with profiling by simply adding: ghc-options: -prof -auto-all to my Cabal file but this did not work because the generated .hi interface files ended in .hi and not .p_hi as expected and the .o and .a files also did not have the expected names. As a work-around I wrote a small script "fixhi" to create symbolic links for the expected filenames. The script can be adjusted to perform a rename by substituting the "ln -s" with "mv". The script is at the end of the message. It is designed to be run in the install directory of the package for a specific version e.g. lagavulin> pwd /c/Program Files/lava/lava-0.1 lagavulin> fixhi Symbolically linking ./Lava/Below.hi to ./Lava/Below.p_hi Symbolically linking ./Lava/Beside.hi to ./Lava/Beside.p_hi Symbolically linking ./Lava/Bit.hi to ./Lava/Bit.p_hi Symbolically linking ./Lava/Classes.hi to ./Lava/Classes.p_hi Symbolically linking ./Lava/Col.hi to ./Lava/Col.p_hi <...lots of lines deleted...> Symbolically linking ./Xilinx/Adder.hi to ./Xilinx/Adder.p_hi Symbolically linking ./Xilinx/Comparator.hi to ./Xilinx/Comparator.p_hi Symbolically linking ./Xilinx/Components.hi to ./Xilinx/Components.p_hi Symbolically linking ./Xilinx/OneBitAdder.hi to ./Xilinx/OneBitAdder.p_hi Symbolically linking ./Xilinx/OneBitSubtractor.hi to ./Xilinx/OneBitSubtractor.p_hi Symbolically linking ./Xilinx/Subtractor.hi to ./Xilinx/Subtractor.p_hi Symbolically linking ./Xilinx.hi to ./Xilinx.p_hi Symbolically linking ./HSlava-0.1.o to ./HSlava-0.1_p.o Symbolically linking ./libHSlava-0.1.a to ./libHSlava-0.1_p.a lagavulin> Application of the script should be idempotent. A simple change could allow the script to take a path to the installation so it can be run from elsewhere (e.g. a Makefile). I also expected when I used ghc --make to compile my programs that use this library to also be automatically compiled with "-prof -auto-all" but I guess that must be another option to Cabal and I had to add this to the ghc compilation command for the clients of this library. Hopefully the next version of Cabal will make it easier to build profiled and non-profiled versions of libraries and applications. Until then maybe the script below might provide some utility to others. I've only tested it under Microsoft Windows with msys (other OS-es are kind of hard to come by where I work). Cheers, Satnam Singh Microsoft One Microsoft Way Redmond Washington 98052-6399 USA #!/bin/sh # Workaround script for producing profiling interface files and libs # with the expected extension for use with Cabal. # Find and symbolically link to the interface files. for intfFile in `find . -name "*.hi" -print` do echo Symbolically linking $intfFile to ${intfFile%*.*}.p_hi ln -f -s $intfFile ${intfFile%*.*}.p_hi done # Find all the libraries and objects and link to them too. # First delete old profiling library files. rm -rf *_p.a *_p.o for objFile in `find . -name "*.o" -print` do echo Symbolically linking $objFile to ${objFile%*.*}_p.o ln -f -s $objFile ${objFile%*.*}_p.o done for libFile in `find . -name "*.a" -print` do echo Symbolically linking $libFile to ${libFile%*.*}_p.a ln -f -s $libFile ${libFile%*.*}_p.a done

3 2

working Edison, a couple of collection modules, and typing troubles
by Samuel Bronson 26 May '05

26 May '05

Whatever happened to Edison? I want to play with it and the one in the HFL cvs repository won't build for me (and uses flat names). I was trying my hand at writing some collection classes myself and I can't figure out a good typing for map that will let me make Map an instance of my Collection class... I'm attaching what I have so far. I don't much like the head of Mapping. I expect oleg will have some crazy type-system trick up his sleeve. -- Thankful-in-advance-ly yrs, Sam

2 2

Time library comment
by Eric Etheridge 26 May '05

26 May '05

I have read all of the comments on this list over the last half a year regarding the Time library, and I feel I need to comment. (That was a lot of reading!) I write games, and I use Haskell. I don't need a time library to do anything fancy at all, no timezones, no leap seconds, nothing. I only need two things from a Time library: 1. An absolute assurance that some method of determining current time will give me an actual resolution of at most 1-3 milliseconds, without regard for leap seconds or even the user changing the system clock. 2. A way to set an event (OS signal, IO () function, whatever) to happen a certain amount of time in the future, again without regard to leap seconds or gross alteration of the system clock. #1 is very critical to games, because it is desirable to coordinate the display function with the rate of the screen refresh, which can be 85 Hz or higher on high-end machines. Hopefully, you redraw once and only once for each screen refresh. Currently, #2 means writing my own alarm thread and depending on poll and the like, as others have pointed out. Why can't that be a standard function? All of the other functions such as conversion and the like are frivolous for game design, because everything is measured relatively from game start, since the system clock as-is can't be trusted. Don't take this too seriously. Just know that the current method of achieving that kind of resolution requires using GLUT, which means eating up more memory and CPU than necessary. As always, thanks for a wonderful language, libraries, and compilers. - Eric Etheridge __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

3 2

Win32 bindings and the GHC6.4 windows distro
by Philippa Cowderoy 24 May '05

24 May '05

I decided to have a play with the win32 bindings in the hierarchical libraries. The attached program built with ghc --make fails to link with these errors: test.o(.text+0x1c2):fake: undefined reference to `GraphicsziWin32ziMisc_messageB ox_closure' test.o(.text+0x255):fake: undefined reference to `__stginit_GraphicsziWin32ziMis c_' test.o(.data+0x3c):fake: undefined reference to `GraphicsziWin32ziMisc_messageBo x_closure' How can I get this to build for now, and is it possible to set up the package that comes with the binary windows distribution so that no fix is needed in the future? -- flippa(a)flippac.org A problem that's all in your head is still a problem. Brain damage is but one form of mind damage.

2 2

Difference Argument Order
by Ashley Yakeley 24 May '05

24 May '05

Which of these argument orders is more intuitive to you? 1. This one makes more sense when considering the function formed by applying one argument: add :: Diff -> Absolute -> Absolute add d a = a + d subtract :: Diff -> Absolute -> Absolute subtract d a = a - d diff :: Absolute -> Absolute -> Diff diff a b = b - a So "add x", "subtract y" and perhaps "diff z" are intuitively useful functions. And we also have "subtract = add . negate". 2. This one is more familiar for the English language and for the standard operators: add :: Absolute -> Diff -> Absolute add a d = a + d subtract :: Absolute -> Diff -> Absolute subtract a d = a - d diff :: Absolute -> Absolute -> Diff diff a b = a - b -- Ashley Yakeley, Seattle WA

4 7

RFC: general sequences
by Ross Paterson 24 May '05

24 May '05

A general implementation of sequences (based on work with Ralf Hinze) can be found at http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html http://www.soi.city.ac.uk/~ross/software/Data/Sequence.hs Our experiments indicate that its performance is comparable to (and sometimes better than) the best known persistent implementations(*). Non-persistent implementations are typically faster, but you need to be more careful when using them. I'd like to propose this for base. Comments welcome. (*) or at least it will be when GHC's SPECIALIZE pragma is fixed for polymorphic specializations (SF bug #1019758).

11 32

RE: GHC Win32 ffi functions as implemented for Pugs
by Simon Marlow 23 May '05

23 May '05

On 22 May 2005 23:32, Max Maischein (Corion) wrote: > The file is (live version) : > > http://svn.openfoundry.org/pugs/src/Pugs/Compat.hs > > The implemented wrappers that are functional and not just stubs are > (as of r3680) : > > For System.Environment: > setEnv :: String -> String -> Bool -> IO () > getEnv :: String -> IO (Maybe String) > unsetEnv :: String -> IO () System.Environment.getEnv should work on Win32. For the others, it would possibly make sense to include these in System.Environment, with implementations for both Unix & Win32. > For Posix.Process > getProcessTimes :: IO ProcessTimes > getProcessID :: IO Int Should probably be in System.Win32 somewhere. > The code itself is dual-licensed under the Artistic License and GPL > and thus should be compatible with whatever license GHC uses. Unfortunately we can't take code under that license into our existing packages - the rule is that each package has a single license, and currently all the packages distributed with GHC have a BSD3 license, with the exception of readline. You can start new packages, of course. > Hope you find my code useful, Contributions are always welcome, even if we can't use the code directly. You've pointed out things that the standard libraries lack. Thanks! Cheers, Simon

2 1

Let the key (digest of contents) _be_ the identity (was: hackage, cabal-get, and security)
by Dimitry Golubovsky 23 May '05

23 May '05

This was inspired by the discussion in [Libraries] on how to validate the contents of a distributed package. John Meacham wrote: > The whole idea of tying a key to an > existential identity is flawed, let the key _be_ the identity and all > problems go away. Let me suggest. Why cannot the following simple approach be used as a basis? Consider some "distribution unit", OK, let's call it "Package". It has a property of being distributed independently, say, as a tar ball (or a zip file). Right before packing, a digest may be computed (say MD5 or whatever else, doesn't really matter at this point) on the contents of a directory (with subdirectories) containing the distribution. Then a tar ball file is created in traditional way. The tarball file itself will be named based on the digest: for example, if we have computed a digest d41d8cd98f00b204e9800998ecf8427e then the file will be named "package_d41d8cd98f00b204e9800998ecf8427e.tar.gz". When a developer wishes to announce a new package, he/she supplies this digest-containing name (digest calculated just before creation of the tarball), and a "descriptive" name (say Package Foo version 8 revision 75) will accompany the announce. Such an announce being placed on one (or several) of many web-enabled mailing lists (such as the haskell mailing list for instance, or fm-announce for freshmeat) will soon be indexed by various search engines, so it will be easy to verify (even in some automated way provided that all announce messages are forced to be formatted uniformly) the identity (digest) of a package given its descriptive name. In any ambiguity, priority must be given to the earliest post found (as it was most likely made by the original developer). Someone willing to use a package, locates and downloads the tarball (by its name which contains the digest). It may then be unpacked, the digest produced: if it matches that in the file name, the file is valid, otherwise not. Additionally, size and checksum of the tarball may be also added to the announce message. So the only question I cannot answer (not being a crypto expert) is whether there exists such a digest algorithm that makes it nearly impossible to supply a distribution file with different contents, same size, and same checksum, but after unpacking, yielding the same digest value. With this approach, there is no need to have a centralized storage for packages: the Internet itself becomes such a storage, and the packages database is replaced by existing search engines given we are able to make search requests programmatically (see my earlier post in [Haskell-cafe] on locating Cabal files with Google). So, to locate a package, one searches (googles) for its descriptive name: result will return URLs of all cabal files indexed by the search engine containing such a name. The next step is downloading the cabal file and finding the distribution tarball file name. So, instead of going into cryptography problems, I am suggesting to use the contents of a package for self-validation (via computed digest), and to use the "public record" such as an internet-archived mailing list message to establish a truth about relationship between "descriptive" name (which is human-readable) and "distribution" name (which contains a digest to verify). Implementation of this approach does not need any extra software (except maybe a wrapper around md5sum or like to digest a whole directory with subdirectories) and few other shell scripts. Perhaps a tag needs to be added to cabal file syntax which would contain the digest (if one does not exist, at least I couldn't find it in the documentation at haskell.org/cabal) Distribution file name may be derived from that digest. -- Dimitry Golubovsky Anywhere on the Web

1 0