- Haskell - Haskell.org

Re: slightly ot: data structure question
by George Russell 02 Aug '02

02 Aug '02

Andrew Bromage wrote > On Mon, Jul 29, 2002 at 02:50:55PM -0700, Hal Daume III wrote: > > > I need a data structure which is a map from Ints to Doubles; the > > distribution of the Ints is in the range say 0-20000 and a map will > > contain somewhere around 100-200 elements. I need to be able to query > > *very* quickly, insert *quite* quickly, and iterate through the elements > > very quickly. I'm thinking hash tables, but I'm not sure. Does anyone > > have any thoughts on this? > > How about this? > > http://citeseer.nj.nec.com/briggs93efficient.html > > Another paper which might be useful: > > Aasa, A., Holstrom, S. and Nilsson, C. (1988), > "An Efficiency Comparison of Some Representations of Purely > Functional Arrays". BIT 28(3):490--503. You aren't doing sparse matrix computations are you? In that case there are specialised storage techniques around, which are probably better than any general solution. If you ask on sci.math.num-analysis you'll probably get more references than you know what to do with. The method in the first paper effectively has one array of length 20000 allowing you to query *very* quickly, plus a smaller array listing the elements. I think the main problem with this would be the array of 20000 elements. Apart from the cost of memory (which is probably pretty insignificant), you have the problem that 20000 elements is 160kB which is quite a lot to all keep in cache at once. If the elements are uniformly distributed it seems to me you might get better performance by, say, using a closed hash table with size say 1024 and indexing just by some selection of 10 bits from the integers. (Of course if the integers are not uniformly distributed you will need a better hash function.) Then in 80-90% of cases you will get a positive/negative answer to the query in just one lookup; if it's a don't know (there is a different element at this position) you will only have to scan through the same cache line (almost certainly) until you get the right answer. You can also dispense with the first paper's auxiliary array this way by setting the integers in the array to out-of-range values (or by using signalling NaN's for the doubles); iterating through the array checking all the integers shouldn't take too long.

1 0

how to catch GHC "no threads to run" exception?
by paul＠theV.net 02 Aug '02

02 Aug '02

My program runs 3 threads, and after a few minutes' execution all threads come to a state that they all wait on some MVars, then the program halts with an error: test: no threads to run: infinite loop or deadlock? (test is my program name) My problem is that this behavior is actually desired, but how do I catch this exception and do some bookkeeping (closing external IO, etc.) and then a proper exit? Thanks in advance! Regards, .paul.

3 3

can't write instance Storable
by Hal Daume III 02 Aug '02

02 Aug '02

