Re: [Haskell-cafe] FiniteMap-like module for unordered keys?
On Tue, Nov 09, 2004 at 11:41:49PM +, Jorge Adriano Aires wrote:
Hello,
A hash-table becomes rather useless without mutable state AFAICS.
Without it, one might almost just as well use a list of pairs...
Could you please elaborate? Is there motive why an Hash Table, implemented as
FiniteMap of Lists, for instance, wouldn't be worth to using over a simple
List? (This wouldn't help G. Klyne of course). I've always wondered why a
non-monadic version of is not provided in the GHC libs...
J.A.
I assume you're talking about something like this:
{-# OPTIONS -fglasgow-exts #-}
{- I want a Hashable instance for String ;) -}
import Data.FiniteMap
import Data.HashTable (hashInt, hashString)
import Data.Int (Int32)
class Hashable a where hash :: a - Hash
instance Hashable Int where hash = hashInt
instance Hashable String where hash = hashString
type Hash = Int32
newtype HashTable a b = HT (FiniteMap Hash [b])
emptyHT :: HashTable a b
emptyHT = HT emptyFM
addToHT :: (Hashable a) = HashTable a b - a - b -
HashTable a b
addToHT (HT m) k v
= HT $ addToFM_C (flip (++)) m (hash k) [v]
Of course one could do that, and it would be (expected) O(log n)
instead of O(n), but I doubt I'd really call it a hashtable...
It's more like a variant on (Python's?) Decorate-Sort-Undecorate
pattern. (Replacing a direct comparison by a conversion to
something else which can be compared.) However, it could still be
usefull if there will be lots of lookups and comparing elements
is expensive.
Groetjes,
Remi
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Predicates in HaXml
Hi there, In XSLT there is an XPath function that will let you select a particular node in the current context, for example; xsl:value-of select=team[1] / in Michael Kay's article http://www-106.ibm.com/developerworks/xml/library/x-xslt/?article=xr This selects the first team element in the current context. Is there a work around to get similar functionality from the HaXml library? Many Thanks Tom Spencer ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] One-shot? (was: Global variables and stuff)
On 09 November 2004 11:54, Graham Klyne wrote:
I've not been following the Global variables debate too closely, it
seeming to have something of a religious wars flavour, but I noticed
that an example being proposed was how to achieve a one shot
execution. Here's something I did when working on modifications to
the HaXML parser:
[[
-- Memoization of withSocketsDo to prevent multiple calls.
-- (cf. http://tangentsoft.net/wskfaq/articles/lame-list.html)
socketsInitialized :: Bool
socketsInitialized = unsafePerformIO ( withSocketsDo ( return True ) )
]]
Does it work as I think it does? ARe there any problems I'm
overlooking?
You should add {-# NOINLINE socketsInitialized #-} to be on the safe
side, but in practice GHC won't inline it anyway. The pragma would be
good documentation though.
Cheers,
Simon
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Predicates in HaXml
Tom Spencer [EMAIL PROTECTED] writes: In XSLT there is an XPath function that will let you select a particular node in the current context, for example; xsl:value-of select=team[1] / This selects the first team element in the current context. Is there a work around to get similar functionality from the HaXml library? It's easy to define, yes. Here is an indexing combinator that chooses one result of a CFilter, based on numeric position: index :: Int - CFilter - CFilter index n f = (\c- [ (f c)!!n ]) So for your example, you want to write something like: index 0 (tag team) `o` children This is probably the simplest way of doing your specific task, but there are of course other ways. The tool Xtract has a parser for XPath-like expressions, including more complex predicates, which get translated directly to combinator-style accessors. Unfortunately, the set of combinators used in Xtract is slightly different from those in the rest of HaXml, but they bear a close relationship. You could also use LabelFilters, e.g. (\cs- ... cs!!0 ...) `oo` numbered (tag team `o` children) and doubtless there are other techniques too. Regards, Malcolm ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Space efficiency problem
Hi, This may be silly, but I tried to code a simmulated annealing method to solve the travelling salesman prblem, by adapting the algorithm described in Numerical Recipes in C. Doesn't seem silly so far! :-) The problem is that there are so many iterations, that the program gets killed (kill -9) by the system. I'm not sure what you mean here - I've never encountered a system that kills processes with -9, other than at shutdown time. Are you sure it's -9? How do you know it's because there are too many iterations? I use the State monad to code the optimisation algorithm, and a simple configurations generator for generating the each path. After profiling with -hc, the heap profile shows that the top-level function of the algorithm uses about 40Mb of heap space. That sounds fine to me - I have plenty of programs that use well over 100MB of heap. How much memory do you have? (you say later that it eats up all the available space - I find it hard to believe 40MB is all you have!). How can I improve this awful program? You probably have a space leak. This is usually caused by p or f not forcing the evaluation of all of m0. Since the next m0 depends on the previous one, and so on, this causes all values of m0 to be held in the heap until the end of the program. Add strictness annotations in the right places[*] until heap usage is constant, rather than increasing with each iteration. untilM :: (Monad m) = (m a - m Bool) - (a - m a) - m a - m a untilM p f m0 = do isOver - p m0 if isOver then m0 else untilM p f (m0 = f) [*] of course, this is an entirely non-trivial task, and involves art as well as skill... Hope this helps. Cheers, --KW 8-) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] One-shot? (was: Global variables and stuff)
I have written a small library for supporting one-shot without using
unsfePerformIO...
The library uses SYSV semaphores under linux to make sure the functional
argument of
once is only ever run once. It uses the ProcessID as the key for the
semaphore, so will
even enforce the once-only property accross different Haskell threads.
Some semaphore
functions are also exported, allowing other constraints to be used (for
example, once
only over multiple processes by using a constant ID rather than the
processID.
I have attached the source for the library incase anyone is interested.
If people think
it is useful I could put it up on a website (let me know). Also attached
is an example,
which can be compiled with:
ghc -o test NamedSem.hs Test.hs -package posix
Keean.
{-# OPTIONS -fffi #-}
module NamedSem(once,NamedSem,openNamedSem,closeNamedSem,tasNamedSem) where
import IO
import Foreign.C.Types
import Foreign.Ptr
import Foreign.Storable
import System.Posix.Process
foreign import ccall wrapper mkCallback :: IO CInt - IO (FunPtr (IO CInt))
foreign import ccall unsafe stdlib.h malloc mallocSemOp :: CInt - IO (Ptr SemOp)
foreign import ccall unsafe stdlib.h free freeSemOp :: Ptr SemOp - IO ()
foreign import ccall unsafe stdlib.h atexit atexit :: FunPtr (IO CInt) - IO ()
foreign import ccall unsafe sys/sem.h semget semget :: CInt - CInt - CInt - IO CInt
foreign import ccall unsafe sys/sem.h semop semop :: CInt - Ptr SemOp - CInt - IO CInt
foreign import ccall unsafe sys/sem.h semctl semctl :: CInt - CInt - CInt - IO CInt
data NamedSem = NamedSem CInt deriving Show
data SemOp = SemOp CShort CShort CShort
instance Storable SemOp where
peek p = do { n - peekByteOff p 0; o - peekByteOff p 2; f - peekByteOff p 4; return (SemOp n o f) }
poke p (SemOp n o f) = do { pokeByteOff p 0 n; pokeByteOff p 2 o; pokeByteOff p 4 f }
sizeOf _ = 6
alignment _ = 2
atExit :: IO CInt - IO ()
atExit f = do { g - mkCallback f; atexit g }
openNamedSem :: Int - IO (Maybe NamedSem)
openNamedSem n = do
id - semget (fromIntegral n) 1 0o1660
if id = 0
then do { atExit (semctl id 0 0); return $ Just (NamedSem id) }
else return $ Nothing
closeNamedSem :: NamedSem - IO ()
closeNamedSem (NamedSem id) = do
_ - semctl id 0 0 -- remove semaphore set
return ()
copySemOpList :: Ptr SemOp - [SemOp] - IO Int
copySemOpList op = foldl
(\a b - do { i - a; pokeElemOff op i b; return (i+1) })
(return 0)
applySemOpList :: NamedSem - [SemOp] - IO Bool
applySemOpList (NamedSem id) ol@(o0:_) = bracket
(mallocSemOp $ fromIntegral $ sizeOf o0 * length ol)
freeSemOp $ \op - do
i - copySemOpList op ol
j - semop id op (fromIntegral i)
return (j = 0)
tasNamedSem :: NamedSem - IO Bool
tasNamedSem ns = applySemOpList ns [
SemOp 0 0 0o4000, -- test for zero
SemOp 0 1 0 -- add 1 to semaphore
]
once :: IO () - IO ()
once f = do
i - getProcessID
s - openNamedSem (fromIntegral i)
case s of
Just n - do
b - tasNamedSem n
if b then f else return ()
_ - error unable to get semaphore
{-# OPTIONS -fglasgow-exts #-}
module Main where
import NamedSem
test :: IO ()
test = once $ putStrLn testing
main :: IO ()
main = do
test
test
test
test
test
test
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Space efficiency problem
Keith Wansbrough wrote: The problem is that there are so many iterations, that the program gets killed (kill -9) by the system. I'm not sure what you mean here - I've never encountered a system that kills processes with -9, other than at shutdown time. Are you sure it's -9? If a process exhausts its resource limits (as set with setrlimit()), the kernel will typically kill it with SIGKILL. Also, if the available system-wide memory gets too low, the kernel may start killing of processes, again with SIGKILL. When this occurs, the shell from which the process was spawned will typically write Killed to the terminal. -- Glynn Clements [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] One-shot? (was: Global variables and stuff)
What about the following? It does use unsafePerformIO, but only to
wrap newMVar in this
specific case.
once :: Typeable a = IO a - IO a
once m = let {-# NOINLINE r #-}
r = unsafePerformIO (newMVar Nothing)
in do
y - takeMVar r
x - case y of
Nothing - m
Just x - return x
putMVar r (Just x)
return x
The Typeable constraint forces the return value to be monomorphic,
which prevents the
following from happening (the first line doesn't type check under the
constraint):
let ref = once (newIORef [])
:t ref
ref :: forall a. IO (IORef [a])
ref = flip writeIORef foo
ref = readIORef = (\(x::[Bool]) - print x)
[Illegal instruction
Additionally, I'd like to repeat the point that once (whether
defined my way or Keean's) is
not just a consequence of module initialization; it can actually
replace it in most cases!
For example:
myRef :: IO (IORef Char)
myRef = once (newIORef 'a')
readMyRef :: IO Char
readMyRef = myRef = readIORef
writeMyRef :: Char - IO ()
writeMyRef c = myRef = flip writeIORef c
A library interface might consist of readMyRef and writeMyRef, while hiding
myRef itself from the user. However, what happens in IO stays in the
IO monad; myRef is an action, so the IORef is not initialized until
the first time
that one of read/writeMyRef is called. Indeed, any action wrapped by once
will only be run in the context of the IO monad. IMO, this is the primary
advantage of a function like once over the proposal for top-level
x - someAction
where the exact time someAction is evaluated is unspecified.
Are there any applications of module initialization for which once
does not suffice?
-Judah
On Wed, 10 Nov 2004 17:11:31 +, Keean Schupke
[EMAIL PROTECTED] wrote:
I have written a small library for supporting one-shot without using
unsfePerformIO...
The library uses SYSV semaphores under linux to make sure the functional
argument of
once is only ever run once. It uses the ProcessID as the key for the
semaphore, so will
even enforce the once-only property accross different Haskell threads.
Some semaphore
functions are also exported, allowing other constraints to be used (for
example, once
only over multiple processes by using a constant ID rather than the
processID.
I have attached the source for the library incase anyone is interested.
If people think
it is useful I could put it up on a website (let me know). Also attached
is an example,
which can be compiled with:
ghc -o test NamedSem.hs Test.hs -package posix
Keean.
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] IO and State
Hello,
Concurrency in Haskell (technically GHC) is much like concurrency in
other languages,
in that you fork off threads and do stuff with them, etc.
I think you are perhaps thinking of another kind of concurrency, where
different redexes in
a term are evaluted simultaneously? Here is an example to illustrate
what I was talking about
(the point about stToIO making that one law unsafe)
import Control.Monad.ST
import Data.STRef
import Control.Concurrent
import Control.Monad(when)
reader :: STRef r Int - ST r ()
reader r= do x - readSTRef r
y - readSTRef r
when (x == y) (reader r)
writer :: Int - STRef r Int - ST r ()
writer n r = do writeSTRef r n
writer (n+1) r
main :: IO ()
main= do r - stToIO (newSTRef 0)
forkIO (stToIO (writer 1 r))
stToIO (reader r)
In GHC the whole program stops when the main thread exits.
So if the law I was talking about holds, this program should
never terminate, as it will forever loop in 'reader'.
However since there is a concurrent thread running that can modify
the state, if 'reader' is interrupted between the two readSTRefs
we will get different values for 'x' and 'y' and 'reader' will stop.
I tried that in GHC and it stops after a little while, so the law does
not hold.
What is interesting is that I think the law does hold if
we execute an ST computation using runST, so at least in principle
GHC could perform this optimiziation in such situations.
I think the law holds then, as I think no reference can escape to
concurrent threads,
as if they did their region parameter would become RealWorld, and so
the computation
could not be runSTed.
-Iavor
Graham Klyne wrote:
At 10:38 08/11/04 -0800, Iavor S. Diatchki wrote:
... Now the above law already doesn't hold when all GHC extensions
are used,
as when concurrency is present we cannot assume that nobody modified
the state concurrently.
As a result all pointers in GHC probably behave as if they were
volatile, which is not very nice.
Eek! I find this most worrisome. And I'm not sure that I agree.
I thought that part of the reason for having a monad that it was
threaded in a useful way through the path of a *single* computation
(expression evaluation). If concurrent activities can change that,
then I sense that they're breaking something quite fundamental in the
way Haskell should work.
e.g. in a sequence like:
v :: SomeMonad
v = do { e1 ; e2 ; e3 }
Then I think that exactly the monad created by e1 is passed to e2, and
the result of e2 passed to e3, without any visible external
interference under any circumstance. Concurrency, as I understand it
should apply to Haskell, would allow different elements of that
computation to be performed in different threads/processes, but the
overall result of the computation should not be changeable. Put
another way, the graph reduction model for evaluating a Haskell
program should not change, just the mechanics actual processes (or
processors) actually perform the reduction steps.
Or am I really overlooking something here?
#g
Graham Klyne
For email:
http://www.ninebynine.org/#Contact
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] One-shot? (was: Global variables and stuff)
OK, I'll play again..
On Wednesday 10 Nov 2004 4:39 pm, Judah Jacobson wrote:
What about the following? It does use unsafePerformIO, but only to
wrap newMVar in this
specific case.
once :: Typeable a = IO a - IO a
once m = let {-# NOINLINE r #-}
r = unsafePerformIO (newMVar Nothing)
in do
y - takeMVar r
x - case y of
Nothing - m
Just x - return x
putMVar r (Just x)
return x
My initial feeling is that this kind of swizzles the problem around a bit
and leaves us right back where we started. Pretty much any use of
unsafePerformIO is unsound, though whether or not this has any bad
consequences probably depends a lot on the context it's used what
transformations and optimisations the compiler implements. But I'd
really like to avoid using it at all if possible. Unless I'm
missing something, once is still unsafe (see below..)
Additionally, I'd like to repeat the point that once (whether
defined my way or Keean's) is
not just a consequence of module initialization; it can actually
replace it in most cases!
Hmm, must of missed that..
For example:
myRef :: IO (IORef Char)
myRef = once (newIORef 'a')
readMyRef :: IO Char
readMyRef = myRef = readIORef
writeMyRef :: Char - IO ()
writeMyRef c = myRef = flip writeIORef c
Suppose I had..
myOtherRef :: IO (IORef Char)
myOtherRef = once (newIORef 'a')
There's nothing to stop the compiler doing CSE and producing, in effect..
commonRef :: IO (IORef Char)
commonRef = once (newIORef 'a')
.. followed by substitution of all occurrences of myRef and myOtherRef
with commonRef. I think this would break your programs.
A library interface might consist of readMyRef and writeMyRef, while hiding
myRef itself from the user. However, what happens in IO stays in the
IO monad; myRef is an action, so the IORef is not initialized until
the first time
that one of read/writeMyRef is called. Indeed, any action wrapped by once
will only be run in the context of the IO monad. IMO, this is the primary
advantage of a function like once over the proposal for top-level
x - someAction
where the exact time someAction is evaluated is unspecified.
AFAICS this is only true if the argument to once is something like
(newIORef 'a), in which case the same is also true of the x - newIORef 'a'
solution. Also my own pet solution (SafeIO monad) and Koen's CIO monad
are intended to make it impossible to use constructions whose initial
value depends on when construction occurs.
The intention of the (x - constructor) proposal is more than just
syntactic sugar for (x = unsafePerformIO constructor). I think something
like this really is necessary for a proper solution, though not everybody
agrees what that should be at the moment (and some don't seem agree that
there's a problem in the first place :-)
Hope I haven't missed anything. (I'm sure you'll let me know if you think
I'm being stupid :-)
Regards
--
Adrian Hey
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] One-shot? (was: Global variables and stuff)
Adrian Hey wrote: Suppose I had.. myOtherRef :: IO (IORef Char) myOtherRef = once (newIORef 'a') There's nothing to stop the compiler doing CSE and producing, in effect.. commonRef :: IO (IORef Char) commonRef = once (newIORef 'a') .. followed by substitution of all occurrences of myRef and myOtherRef with commonRef. I think this would break your programs. Well thats certainly not the case with the solution I posted. There are no unsafe operations at all (Well the FFI imports are marked 'unsafe' but that means it is unsafe for them to call back into Haskell)... The solution I posted uses no unsafePerformIO, and the type of action allowed is limited to IO (). In other word all results must be returned as side effects, and the computation either happens (if its the first time) or doesn't happen... Also the semaphore method is very flexible, you can run things exactly twice, or you can reset the semaphore and allow the next init to happen (sort of closing the library and opening it again)... Also once-ness can be restricted accross many domais, thread, process, process-group, multiple sequential executions, once and for all (may only run once on any machine)... Of course in this case it ties up one semaphore indefiniely - but hey its a single bit, and there are 65536x32 semaphores available, so its not really going to cause a problem. Posix(1b) semaphores with string names would be even better (and have a slightly neater interface) but linux does not seem to support sem_open, so I have had to use SYSV semaphores. Keean. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANNOUNCE: Haskell Communities Activities Report (7th ed., November 2004)
Right in time, I am pleased to announce -- on behalf of the many contributers -- that the Haskell Communities and Activities Report (7th edition, November 2004) http://www.haskell.org/communities/ is now available from the Haskell Communities home page in several formats: PDF, for screenreading as well as printing, HTML, for those of you who prefer not to deal with plugins or external viewers, and PostScript, for those of you who have nice quick printers that do not grok PDF. Many thanks go to all the people that contributed to this report, both directly, by sending in descriptions, and indirectly, by doing all the interesting things that are reported. I hope you will find it as interesting a read as we did. If you haven't encountered the Haskell Communities and Activities Reports before, you may like to know that the first of these reports was published in November 2001. Their goal is to improve the communication between the increasingly diverse groups, projects and individuals working on, with, or inspired by Haskell. The idea behind these reports is simple: Every six months, a call goes out to all of you enjoying Haskell to contribute brief summaries of your own area of work. Many of you respond (eagerly, unprompted, and well in time for the actual deadline ;) ) to the call. The editor collects all the contributions into a single report and feeds that back to the community. When we try for the next update, six months from now, you might want to report on your own work, project, research area or group as well. So, please put the following into your diaries now: End of April 2005: target deadline for contributions to the May 2005 edition of the HCA Report Unfortunately, many Haskellers working on interesting projects are so busy with their work that they seem to have lost the time to follow the Haskell related mailing lists and newsgroups, and have trouble even finding time to report on their work. If you are a member, user or friend of a project so burdened, please find someone willing to make time to report and ask them to `register' with the editor for a simple e-mail reminder in the middle of April (you could point us to them as well, and we can then politely ask if they want to contribute, but it might work better if you do the initial asking). Of course, they will still have to find the ten to fifteen minutes to draw up their report, but maybe we can increase our coverage of all that is going on in the community. Feel free to circulate this announcement further in order to reach people who might otherwise not see it. Enjoy! Andres Loeh [EMAIL PROTECTED] [EMAIL PROTECTED] -- Haskell Communities and Activities Report (http://haskell.org/communities) ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FiniteMap-like module for unordered keys?
Ugh, replying to myself...
Obviously, the following contains a few mistakes...:
On Wed, Nov 10, 2004 at 11:34:32AM +0100, R. Turk wrote:
{-# OPTIONS -fglasgow-exts #-}
{- I want a Hashable instance for String ;) -}
import Data.FiniteMap
import Data.HashTable (hashInt, hashString)
import Data.Int (Int32)
class Hashable a where hash :: a - Hash
instance Hashable Int where hash = hashInt
instance Hashable String where hash = hashString
type Hash = Int32
newtype HashTable a b = HT (FiniteMap Hash [b])
newtype HashTable a b = HT (FiniteMap Hash [(a,b)])
emptyHT :: HashTable a b
emptyHT = HT emptyFM
addToHT :: (Hashable a) = HashTable a b - a - b - HashTable a b
addToHT (HT m) k v
= HT $ addToFM_C (flip (++)) m (hash k) [v]
addToHT (HT m) k v
= HT $ addToFM_C (flip (++)) m (hash k) [(k,v)]
--
Nobody can be exactly like me. Even I have trouble doing it.
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] One-shot? (was: Global variables and stuff)
Hi, Here's another completely safe (and simpler way) to limit a computation to only happen once: once' :: IO () - IO () once' f = do k - getProcessID a - getEnv (showString MyApp.Main $ show k) case a of Just _ - return () _ - do f setEnv (showString MyApp.Main $ show k) False Actually both this and the semaphore example show that there is probably an alternative to allowing top-level '-' type definitions - and that would be to have named-MVars in Haskell. It would be quite easy to code these as a small C library - and then FFI import the bindings to Haskell. I don't know whether from a 'purists' point of view whether this represents anything better than module-initialisations - but it does remove the diamond-inheritance style problem you get (if B imports A and C imports A and Main imports B and C, does A's init get run twice? are there two copies of the variables, each initialised once, or one copy that gets initialised twice?). But either way the idea could be implemented without requiring changes to the language spec or the compilers, and would just be a library which you could use. Keean. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] FiniteMap-like module for unordered keys?
On Tue, Nov 09, 2004 at 11:41:49PM +, Jorge Adriano Aires wrote: Hello, A hash-table becomes rather useless without mutable state AFAICS. Without it, one might almost just as well use a list of pairs... Could you please elaborate? Is there motive why an Hash Table, implemented as FiniteMap of Lists, for instance, wouldn't be worth to using over a simple List? (This wouldn't help G. Klyne of course). I've always wondered why a non-monadic version of is not provided in the GHC libs... Sometimes you are willing to pay an arbitrary setup cost for very fast future lookups. for things like symbols tables for instance. This is where a constant non-monadic hash would be quite useful, especially since you know it is immutable you can choose things like the number of buckets more inteligently. or if you wanted to go crazy, generate a perfect-hash on the fly. Binary trees are good at a lot of things, but their memory locality is pretty cruddy for lookups or when your key comparason operator is slow. (I am aware of the absurdity of thinking about memory locality with a dynamic-dispatch STG-machine, but old habits from my Kernel programming days die hard :) ) John -- John Meacham - repetae.netjohn ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
