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

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

Documentation

data IntTrie a Source

A trie from integers to values of type a.

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

Instances

Functor IntTrie Source
Applicative IntTrie Source
Monoid a => Monoid (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