Okay, I'm dumb and can't figure this out. I'm migrating hMPI from GHC 4.08 to GHC 5.04 (fun fun) and am having trouble writing an instance of Storable. The relevant information is: > import Foreign.Storable > type MPI_Rank_Type = Int > newtype MPI_Rank = MPI_Rank MPI_Rank_Type deriving (Eq) > > instance Storable MPI_Rank where > sizeOf (MPI_Rank r) = sizeOf r > alignment (MPI_Rank r) = alignment r > peek addr = do r <- peek addr > return (MPI_Rank r) > poke addr (MPI_Rank r) = poke addr r which doesn't work; ghc complains: /nfs/isd/hdaume/download/hmpi-0.9.3/src/Foo.hs:12: Couldn't match `MPI_Rank_Type' against `MPI_Rank' Expected type: MPI_Rank_Type Inferred type: MPI_Rank In the first argument of `MPI_Rank', namely `r' In the first argument of `return', namely `(MPI_Rank r)' Failed, modules loaded: none. I have no idea what's wrong. if i make it "...do (r :: Int) <- ..." it complains: /nfs/isd/hdaume/download/hmpi-0.9.3/src/Foo.hs:12: Couldn't match `Int' against `MPI_Rank' Expected type: Int Inferred type: MPI_Rank When checking the pattern: r :: Int In a 'do' expression pattern binding: (r :: Int) <- peek addr Failed, modules loaded: none. it's like it doesn't realize that "peek" is part of the class and can be overloaded. someone please clear this up and tell me what obvious thing i'm missing... Thanks! - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

slightly ot: data structure question
by Hal Daume III 02 Aug '02

02 Aug '02

Not really Haskell-specific, but... I need a data structure which is a map from Ints to Doubles; the distribution of the Ints is in the range say 0-20000 and a map will contain somewhere around 100-200 elements. I need to be able to query *very* quickly, insert *quite* quickly, and iterate through the elements very quickly. I'm thinking hash tables, but I'm not sure. Does anyone have any thoughts on this? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

monads, modules, sandboxes
by Daniel Crealer 01 Aug '02

01 Aug '02

Warning: pseudo-caml below since I don't know Haskell too well. But in trying to learn I came across interesting concept of monad, and that is what inspired the following idea. I would just like to know if anyone thinks it's interesting and if someone has already developed it. Inspired by monads, I had the following idea for controlled sandboxing of an application. I'll give you a very concrete scenario, but maybe it isn't the most interesting use of idea. I download a program off the Internet that claims to do some interesting transformation on my data. But I don't trust the application not to send my secret data back to the web site. I could achieve this by running the program in a sandbox that doesn't allow it to send data over the Internet. But maybe the program has legitimate reasons to send data, e.g., the company charges based on how much data I transform, so the program wants to periodically send messages to the web site saying it performed some units of work. The idea is just that if my data has type t, instead of a program of type t -> t, the website provides a program of type m -> m written in a monadic style. Actually m = t, and the bind operation (>>=) is trivial. But it is run in the sandbox. Here is pseudo-code, where MYDATA is thought of as a well-known signature of a well-known standard, like JPEG or something, with standard implementation MyData (though I could change MyData as long as I think my changes won't break the code I got off the web site) and DataTransformer is the untrusted code from the web site. In some applications, probably you could get away with just bind and return, but for the example I give here, the untrusted code needs a way to find out if the data is done being transformed. I implement that by providing an is_done function, but note that this could be a security hole. A safer way might be to have really_do_100_steps throw an exception when it finishes that would be caught by bind. module MyData = struct type t = ... type m = t let (>>=) mm f = try run_in_sandbox (fun _ -> f mm) with _ -> failwith "gotcha" let return x = x (* functions that only run in the sandbox *) ... things that take t's ... (* functions that can run outside the sandbox *) let is_done = ... ... other things that take m's ... end module type MYDATA = sig type t = ... type m val (>>=) : m -> (t -> m) -> m val return : t -> m is_done : m -> bool ... other stuff ... end module DataTransformer = struct let really_do_100_steps x = ... let do_100_steps x = x >>= (function y -> return (really_do_100_steps y)) let rec doit x = bill_customer_for_100_steps (); let x' = do_100_steps x in if is_done x' then x' else doit x' end _________________________________________________________________ Join the worlds largest e-mail service with MSN Hotmail. http://www.hotmail.com

3 2

Re: good advanced fp (haskell) book
by Fritz K Ruehr 01 Aug '02

01 Aug '02

Chris Okasaki's book "Purely Functional Data Structures" is not on Haskell per se, but it addresses data structures (and efficiency issues) from a higher level than the typical introductory FP book. All the data structures and code are available in Haskell in an appendix (and on-line). Amazon has 15 sample pages (hmm, must be a big seller). You should also look at the book "Algebra of Programming" by Richard Bird and Ooge de Moor: you will find much to satisfy your mathematical tastes, as well as motivations which include efficiency. Again the language is not exactly Haskell, but if past history is any guide, then Haskell will probably look more like the language of this book after a few years anyway :) . -- Fritz Ruehr PS: I found "A of P" on Barnes and Noble's site more easily than on Amazon.

1 0

good advanced fp (haskell) book
by Hal Daume III 01 Aug '02

01 Aug '02

Hi all, I'm looking to purchase one (perhaps two) books for my collection. I'm looking for two things in particular: - good algorithmic reference - good explanation of the meat of haskell (advanced stuff) I don't care about introductory stuff; I've written tens of thousands of lines of Haskell code and don't want to waste my time reading what a tuple is. I was looking at the "Algorithms: A Purely Functional Approach" online which, based on the contents, seems to satisfy well my first desire, but I fear it doesn't get advanced quickly enough and am left with only a little on advanced topics. All the other books I looked at on the bookshelf seemed too introductory. I'm not afraid of math (it was my undergraduate degree) and rather enjoy theorems, but I'm also insanely practical and am interested in a book which has a large section on *efficiency*. I fear what I'm looking for doesn't exist, and in the absense of a book, perhaps people could point me to good extended (perhaps journal?) papers -- though papers tend to largely ignore the efficiency stuff and serve as very poor references. Thanks! - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

3 2

Correction
by Carl McTague 31 Jul '02

31 Jul '02

I'm sorry, there was a subtle error in the definition of the function finAuDeterminize in my posting, which caused genuine performance trouble! Replace sort by (sort.nub). That is: finAuDeterminize :: (Ord l) => FinAu l -> FinAu [l] finAuDeterminize startStates = [f startStates] where f :: (Ord l) => [FaState l] -> FaState [l] f states = FaState label' acceptQ' trans' where label' = (sort.nub) (map label states) acceptQ' = or (map acceptQ states) trans' = map (singleton.f.concat) (transpose (map trans states)) singleton a = [a] Carl

1 0

Efficiency of list indices in definitions
by Carl McTague 31 Jul '02

31 Jul '02

Hi, I'm experimenting with various implementations of finite automata. I think the following is interesting, but gives rise to a question, which might actually be silly. (Forgive me if it is.) First, I can define a state as a recursive data type: data FaState l = FaState {label :: l, acceptQ :: Bool, trans :: [[FaState l]]} where l is the type of an arbitrary label. (This will become important a bit later on.) The trans is the adjacency list for state automaton: trans!!i is a list of all states reachable via the symbol i from the current state. (I use a list rather than an array because I typically work with binary alphabets, so the use of Arrays doesn't seem justified.) I make trans!!i a list so that I can represent nondeterminism. Then a finite automaton is merely a list of starting FaStates: type FinAu l = [FaState l] So, for example, an automaton equivalent to the regular expression 0*(0(0+1)*)* could be defined as: dom18 :: FinAu Int dom18 = [one,two] where one = FaState 1 True [[two],[]] two = FaState 2 True [[one],[one]] So, with this machinery in place we can define most of the classical constructions quite easily. For example, to check whether a given string is accepted by an automaton: finAuAcceptStringQ :: FinAu l -> [Int] -> Bool finAuAcceptStringQ startStates string = or [faStateAcceptStringQ s string | s <- startStates] where faStateAcceptStringQ (FaState _ acceptQ _) [] = acceptQ faStateAcceptStringQ (FaState _ _ trans) (a:as) | null followerStates = False | otherwise = or [ faStateAcceptStringQ s as | s <- followerStates ] where followerStates = if a > (length trans) - 1 then [] else trans!!a and the classical nfa-to-dfa power-set (determinization) construction may be implemented quite nicely with: finAuDeterminize :: (Ord l) => FinAu l -> FinAu [l] finAuDeterminize startStates = [f startStates] where f :: (Ord l) => [FaState l] -> FaState [l] f states = FaState label' acceptQ' trans' where label' = sort (map label states) acceptQ' = or (map acceptQ states) trans' = map (singleton.f.concat) (transpose (map trans states)) singleton a = [a] Now, we get to the heart of my question. This definition is quite lovely, recursive and lazy, but it doesn't actually capture the recurrent structure of the resulting automata. That is, if we were to compute: finAuAcceptStringQ (finAuDeterminize dom18) somestring then finAuDeterminize would keep spinning out, generating more and more states, which would actually be equivalent (and, have identical state labels). So an idea is that we can assume the state labels induce an equivalence relation on our states and define something like: finAuConsolidate :: (Eq l) => FinAu l -> FinAu l finAuConsolidate startStates = [ newStates!!i | l <- map label startStates, i <- elemIndices l (map fst assocs) ] where assocs = finAuStateLabelAssoc startStates newStates = map (f.snd) assocs f oldState@(FaState l acceptQ trans) = FaState l acceptQ (map (map (g.label)) trans) g label = case elemIndex label (map fst assocs) of Just i -> newStates!!i Nothing -> error "odd error in finAuConsolidate" provided we have defined: finAuStateLabelAssoc :: (Eq l) => FinAu l -> [(l,FaState l)] finAuStateLabelAssoc startStates = foldl f [] startStates where f knownStatesAssoc state@(FaState label _ trans) | isJust (lookup label knownStatesAssoc) = knownStatesAssoc | otherwise = foldl f ((label,state):knownStatesAssoc) followers where followers = concat trans So this is the heart of my question: is this the best way to proceed? Will the list lookups (!!) of finAuConsolidate be used only once in the construction or will they be perpetually used in something like: finAuAcceptStringQ ((finAuConsolidate.finAuDeterminize) dom18) somestring? That is, how much of a difference would it make if I were to use an Array instead? Thanks, Carl

1 0

edison question
by paul＠theV.net 31 Jul '02

31 Jul '02

I am quite confused with the collection package provided by the edison library. Attached is a sample program, what I wanted to do is to maintain a sorted of Pair of id and time (sorted by time). The error I got is: ghc -package data -package lang test.hs test.hs:17: No instance for `Collection.OrdColl c Pair' arising from use of `Collection.minElem' at test.hs:17 in a pattern binding: Collection.minElem sorted Actually I don't really understand what a class like "OrdColl c a" really means and how to use them. Please help! Regards, .paul.

4 4