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
2010/7/16 wren ng thornton w...@freegeek.org:
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
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
2010/7/15 Jake McArthur jake.mcart...@gmail.com:
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 Thu, Jul 15, 2010 at 4:30 AM, Stephen Tetley
stephen.tet...@gmail.com wrote:
2010/7/15 Jake McArthur jake.mcart...@gmail.com:
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. ;)
Stephen Tetley stephen.tet...@gmail.com writes:
2010/7/15 Jake McArthur jake.mcart...@gmail.com:
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,
2010/7/15 Serguey Zefirov sergu...@gmail.com:
2010/7/14 Sergey Mironov ier...@gmail.com:
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
15 июля 2010 г. 2:01 пользователь Victor Gorokhov m...@rkit.pp.ru написал:
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
2010/7/15 Sergey Mironov ier...@gmail.com:
2010/7/15 Serguey Zefirov sergu...@gmail.com:
2010/7/14 Sergey Mironov ier...@gmail.com:
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
On 07/15/2010 02:30 AM, Stephen Tetley wrote:
2010/7/15 Jake McArthurjake.mcart...@gmail.com:
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,
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,
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
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
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
2010/7/14 Sergey Mironov ier...@gmail.com:
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
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
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 better,
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
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
hi
I was curious as to whether my implementation of a Rose Tree and a sumTree
function was correct. The aumTree adds up the elements of a tree.
data Tree a = Leaf a | Node [Tree a]
sumTree :: Tree Int - Int
sumTree (Node []) = 0
sumTree (Node xs) = sum (map sumTree xs)
The problem with
There are a few different kinds of trees, but if you only need to
store data on the leaves, that representation will work. As for your
sumTree function, you are indeed missing a case...consider sumTree
(Leaf 3)! Once you deal with that case, the other two can actually be
combined (since sum [] =
Hi everyone
I'm trying to write a piece of Haskell code, but for some reason I
can't make it working. I'm asking for your help in finding a bug in
this code:
import Data.Tree
import Data.List
expandTree :: Int - [(Int,Int)] - ((Tree Int),[(Int,Int)])
expandTree rootLabel [] = ((Node
Am Dienstag, 26. Februar 2008 18:29 schrieb Krzysztof Skrzętnicki:
Hi everyone
I'm trying to write a piece of Haskell code, but for some reason I
can't make it working. I'm asking for your help in finding a bug in
this code:
import Data.Tree
import Data.List
expandTree :: Int -
Adrian Neumann wrote:
data Tree a = Leaf a | Node a [Tree a]
example: given a tree t and two nodes u,v, find the
first common ancestor. In Java this is really simple,
because each node has a parent reference...
In Haskell however the best way I've come up with so
far is doing a BFS and
Adrian Neumann:
data Tree a = Leaf a | Node a [Tree a]
example: given a tree t and two nodes u,v, find the
first common ancestor.
The following solves what I think is a generalisation of this problem.
That is, given a tree and a predicate on its elements, return the
smallest subtree
On Mon, 2007-12-03 at 16:56 +0200, Yitzchak Gale wrote:
Adrian Neumann wrote:
data Tree a = Leaf a | Node a [Tree a]
example: given a tree t and two nodes u,v, find the
first common ancestor. In Java this is really simple,
because each node has a parent reference...
In Haskell however
Good morning,
as an exercise for my Algorithms and Programming course I have to
program a couple of simple functions over trees. Until now everything
we did in Java could be done in Haskell (usually much nicer too)
using the naive
data Tree a = Leaf a | Node a [Tree a]
But now the
aneumann:
Good morning,
as an exercise for my Algorithms and Programming course I have to
program a couple of simple functions over trees. Until now everything
we did in Java could be done in Haskell (usually much nicer too)
using the naive
data Tree a = Leaf a | Node a [Tree a]
On Mon, Dec 03, 2007 at 08:13:57AM +0100, Adrian Neumann wrote:
Good morning,
as an exercise for my Algorithms and Programming course I have to program a
couple of simple functions over trees. Until now everything we did in Java
could be done in Haskell (usually much nicer too) using the
29 matches
Mail list logo
