- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Pure hashtable library
by Richard A. O'Keefe 29 Aug '08

29 Aug '08

On 28 Aug 2008, at 9:07 pm, Jules Bean wrote: > Insert for Data.Sequence is log(i) where i is the position of the > insertion; clearly bounded by log(n). toList is O(n) and index is > (at worst) log(i). > > I think the corresponding operations with tries are log(n), Let the key you want to insert have length L. Then insertion into a trie is O(L), independent of the size of the collection. If the "alphabet" the key's elements are drawn from is large, you can use a Ternary Search Tree, and insertion is then O(L.lg B) where B is the branching factor. There are fast Trie construction algorithms which are linear in the total size of the collection, \sum_{i=1}^{n}L_i. The worst case for Data.Sequence is where keys mostly vary at the end, in which case comparisons take O(L) time, and the cost is O(L.lg n), where n is usually much bigger than B. > So, it's all in the constants, isn't it? No.

1 0

Haskell Propeganda
by Thomas Davie 29 Aug '08

29 Aug '08

Today I made an interesting discovery. We all know the benefits of a strong type system, and often tout it as a major advantage of using Haskell. The discovery I made, was that C programmer don't realise the implications of that, as this comment highlights: http://games.slashdot.org/comments.pl?sid=654821&cid=24716845 Apparently, no one realises that a SEGFAULT is a type error, just not a very helpful one. Bob

28 50

ANN: gsl-random 0.1 and monte-carlo-0.1
by Patrick Perry 28 Aug '08

28 Aug '08

Hi everyone, I've started on bindings for the random number generators and random distributions provided by the gsl. The package is available here: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/gsl-random I've also written a monad and transformer for doing monte carlo computations that uses gsl-random internally. Here is that package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/monte-carlo For a quick tutorial in the latter package, see my blog: http://quantile95.com/2008/08/27/a-monte-carlo-monad-for-haskell/ There is also a more complicated example in the "examples" directory. Currently, only normal, uniform, and poisson random variables are supported. I have no plans to add anything else unless I need it, but I will happily accept patches if someone else is willing to do the work. One thing you may need to watch out for is that gsl-random needs to link with cblas. If your cblas is not called "cblas", you may have to edit "gsl-random.cabal" to get things to work correctly. To use the cblas that comes with the gsl, change "cblas" to "gslcblas". To use ATLAS, change "cblas" to "cblas atlas". Patrick

3 3

Re: [Haskell-cafe] Pure hashtable library
by Richard A. O'Keefe 28 Aug '08

28 Aug '08

Someone wrote: >> >> trie: O(len)*O(width) >> hashed trie: O(len) >> hash: O(len) If "width" here refers to the branching factor of the trie, it's actually O(len.lg(width)), and the width that matters is not the *possible* number of choices but the *actual* number. The great problem with hash tables is devising good hash functions. There is a vast literature about hash tables, but there is very little about how to design good hash functions for anything other than numbers and maybe strings. It would be nice to think that _had__ there been plenty of good advice about constructing good hash functions the Java library implementors would have taken it. As it is, their hashing functions for collections leave much to be desired.

5 10

Galois Tech Talks: Stream Fusion for Haskell Arrays
by Don Stewart 28 Aug '08

28 Aug '08

Just a quick note about next week's Galois Tech Talk. Now that Galois has completed its move into downtown Portland, and a shiny new, centrally located, office space, we're opening up our tech talk series a bit more widely. If you're in Portland, and interested in functional programming and formal methods, drop by! ------------------------------------------------------------------------ Title: Stream Fusion for Haskell Arrays Speaker: Don Stewart Date: Tuesday, July 15th, 10.30am sharp. Location: Galois, Inc. 421 SW 6th Ave. Suite 300 (3rd floor of the Commonwealth Building) Portland, Oregon Abstract: Arrays have traditionally been an awkward data structure for Haskell programmers. Despite the large number of array libraries available, they have remained relatively awkward to use in comparison to the rich suite of purely functional data structures, such as fingertrees or finite maps. Arrays have simply not been first class citizens in the language. In this talk we'll begin with a survey of the more than a dozen array types available, including some new matrix libraries developed in the past year. I'll then describe a new efficient, pure, and flexible array library for Haskell with a list like interface, based on work in the Data Parallel Haskell project, that employs stream fusion to dramatically reduce the cost of pure arrays. The implementation will be presented from the ground up, along with a discussion of the entire compilation process of the library, from source to assembly. About the Galois Tech Talks. Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities. The talks are open and free. If you’re planning to attend, dropping a note to <dons(a)galois.com> is appreciated, but not required. If you're interested in giving a talk, Don's always looking for new speakers. ------------------------------------------------------------------------

