February 2010 - Haskell-Cafe

Re: [Haskell-cafe] Very imperfect hash function
by John Lato 02 Feb '10

02 Feb '10

> From: Hans Aberg <haberg(a)math.su.se> > > On 28 Jan 2010, at 20:07, Steve Schafer wrote: > >> The data are currently in a large lookup table. To save space, I'd >> like >> to convert that into a sort of hash function: >> >> hash :: key -> value >> >> My question is this: Is there any kind of generic approach that can >> make >> use of the knowledge about the internal redundancy of the keys to come >> up with an efficient function? > > There are minimal perfect hash functions; there are some libraries > mentioned here, though they are not in Haskell code: > http://en.wikipedia.org/wiki/Perfect_hash_function > > This is suitable when you do a lot of lookups with few key updates. An > alternative might be Data.Map, where lookups have time complexity > O(log n), n = size of map. The minimal perfect hash function looks like the real algorithmic solution, but I would just use Data.IntMap for this. Cheers, John

3 7

Very imperfect hash function
by Steve Schafer 01 Feb '10

01 Feb '10

I'm looking for some algorithmic suggestions: I have a set of several hundred key/value pairs. The keys are 32-bit integers, and are all distinct. The values are also integers, but the number of values is small (only six in my current problem). So, obviously, several keys map to the same value. For some subsets of keys, examining only a small portion of the key's bits is enough to determine the associated value. For example, there may be 250 keys that all have the same most-significant byte, and all 250 map to the same value. There are also keys at the other extreme, where two keys that differ in only one bit position map to different values. The data are currently in a large lookup table. To save space, I'd like to convert that into a sort of hash function: hash :: key -> value My question is this: Is there any kind of generic approach that can make use of the knowledge about the internal redundancy of the keys to come up with an efficient function? Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

5 4

Re: Non-termination of type-checking
by oleg＠okmij.org 01 Feb '10

01 Feb '10

Here is a bit more simplified version of the example. The example has no value level recursion and no overt recursive types, and no impredicative polymorphism. The key is the observation, made earlier, that two types c (c ()) and R (c ()) unify when c = R. Although the GADTs R c below is not recursive, when we instantiate c = R, it becomes recursive, with the negative occurrence. The trouble is imminent. We reach the conclusion that an instance of a non-recursive GADT can be a recursive type. GADT may harbor recursion, so to speak. The code below, when loaded into GHCi 6.10.4, diverges on type-checking. It type-checks when we comment-out absurd. {-# LANGUAGE GADTs, EmptyDataDecls #-} data False -- No constructors data R c where -- Not recursive R :: (c (c ()) -> False) -> R (c ()) -- instantiate c to R, so (c (c ())) and R (c ()) coincide -- and we obtain a recursive type -- mu R. (R (R ()) -> False) -> R (R ()) cond_false :: R (R ()) -> False cond_false x@(R f) = f x absurd :: False absurd = cond_false (R cond_false)

7 9

very strange utf8 problem
by Günther Schmidt 01 Feb '10

01 Feb '10

Hi all, I know this sounds daft but I do have good reason to ask. Is it possible that GHC's core itself has a problem with a particular Umlaut only? HDBC-ODBC won't read in data from an SQLite database as soon as it comes accross a *lowercase* U-Umlaut ("ü") ghci crashes. Other Umlauts ("ä", "ö" and "ß") pass however. This is the error message: readUTF8Char: illegal UTF-8 character 252 As I said, other Umlauts do pass. I got this very message quite often, usually when working with databases and not always using HDBC but also Takusen. I kept blaming it on HDBC-ODBC or the input data but I might have been wrong there. Günther

2 1

OT: Literature on translation of lambda calculus to combinators
by Dušan Kolář 01 Feb '10

01 Feb '10

Dear cafe, Could anyone provide a link to some paper/book (electronic version of both preferred, even if not free) that describes an algorithm of translation of untyped lambda calculus expression to a set of combinators? Preferably SKI or BCKW. I'm either feeding google with wrong question or there is no link available now... Thanks, Dušan

10 11

Determining application directory
by Matveev Vladimir 01 Feb '10

01 Feb '10

Hi, I'm writing cross-platform application in Haskell which should be running under Windows and Linux. Under Linux configuration is stored in the /etc directory, and under Windows configuration is meant to be in the application directory. So, is there a way to get an application directory path under Windows? I remember that there is a way to do this using WinAPI, but how to do this Haskell?

7 9

Greencard/c2hs + cabal
by Maciej Piechotka 31 Jan '10

31 Jan '10

I have a problem with integrating cabal with greencard. 1. When I run build it creates: src/Path/To/Module_stub_ffi.c src/Path/To/Module_stub_ffi.h instead of dist/build/Path/To/Module_stub_ffi.c dist/build/Path/To/Module_stub_ffi.h 2. I get the unknown symbols errors for symbols defined in stubs. The problem is that I need to import the macros constants c2hs puts #c/#endc in header which is not compiled (and therefore suffers from the same problems). Is there any way to get the value of macro without having additional c file? Regards

1 0