| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Unison.Util.Rope
Description
A rope: a sequence of chunks that knows its size in elements (the characters of a text, the bytes of a byte string).
- O(1)
size - amortized O(1)
cons,snoc,uncons,unsnocof a chunk, and so of a short piece of text at either end - O(log n)
index,take,drop, append; close to O(1) near either end
It is the finger tree of Unison.Util.Deque with chunks for elements and sizes counted in what the chunks hold. The middle of the tree is the Deque's own middle, a sequence of nodes that knows the size under each; only the top level, whose items are chunks, is written here.
Invariants:
Synopsis
- chunks :: Rope a -> [a]
- fromChunks :: (Sized a, Semigroup a) => [a] -> Rope a
- singleton :: Sized a => a -> Rope a
- one :: Sized a => a -> Rope a
- map :: (Sized b, Semigroup b) => (a -> b) -> Rope a -> Rope b
- traverse :: (Applicative f, Sized b, Semigroup b) => (a -> f b) -> Rope a -> f (Rope b)
- traverseWithPos_ :: (Applicative f, Sized a) => (Int -> a -> f ()) -> Rope a -> f ()
- null :: Rope a -> Bool
- flatten :: Monoid a => Rope a -> a
- two :: (Sized a, Semigroup a) => Rope a -> Rope a -> Rope a
- cons :: (Sized a, Semigroup a) => a -> Rope a -> Rope a
- uncons :: Sized a => Rope a -> Maybe (a, Rope a)
- snoc :: (Sized a, Semigroup a) => Rope a -> a -> Rope a
- unsnoc :: Sized a => Rope a -> Maybe (Rope a, a)
- index :: (Sized a, Index a ch) => Int -> Rope a -> Maybe ch
- debugDepth :: Rope a -> Int
- extractChunk :: (Monoid a, Sized a, Take a, Drop a) => Int -> Int -> Rope a -> a
- threshold :: Int
- valid :: Sized a => Rope a -> Either String ()
- class Sized a where
- class Take a where
- class Drop a where
- class Reverse a where
- reverse :: a -> a
- class Index a elem where
- unsafeIndex :: Int -> a -> elem
- data Rope a
Documentation
map :: (Sized b, Semigroup b) => (a -> b) -> Rope a -> Rope b Source #
The result is rebuilt from the chunks the function returns, so it is a rope whatever their sizes are.
traverseWithPos_ :: (Applicative f, Sized a) => (Int -> a -> f ()) -> Rope a -> f () Source #
debugDepth :: Rope a -> Int Source #
The number of levels below the top one.
Two chunks next to each other with this many elements or fewer between them are made one chunk.
See https://github.com/unisonweb/unison/pull/1899#discussion_r742953469
The first Int of Deep packs three numbers, as in the Deque: the size
of the rope (bits 8 and up), the number of chunks in the suffix (bits 4 to
7) and in the prefix (bits 0 to 3). The second is the size of the prefix.
The prefix runs front to back and the suffix back to front, so the first
and last chunks of the rope are the heads of the two lists.
Instances
| Foldable Rope Source # | |
Defined in Unison.Util.Rope Methods fold :: Monoid m => Rope m -> m # foldMap :: Monoid m => (a -> m) -> Rope a -> m # foldMap' :: Monoid m => (a -> m) -> Rope a -> m # foldr :: (a -> b -> b) -> b -> Rope a -> b # foldr' :: (a -> b -> b) -> b -> Rope a -> b # foldl :: (b -> a -> b) -> b -> Rope a -> b # foldl' :: (b -> a -> b) -> b -> Rope a -> b # foldr1 :: (a -> a -> a) -> Rope a -> a # foldl1 :: (a -> a -> a) -> Rope a -> a # elem :: Eq a => a -> Rope a -> Bool # maximum :: Ord a => Rope a -> a # | |
| NFData a => NFData (Rope a) Source # | |
Defined in Unison.Util.Rope | |
| (Sized a, Semigroup a) => Monoid (Rope a) Source # | |
| (Sized a, Semigroup a) => Semigroup (Rope a) Source # | |
| (Sized a, Take a, Drop a, Eq a) => Eq (Rope a) Source # | |
| (Sized a, Take a, Drop a, Ord a) => Ord (Rope a) Source # | |
| (Sized a, Semigroup a, Drop a) => Drop (Rope a) Source # | |
| (Sized a, Semigroup a, Reverse a) => Reverse (Rope a) Source # | |
| Sized a => Sized (Rope a) Source # | |
| (Sized a, Semigroup a, Take a) => Take (Rope a) Source # | |
| (Sized a, Index a ch) => Index (Rope a) ch Source # | |
Defined in Unison.Util.Rope Methods unsafeIndex :: Int -> Rope a -> ch Source # | |