4 7

Haskell symbol ~
by Maurício 28 Aug '08

28 Aug '08

Hi, What does '~' mean in Haskell? I read in haskell.org/haskellwiki/Keywords that “(...) Matching the pattern ~pat against a value always suceeds, and matching will only diverge when one of the variables bound in the pattern is used.” Isn't that true for any variable, due to lazyness? At the same place, I found that example, but wasn't wise enough to figure out what it does: (f *** g) ~(x,y) = (f x, g y) Can you help me understand it? Thanks, Maurício

8 10

Pure hashtable library
by Bulat Ziganshin 28 Aug '08

28 Aug '08

Hello haskell-cafe, solving one more task that uses English dictionary, i've thought: why we don't yet have pure hashtable library? There is imperative hashtables, pretty complex as they need to rebuild entire table as it grows. There is also simple assoc lists and tree/trie implementations, but there is no simple non-modifiable hashes. how should it look: * hashtable is represented as an array of assoc lists: Array Int [(a,b)] * interface to extract data from ht is the same as from assoc list: lookup :: HT a b -> a -> Maybe b * ht may be built from assoc list. we should just know it's size beforehand in order to create Array of reasonable size. constructor also need a hashing function: create :: [(a,b)] -> Int -> (a->Int) -> HT a b given these constraints, it should be just a 10-20 lines of code, and provide much better efficiency than any tree/trie implementations -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

10 18

Building SDL-image package on Windows
by Garrick Chin 28 Aug '08

28 Aug '08

Hello, I'm trying to build the latest SDL-image package (0.5.2) from Hackage on Windows and encountering problems. These are the steps I've taken so far: 1. Downloaded SDL 1.2.13 developmental library for Mingw32 to E:\SDL-1.2.13, and SDL_image 1.2.6 developmental library for VC8 to E:\SDL_image-1.2.6. 2. Installed SDL package from Hackage, modifying the SDL.cabal according to the included WIN32 readme file and then runghc Setup.lhs configure/build/install 3. Downloaded the SDL-image package from Hackage, modified the SDL-image.cabal file to add the line "Include-Dirs: E:\SDL_image-1.2.6\include\SDL, E:\SDL-1.2.13\include\SDL" so Cabal can find the header files. After doing "runghc Setup.lhs configure", "runghc Setup.lhs build -v" gives me the following output: Creating dist\build (and its parents) Creating dist\build\autogen (and its parents) Preprocessing library SDL-image-0.5.2... Creating dist\build\Graphics\UI\SDL\Image (and its parents) E:\ghc\ghc-6.8.2\bin\hsc2hs.exe --cc=E:\ghc\ghc-6.8.2\bin\ghc.exe --ld=E:\ghc\ghc-6.8.2\bin\ghc.exe --cflag=-package --cflag=SDL-0.5.4 --cflag=-package --cflag=base-3.0.1.0 --cflag=-IE:\SDL_image-1.2.6\include\SDL --cflag=-IE:\SDL-1.2.13\include\SDL -o dist\build\Graphics\UI\SDL\Image\Version.hs Graphics\UI\SDL\Image\Version.hsc E:/ghc/ghc-6.8.2/libHSrts.a(Main.o)(.text+0x7):Main.c: undefined reference to `__stginit_ZCMain' E:/ghc/ghc-6.8.2/libHSrts.a(Main.o)(.text+0x36):Main.c: undefined reference to `ZCMain_main_closure' collect2: ld returned 1 exit status linking dist\build\Graphics\UI\SDL\Image\Version_hsc_make.o failed command was: E:\ghc\ghc-6.8.2\bin\ghc.exe dist\build\Graphics\UI\SDL\Image\Version_hsc_make.o -o dist\build\Graphics\UI\SDL\Image\Version_hsc_make.exe The results of a limited google search suggests that the __stginit_ZCMain linker error has to do with GHC expecting a main function, but I'm not really sure how that works in context of a library.

2 3

building documentation
by Thomas Hartman 28 Aug '08

28 Aug '08

I'm on ubuntu, ghc 6.8.3. I built this using the Generic i386 Linux build at http://www.haskell.org/ghc/download_ghc_683.html How do I build local documentation that matches what I see at http://www.haskell.org/ghc/docs/latest/html/libraries/ -- and am I correct that this is 6.8.3 right now? When I go to file:///usr/share/doc/ghc6-doc/libraries/index.html to browse local docu, I am missing for example Control.Monad.Error.

1 0

Is there GHC 6.8.3 on Ubuntu?
by Rafael Gustavo da Cunha Pereira Pinto 28 Aug '08

28 Aug '08

Is there anyone packing GHC 6.8.3 for Ubuntu Hardy? Thanks -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

3 2