haskell / critbit Goto Github PK
View Code? Open in Web Editor NEWA Haskell implementation of crit-bit trees.
License: BSD 2-Clause "Simplified" License
A Haskell implementation of crit-bit trees.
License: BSD 2-Clause "Simplified" License
Documentation states that Empty
allowed only as a root of the tree. Both performance and functions (e. g. binarySetOpWithKey) depends on this invariant. But, now it is not checked by tests at all.
Unfortunately, there is no way to write such check function using public API only.
AFAIU there are two ways to solve this problem:
I think first variant is better.
As reported by criterion.
critbit:
benchmarking bytestring/alter/critbit
mean: 587.6628 ns
std dev: 25.92060 ns
map:
benchmarking bytestring/alter/map
mean: 481.7831 ns
std dev: 13.77285 ns
Hoping that @archblob can take a look.
Or get the key of specified position
From what I understand, and if I'm not mistaken, the complexity of union is O(n*log m) where n is the size of the second map and m the size of the first one.
Can't we do better ? I've tried to implement the difference function and I have not found a way to do it better.
member
is marked INLINABLE while notMember
is marked INLINE, despite both habing essentially identical structure. Other things that are INLINE while similar functions are INLINABLE: foldlWithKeyWith
, foldrWithKeyWith
(in these cases I would expect the API wrapper functions to be INLINE and the longer core function INLINABLE, if anything), updateExtremity
.
Functions missing any such pragma that I think may want one: null
, empty
, elems
, assocs
, keys
, unionWith
, unionWithKey
, unions
, unionsWith
, intersectionWithKey
, map
, mapKeys
, toAscList
, toDescList
, filter
.
Is there some reason to these decisions that I have overlooked?
Are you planning a strict implementation of the functions ?
haskell-platform 2012.4.0.0 has text == 0.11.2.3
https://github.com/haskell/haskell-platform/blob/master/haskell-platform.cabal#L91
Changing the requirement to >= 0.11.2.3 appears to build and pass tests just fine here.
The benchmarks don't build with 2012.4.0.0 for at least the following reasons:
import Prelude hiding (catch)
No instance for (NFData B.ByteString)
, which is easy to define (since they're strict) but I don't know what commotion it would cause with a newer version of bytestringimport System.Environment (getEnv)
lookupEnv :: String -> IO (Maybe String)
lookupEnv name = (Just <$> getEnv name) `catch` \(_::IOError) -> return Nothing
instance NFData B.ByteString
I am currently implementing unionWithKey.
The instructions say to 'git clone git://github.com/bos/critbit'. Should we not fork and clone our own repository?
In the definition of delete
,
go (Leaf lk _) cont
| k == lk = cont Empty
becomes
go (Leaf lk lv) cont
| k == lk = case f k lv of
Just lv' -> cont (Leaf lk lv')
Nothing -> cont Empty
since - unlike with Data.Map - we don't rebalance the tree on a deletion. Then delete = updateWithKey (const (const Nothing))
.
Hopefully this isn't too hard on GHC. I'll look at this unless someone else is interested.
Current imlementation of split
and splitLookup
is invalid.
Call split "bb" $ fromList [("aa", 1), ("ac", 2), ("ad", 3)]
returns (fromList [("aa",1),("ac",2)],fromList [("ad",3)])
instead of (fromList [("aa",1),("ac",2), ("ad",3)],fromList [])
.
The same arguments demonstrate bug in splitLookup
.
Hi,
Would it be possible to add critbit
on Stackage ?
Or would it be better if it is added by another package maintainer, one that uses it as a dependency ?
Cheers,
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.