Hackage :: [Package]

mutable-fenwick: Mutable Fenwick trees

[ data, library, mit ] [ Propose Tags ] [ Report a vulnerability ]

This package provides an implementation of mutable Fenwick trees.

It is maximally generic. Each operation of Fenwick tree is implemented using a subset of constraints from Semigroup, Monoid, or Commutative, chosen based on the nature of each operation.

It is fast and efficient. With ArrayC and VectorC from this package, it is possible to use unboxed arrays and vectors for newtypes that implement a custom algebra (e.g. Sum, Product or Xor). An implementation using this library can be as fast as a C/C++ implementation.

[Skip to Readme]

Modules

  • Data
    • Array
      • Data.Array.ArrayC
    • Fenwick
      • Data.Fenwick.Array
      • Data.Fenwick.Vector
    • Vector
      • Data.Vector.VectorC

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0
Change log CHANGELOG.md
Dependencies array (>=0.5.4 && <0.6), base (>=4.17.2 && <4.18), commutative-semigroups (>=0.2.0 && <0.3), monoid-subclasses (>=1.2.6 && <1.3), vector (>=0.13.1 && <0.14) [details]
Tested with ghc ==9.2.8 || ==9.4.8
License MIT
Copyright (c) Parsa Alizade, 2025
Author Parsa Alizadeh
Maintainer parsa.alizadeh1@gmail.com
Category Data
Home page https://github.com/ParsaAlizadeh/fenwick-tree
Bug tracker https://github.com/ParsaAlizadeh/fenwick-tree/issues
Source repo head: git clone https://github.com/ParsaAlizadeh/fenwick-tree.git
Uploaded by aaparsa at 2025-05-22T11:35:30Z
Distributions
Downloads 2 total (2 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs not available [build log]
All reported builds failed as of 2025-05-22 [all 2 reports]

Readme for mutable-fenwick-0.1.0.0

[back to package description]

mutable-fenwick

This package provides an implementation of mutable Fenwick trees in Haskell.

Features

It is maximally generic. Each operation of Fenwick tree is implemented using a subset of constraints from Semigroup, Monoid, or Commutative, chosen carefully based on the nature of each operation. This is mostly possible due to how Haskell typeclasses work, and provides different functionality based on the constraints provided by the underlying element type.

It is fast and efficient. Every operation is marked as inline, meaning that they will be optimized for the given element type. With ArrayC and VectorC from this package, it is possible to use unboxed arrays and vectors for newtypes that implement a custom algebra (e.g. Sum, Product or Xor). An implementation using this library can be as fast as a C/C++ implementation.

It is the only Haskell library (I believe, as of this date) that provides Fenwick trees.

  • The FenwickTree package is more similar to a Segment tree, and it does not have a generic interface for the data structure.
  • The binary-indexed-tree package has an interface for ST monad, but the implementation is only limited to Sum monoid.