mono-traversable 0.8.0.1 → 0.9.0
raw patch · 3 files changed
+162/−11 lines, 3 files
Files
- ChangeLog.md +4/−0
- mono-traversable.cabal +1/−1
- src/Data/MinLen.hs +157/−10
ChangeLog.md view
@@ -1,3 +1,7 @@+## 0.9.0++* Better fixity for mlcons [#56](https://github.com/snoyberg/mono-traversable/issues/56)+ ## 0.8.0.1 README updates
mono-traversable.cabal view
@@ -1,5 +1,5 @@ name: mono-traversable-version: 0.8.0.1+version: 0.9.0 synopsis: Type classes for mapping, folding, and traversing monomorphic containers description: Monomorphic variants of the Functor, Foldable, and Traversable typeclasses. If you understand Haskell's basic typeclasses, you understand mono-traversable. In addition to what you are used to, it adds on an IsSequence typeclass and has code for marking data structures as non-empty. homepage: https://github.com/snoyberg/mono-traversable
src/Data/MinLen.hs view
@@ -9,6 +9,8 @@ {-# LANGUAGE FlexibleInstances #-} module Data.MinLen ( -- * Type level naturals+ -- ** Peano numbers+ -- $peanoNumbers Zero (..) , Succ (..) , TypeNat (..)@@ -49,8 +51,16 @@ import Data.GrowingAppend import Control.Monad (liftM) --- Type level naturals+-- $peanoNumbers+-- <https://wiki.haskell.org/Peano_numbers Peano numbers> are a simple way to represent natural numbers (0, 1, 2...) using only a 'Zero' value and a successor function ('Succ'). Each application of 'Succ' increases the number by 1, so @Succ Zero@ is 1, @Succ (Succ Zero)@ is 2, etc.++-- | 'Zero' is the base value for the Peano numbers. data Zero = Zero++-- | 'Succ' represents the next number in the sequence of natural numbers. It takes a @nat@ (a natural number) as an argument.+-- 'Zero' is a @nat@, allowing @Succ Zero@ to represent 1. +-- 'Succ' is also a @nat@, so it can be applied to itself, allowing @Succ (Succ Zero)@ to represent 2, +-- @Succ (Succ (Succ Zero))@ to represent 3, and so on. data Succ nat = Succ nat class TypeNat nat where@@ -63,15 +73,40 @@ toValueNat (Succ nat) = 1 + toValueNat nat typeNat = Succ typeNat +-- | Adds two type-level naturals. See the 'mlappend' type signature for an example. type family AddNat x y type instance AddNat Zero y = y type instance AddNat (Succ x) y = AddNat x (Succ y) +-- | Calculates the maximum of two type-level naturals. See the 'mlunion' type signature for an example. type family MaxNat x y type instance MaxNat Zero y = y type instance MaxNat x Zero = x type instance MaxNat (Succ x) (Succ y) = Succ (MaxNat x y) +-- | A wrapper around a container which encodes its minimum length in the type system.+-- This allows functions like 'head' and 'maximum' to be made safe without using 'Maybe'.+-- +-- The length, @nat@, is encoded as a <https://wiki.haskell.org/Peano_numbers Peano number>,+-- which starts with the 'Zero' constructor and is made one larger with each application +-- of 'Succ' ('Zero' for 0, @Succ Zero@ for 1, @Succ (Succ Zero)@ for 2, etc.).+-- Functions which require atleast one element, then, are typed with @Succ nat@,+-- where @nat@ is either 'Zero' or any number of applications of 'Succ':+--+-- > head :: MonoTraversable mono => MinLen (Succ nat) mono -> Element mono+--+-- The length is also a phantom type, i.e. it is only used+-- on the left hand side of the type and doesn't exist at runtime.+-- Notice how @Succ Zero@ isn't included in the printed output:+--+-- > > toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])+-- > Just (MinLen {unMinLen = [1,2,3]})+--+-- You can still use GHCI's @:i@ command to see the phantom type information:+--+-- > > let xs = 1 `mlcons` toMinLenZero []+-- > > :i xs+-- > xs :: Num t => MinLen (Succ Zero) [t] newtype MinLen nat mono = MinLen { unMinLen :: mono } deriving (Eq, Ord, Read, Show, Data, Typeable, Functor) type instance Element (MinLen nat mono) = Element mono@@ -109,9 +144,29 @@ natProxy :: TypeNat nat => MinLen nat mono -> nat natProxy _ = typeNat -toMinLenZero :: mono -> MinLen Zero mono+-- | Types a container as having a minimum length of zero. This is useful when combined with other 'MinLen' +-- functions that increase the size of the container.+--+-- ==== __Examples__+--+-- > > 1 `mlcons` toMinLenZero []+-- > MinLen {unMinLen = [1]}+toMinLenZero :: (MonoFoldable mono) => mono -> MinLen Zero mono toMinLenZero = MinLen +-- | Attempts to add a 'MinLen' constraint to a 'MonoFoldable'.+--+-- ==== __Examples__+--+-- > > let xs = toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])+-- > > xs+-- > Just (MinLen {unMinLen = [1,2,3]})+-- >+-- > > :i xs+-- > xs :: Maybe (MinLen (Succ Zero) [Int])+--+-- > > toMinLen [] :: Maybe (MinLen (Succ Zero) [Int])+-- > Nothing toMinLen :: (MonoFoldable mono, TypeNat nat) => mono -> Maybe (MinLen nat mono) toMinLen mono = case ocompareLength mono (toValueNat nat :: Int) of@@ -124,45 +179,119 @@ -- | Although this function itself cannot cause a segfault, it breaks the -- safety guarantees of @MinLen@ and can lead to a segfault when using -- otherwise safe functions.+--+-- ==== __Examples__+--+-- > > let xs = unsafeToMinLen [] :: MinLen (Succ Zero) [Int]+-- > > length xs+-- > 0+-- > > head xs+-- > *** Exception: Data.MonoTraversable.headEx: empty unsafeToMinLen :: mono -> MinLen nat mono unsafeToMinLen = MinLen +infixr 5 `mlcons`++-- | Adds an element to the front of a list, increasing its minimum length by 1.+--+-- ==== __Examples__+--+-- > > let xs = unsafeToMinLen [1,2,3] :: MinLen (Succ Zero) [Int]+-- > > 0 `mlcons` xs+-- > MinLen {unMinLen = [0,1,2,3]} mlcons :: IsSequence seq => Element seq -> MinLen nat seq -> MinLen (Succ nat) seq mlcons e (MinLen seq) = MinLen (cons e seq) {-# INLINE mlcons #-} +-- | Concatenates two sequences, adding their minimum lengths together.+--+-- ==== __Examples__+--+-- > > let xs = unsafeToMinLen [1,2,3] :: MinLen (Succ Zero) [Int]+-- > > xs `mlappend` xs+-- > MinLen {unMinLen = [1,2,3,1,2,3]} mlappend :: IsSequence seq => MinLen x seq -> MinLen y seq -> MinLen (AddNat x y) seq mlappend (MinLen x) (MinLen y) = MinLen (x `mappend` y) {-# INLINE mlappend #-} +-- | Returns the first element. head :: MonoTraversable mono => MinLen (Succ nat) mono -> Element mono head = headEx . unMinLen {-# INLINE head #-} +-- | Returns the last element. last :: MonoTraversable mono => MinLen (Succ nat) mono -> Element mono last = lastEx . unMinLen {-# INLINE last #-} +-- | Returns all but the first element of a sequence, reducing its 'MinLen' by 1.+--+-- ==== __Examples__+-- +-- > > let xs = toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])+-- > > fmap initML xs+-- > Just (MinLen {unMinLen = [1,2]}) tailML :: IsSequence seq => MinLen (Succ nat) seq -> MinLen nat seq tailML = MinLen . tailEx . unMinLen +-- | Returns all but the last element of a sequence, reducing its 'MinLen' by 1.+--+-- ==== __Examples__+--+-- > > let xs = toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])+-- > > fmap initML xs+-- > Just (MinLen {unMinLen = [1,2]}) initML :: IsSequence seq => MinLen (Succ nat) seq -> MinLen nat seq initML = MinLen . initEx . unMinLen +-- | Joins two semigroups, keeping the larger 'MinLen' of the two.+--+-- ==== __Examples__+-- +-- > > let xs = unsafeToMinLen [1] :: MinLen (Succ Zero) [Int]+-- > > let ys = xs `mlunion` xs+-- > > ys+-- > MinLen {unMinLen = [1,1]}+-- >+-- > > :i ys+-- > ys :: MinLen (Succ Zero) [Int] mlunion :: GrowingAppend mono => MinLen x mono -> MinLen y mono -> MinLen (MaxNat x y) mono mlunion (MinLen x) (MinLen y) = MinLen (x <> y) -+-- | Maps a function that returns a 'Semigroup' over the container, then joins those semigroups together.+--+-- ==== __Examples__+-- +-- > > let xs = ("hello", 1 :: Integer) `mlcons` (" world", 2) `mlcons` (toMinLenZero [])+-- > > ofoldMap1 fst xs+-- > "hello world" ofoldMap1 :: (MonoFoldable mono, Semigroup m) => (Element mono -> m) -> MinLen (Succ nat) mono -> m ofoldMap1 f = ofoldMap1Ex f . unMinLen {-# INLINE ofoldMap1 #-} +-- | Joins a list of 'Semigroups' together.+--+-- ==== __Examples__+-- +-- > > let xs = "a" `mlcons` "b" `mlcons` "c" `mlcons` (toMinLenZero [])+-- > > xs+-- > MinLen {unMinLen = ["a","b","c"]}+-- >+-- > > ofold1 xs+-- > "abc" ofold1 :: (MonoFoldable mono, Semigroup (Element mono)) => MinLen (Succ nat) mono -> Element mono ofold1 = ofoldMap1 id {-# INLINE ofold1 #-} -+-- | A right fold that has no base case, and thus may only be applied to non-empty structures.+-- -- @'foldr1' f = 'Prelude.foldr1' f . 'otoList'@+--+-- ==== __Examples__+-- +-- > > let xs = "a" `mlcons` "b" `mlcons` "c" `mlcons` (toMinLenZero [])+-- > > ofoldr1 (++) xs+-- > "abc" ofoldr1 :: MonoFoldable mono => (Element mono -> Element mono -> Element mono) -> MinLen (Succ nat) mono@@ -170,10 +299,16 @@ ofoldr1 f = ofoldr1Ex f . unMinLen {-# INLINE ofoldr1 #-} --- | A variant of 'ofoldl\'' that has no base case,+-- | A variant of 'ofoldl'' that has no base case, -- and thus may only be applied to non-empty structures. ----- @'foldl1\'' f = 'Prelude.foldl1' f . 'otoList'@+-- @'foldl1' f = 'Prelude.foldl1' f . 'otoList'@+--+-- ==== __Examples__+-- +-- > > let xs = "a" `mlcons` "b" `mlcons` "c" `mlcons` (toMinLenZero [])+-- > > ofoldl1' (++) xs+-- > "abc" ofoldl1' :: MonoFoldable mono => (Element mono -> Element mono -> Element mono) -> MinLen (Succ nat) mono@@ -181,21 +316,33 @@ ofoldl1' f = ofoldl1Ex' f . unMinLen {-# INLINE ofoldl1' #-} --- | like Data.List, but not partial on a MonoFoldable+-- | Like Data.List.'Data.List.maximum', but not partial on a MonoFoldable.+--+-- ==== __Examples__+--+-- > > let xs = toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])+-- > > fmap maximum xs+-- > Just 3 maximum :: MonoFoldableOrd mono => MinLen (Succ nat) mono -> Element mono maximum = maximumEx . unMinLen {-# INLINE maximum #-} --- | like Data.List, but not partial on a MonoFoldable+-- | Like Data.List.'Data.List.minimum', but not partial on a MonoFoldable.+--+-- ==== __Examples__+--+-- > > let xs = toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])+-- > > fmap minimum xs+-- > Just 1 minimum :: MonoFoldableOrd mono => MinLen (Succ nat) mono -> Element mono minimum = minimumEx . unMinLen {-# INLINE minimum #-} --- | like Data.List, but not partial on a MonoFoldable+-- | Like Data.List.'Data.List.maximumBy', but not partial on a MonoFoldable. maximumBy :: MonoFoldable mono => (Element mono -> Element mono -> Ordering) -> MinLen (Succ nat) mono@@ -203,7 +350,7 @@ maximumBy cmp = maximumByEx cmp . unMinLen {-# INLINE maximumBy #-} --- | like Data.List, but not partial on a MonoFoldable+-- | Like Data.List.'Data.List.minimumBy', but not partial on a MonoFoldable. minimumBy :: MonoFoldable mono => (Element mono -> Element mono -> Ordering) -> MinLen (Succ nat) mono