Serguey Zefirov wrote:

Use IORef. ;)

PS MVar is better, actually

TVar is better still. ;-)

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 directory or file).

In C this can be implemented with the help of following data types:

Any ideas?

Use IORef. ;)

PS MVar is better, actually.

Somehow I forgot about them:) Code will turn into something like data TreeNodeData = File | Dir (IORef TreeNode) data TreeNode = TreeNode { next :: Maybe (IORef TreeNode), prev :: Maybe (IORef TreeNode), up :: Maybe (IORef TreeNode), -- missed it in original C example payload :: TreeNodeData } data User = User { position :: IORef TreeNode, -- ... } It really should work! (we don't take multithreading issues into account for now) Slightly annoying thing is that 1-to-1 mapping from C to Haskell also forces programmer to perform C-like low-level pointer linking. -- Thanks, Sergey

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))

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 was trying to work out how the O(1) time worked as well... -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

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 import Data.Maybe

type PointerSpace = Map Int PackedValue newtype Pointer a = Pointer Int data PackedValue = forall a. Typeable a => PackedValue a

readPointer :: Pointer a -> State PointerSpace a readPointer ( Pointer key ) =  do  space <- get  return $ fromJust $ cast $ Map.find key space

writePointer :: a -> Pointer a -> State PointerSpace () writePointer a ( Pointer key ) = do  space <- get  put $ Map.insert key ( PackedValue a ) space

newPointer :: a -> State PointerSpace ( Pointer a ) newPointer a = do  space <- get  let key = findEmptyKey space -- implement it yourself     p = Pointer key  writePointer a p  return p

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. -- Thanks, Sergey

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 have O(n) modification time.

Excluding DiffArray under certain usage patterns of course, but DiffArray is slow for unknown reasons besides algorithmic complexity.

...

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 way that the former could be *worse* than the latter. - Jake

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), depending on how you look at things, but I don't see any way that the former could be *worse* than the latter.

For n < W: min(n,W) > log n

So, when you can guarantee that n < W ---which is almost always the case for IntMap---, then O(min(n,W)) is linear and therefore worse than O(log n).

Indeed---though you see worst-case behavior only for carefully-chosen key sets (eg successive powers of 2). If the n values in an IntMap are, say, consecutive or nearly-consecutive, we obtain a log n bound. I suspect in practice most programmers will see logarithmic behavior.

...

But even so, if your constant factors are k << c, then k*n < c*log n is perfectly possible for all n < W, and therefore what matters in the real world here is the constant factors. The reason why is that for asymptotic purposes O(min(n,W)) and O(log n) belong to the same class of functions between constant and linear, so they're effectively the same (in asymptotic-land).

The argument for constant-time IntMap performance is essentially similar to the following argument: There are balanced trees that provide an O(lg n) bound on tree depth for a tree containing n elements. Our computer has only k bits of address space and therefore the number of elements in any in-memory tree is O(k). Thus there is a constant (and smallish) upper bound on tree depth, O(lg k). Therefore every balanced tree implementation offers constant-time access. 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 rearrange the tree structure on the fly. That turns out to amortize quite a few extra level traversals in a lot of settings. It also offers really elegant implementations of union and unions. Whether that means they're quickish I leave to the benchmarkers. -Jan-Willem Maessen

-- Live well, ~wren _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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 may be specialized either to MVar or IORef usage -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com