Jan-Willem Maessen wrote:
As you observe, it's really down to constant factors. The reason
IntMap (or any digital trie) is so interesting is that it is simple
enough that the constant factors are quite good---in particular we
don't waste a lot of time figuring out if we're going to need to
rearr
2010/7/16 wren ng thornton :
> Jake McArthur wrote:
>>
>> On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
From the docs, lookup is O(min(n,W))
>>>
>>> Actually worse than O(log n).
>>
>> Perhaps I am misunderstanding you, but O(min(n,W)) is either better than
>> or the same as O(log n), de
Hello Jake,
Friday, July 16, 2010, 7:26:22 AM, you wrote:
> Excluding DiffArray under certain usage patterns of course, but
> DiffArray is slow for unknown reasons besides algorithmic complexity.
unknown reason = MVar usage
ArrayRef library contains parameterized DiffArray implementation that
m
Jake McArthur wrote:
On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
From the docs, lookup is O(min(n,W))
Actually worse than O(log n).
Perhaps I am misunderstanding you, but O(min(n,W)) is either better than
or the same as O(log n), depending on how you look at things, but I
don't see any w
On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
Thanks for an example! Probably, one can think about using Arrays
instead of Map or IntMap in order to achieve 'true' O(1) in pure. But
I suppose that there are some trouble with array expanding. Or
somebody would already make it.
Pure arrays hav
Thanks for an example! Probably, one can think about using Arrays
instead of Map or IntMap in order to achieve 'true' O(1) in pure. But
I suppose that there are some trouble with array expanding. Or
somebody would already make it.
Pure arrays have O(n) modification time.
From the docs, lo
On 07/15/2010 02:30 AM, Stephen Tetley wrote:
2010/7/15 Jake McArthur:
On 07/14/2010 05:01 PM, Victor Gorokhov wrote:
You can implement pure pointers on top of Data.Map with O(log n) time
Or on top of Data.IntMap with O(1) time. ;)
Unlikely...
From the docs, lookup is O(min(n,W))
Exact
2010/7/15 Sergey Mironov :
> 2010/7/15 Serguey Zefirov :
>> 2010/7/14 Sergey Mironov :
>>> Hi cafe! I have a question of C-to-Haskell type:)
>>>
>>> Imagine web application wich allows users to browse some shared
>>> filesystem located at the server.
>>> Application stores every users's position wi
15 июля 2010 г. 2:01 пользователь Victor Gorokhov написал:
> You can implement pure pointers on top of Data.Map with O(log n) time:
>
> {-# LANGUAGE ExistentialQuantification #-}
> import Data.Map ( Map )
> import qualified Data.Map as Map
> import Data.Typeable
> import Control.Monad.State
> impo
2010/7/15 Serguey Zefirov :
> 2010/7/14 Sergey Mironov :
>> Hi cafe! I have a question of C-to-Haskell type:)
>>
>> Imagine web application wich allows users to browse some shared
>> filesystem located at the server.
>> Application stores every users's position within that filesystem
>> (current di
Stephen Tetley writes:
> 2010/7/15 Jake McArthur :
>> On 07/14/2010 05:01 PM, Victor Gorokhov wrote:
>>>
>>> You can implement pure pointers on top of Data.Map with O(log n) time
>>
>> Or on top of Data.IntMap with O(1) time. ;)
>
> Unlikely...
>
>>From the docs, lookup is O(min(n,W))
Yeah, I wa
On Thu, Jul 15, 2010 at 4:30 AM, Stephen Tetley
wrote:
> 2010/7/15 Jake McArthur :
>> On 07/14/2010 05:01 PM, Victor Gorokhov wrote:
>>>
>>> You can implement pure pointers on top of Data.Map with O(log n) time
>>
>> Or on top of Data.IntMap with O(1) time. ;)
>
> Unlikely...
>
> >From the docs, l
2010/7/15 Jake McArthur :
> On 07/14/2010 05:01 PM, Victor Gorokhov wrote:
>>
>> You can implement pure pointers on top of Data.Map with O(log n) time
>
> Or on top of Data.IntMap with O(1) time. ;)
Unlikely...
>From the docs, lookup is O(min(n,W))
___
On 07/14/2010 05:01 PM, Victor Gorokhov wrote:
You can implement pure pointers on top of Data.Map with O(log n) time
Or on top of Data.IntMap with O(1) time. ;)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/list
You can implement pure pointers on top of Data.Map with O(log n) time:
{-# LANGUAGE ExistentialQuantification #-}
import Data.Map ( Map )
import qualified Data.Map as Map
import Data.Typeable
import Control.Monad.State
import Data.Maybe
type PointerSpace = Map Int PackedValue
newtype Pointer a =
Or you can get the best of all worlds by combining all three!
data User = User
{userNext :: IORef (MVar (TVar User)))
,userPrev :: IORef (MVar (TVar User)))
}
On 07/14/10 14:39, Andrew Coppin wrote:
> Serguey Zefirov wrote:
>> Use IORef. ;)
>>
>> PS
>> MVar is
Serguey Zefirov wrote:
Use IORef. ;)
PS
MVar is better, actually
TVar is better still. ;-)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
2010/7/14 Sergey Mironov :
> Hi cafe! I have a question of C-to-Haskell type:)
>
> Imagine web application wich allows users to browse some shared
> filesystem located at the server.
> Application stores every users's position within that filesystem
> (current directory or file).
>
> In C this can
Hi cafe! I have a question of C-to-Haskell type:)
Imagine web application wich allows users to browse some shared
filesystem located at the server.
Application stores every users's position within that filesystem
(current directory or file).
In C this can be implemented with the help of following
19 matches
Mail list logo