data-inttrie-0.1.4: A simple lazy, infinite trie from integers

Copyright | (c) Luke Palmer 2010
License | BSD3
Maintainer | Luke Palmer <lrpalmer@gmail.com>
Stability | experimental
Portability | Haskell 2010
Safe Haskell | Safe-Inferred
Language | Haskell2010

Data.IntTrie

Description

Provides a minimal infinite, lazy trie for integral types. It intentionally leaves out ideas such as delete and emptiness so that it can be used lazily, eg. as the target of an infinite foldr. Essentially its purpose is to be an efficient implementation of a function from integral type, given point-at-a-time modifications.

Synopsis

- data IntTrie a
- identity :: (Num a, Bits a) => IntTrie a
- apply :: (Ord b, Num b, Bits b) => IntTrie a -> b -> a
- modify :: (Ord b, Num b, Bits b) => b -> (a -> a) -> IntTrie a -> IntTrie a
- modify' :: (Ord b, Num b, Bits b) => b -> (a -> a) -> IntTrie a -> IntTrie a
- overwrite :: (Ord b, Num b, Bits b) => b -> a -> IntTrie a -> IntTrie a
- mirror :: IntTrie a -> IntTrie a
- modifyAscList :: (Ord b, Num b, Bits b) => [(b, a -> a)] -> IntTrie a -> IntTrie a
- modifyDescList :: (Ord b, Num b, Bits b) => [(b, a -> a)] -> IntTrie a -> IntTrie a

# Documentation

data IntTrie a Source #

A trie from integers to values of type a.

Semantics: [[IntTrie a]] = Integer -> a

#### Instances

Instances details

Applicative IntTrie Source # |
Instance details Defined in Data.IntTrie Methods pure :: a -> IntTrie a Source # (<*>) :: IntTrie (a -> b) -> IntTrie a -> IntTrie b Source # liftA2 :: (a -> b -> c) -> IntTrie a -> IntTrie b -> IntTrie c Source # (*>) :: IntTrie a -> IntTrie b -> IntTrie b Source # (<*) :: IntTrie a -> IntTrie b -> IntTrie a Source #
Functor IntTrie Source # |
Instance details Defined in Data.IntTrie Methods fmap :: (a -> b) -> IntTrie a -> IntTrie b Source # (<$) :: a -> IntTrie b -> IntTrie a Source #
Monoid a => Monoid (IntTrie a) Source # |
Instance details Defined in Data.IntTrie Methods mempty :: IntTrie a Source # mappend :: IntTrie a -> IntTrie a -> IntTrie a Source # mconcat :: [IntTrie a] -> IntTrie a Source #
Semigroup a => Semigroup (IntTrie a) Source # |
Instance details Defined in Data.IntTrie Methods (<>) :: IntTrie a -> IntTrie a -> IntTrie a Source # sconcat :: NonEmpty (IntTrie a) -> IntTrie a Source # stimes :: Integral b => b -> IntTrie a -> IntTrie a Source #

identity :: (Num a, Bits a) => IntTrie a Source #

The identity trie.

    apply identity = id

apply :: (Ord b, Num b, Bits b) => IntTrie a -> b -> a Source #

Apply the trie to an argument. This is the semantic map.

modify :: (Ord b, Num b, Bits b) => b -> (a -> a) -> IntTrie a -> IntTrie a Source #

Modify the function at one point

    apply (modify x f t) i | i == x = f (apply t i)
                           | otherwise = apply t i

modify' :: (Ord b, Num b, Bits b) => b -> (a -> a) -> IntTrie a -> IntTrie a Source #

Modify the function at one point (strict version)

overwrite :: (Ord b, Num b, Bits b) => b -> a -> IntTrie a -> IntTrie a Source #

Overwrite the function at one point

    overwrite i x = modify i (const x)

mirror :: IntTrie a -> IntTrie a Source #

Negate the domain of the function

    apply (mirror t) i = apply t (-i)
    mirror . mirror = id

modifyAscList :: (Ord b, Num b, Bits b) => [(b, a -> a)] -> IntTrie a -> IntTrie a Source #

Modify the function at a (potentially infinite) list of points in ascending order

    modifyAscList [(i0, f0)..(iN, fN)] = modify i0 f0 . ... . modify iN fN

modifyDescList :: (Ord b, Num b, Bits b) => [(b, a -> a)] -> IntTrie a -> IntTrie a Source #

Modify the function at a (potentially infinite) list of points in descending order