mono-traversable
Type classes for mapping, folding, and traversing monomorphic containers
https://github.com/snoyberg/mono-traversable#readme
Version on this page: | 1.0.15.3 |
LTS Haskell 22.33: | 1.0.17.0 |
Stackage Nightly 2024-09-07: | 1.0.17.0 |
Latest on Hackage: | 1.0.17.0 |
mono-traversable-1.0.15.3@sha256:059bf3c05cdbef2d06b765333fe41c2168ced2503a23de674e2a59ceb2548c48,2060
Module documentation for 1.0.15.3
mono-traversable
Type classes for mapping, folding, and traversing monomorphic and polymorphic containers.
Haskell is good at operating over polymorphic containers such as a list [a]
.
A monomorphic container is one such as Text which has a type Text
that does not expose a type variable for the underlying characters.
mono-traversable also adds
IsSequence
, etc for operating over sequential data typesIsSet
,IsMap
, etc for unifying set and map APIsNonNull
for making partial functions (head, tail) total
In addition to this package, the mono-traversable-instances package provides a number of orphan instances.
Using Typeclasses
There are 2 use cases for mono-traversable: application authors and library authors.
Library authors
As a library author, if you want to allow a user to pass in a Text
or a String
,
then you need to expose an API with a mono-traversable typeclass.
You should think twice about using mono-traversable though because
- Using Typeclasses makes type inference more difficult. It is usually better to force the user to give a
Text
. Another option is to just have multiple APIs. - If you are operating on polymorphic structures in which the normal typeclasses suffice, you should just use them from base. On the other hand, even if you are using polymorphic containers you may want to leverage
IsSequence
orMinLen
.
Application authors
As an application author, you should consider using classy-prelude, which leans heavily on mono-traversable.
When writing your own function signatures, you should default to making them concrete: if you are actually using a list, then make your function take a list rather than an IsSequence
. This will improve type inference, error messages, and make your code easier to understand. When you decide to use a Vector
instead of a list, change the type signature to use a Vector
. When you actually need a function to both accept a Vector
and a list, it is easy to change the function signature to the more abstract typeclasses that you require.
Standard Typeclasses
in the upcoming GHC 7.10, using Functor
, Foldable
, and Traversable
will become common-place. This means that rather than using List.map
, Vector.map
, etc, the map from the prelude will work on all data types that are a Functor. Of course, you can already do this now using fmap
.
For a Haskeller, it is important to understand Functor
, Applicative
, Monad
, Foldable
, and Monoid
: these are encountered in every day code. For mono-traversable, it is most important to understand Foldable.
mono-traversable Typeclasses
MonoFunctor
Same as Functor, but cannot change the type.
type family Element mono
type instance Element Text = Char
type instance Element [a] = a
Element is a type family. This tells the compiler to substitute Char
for Element Text
.
We can create this rule for every monomorphic container we want to operate on such as Text
And we can also create it for a polymorphic container.
Now lets compare MonoFunctor to the normal Functor.
fmap :: Functor f => (a -> b) -> f a -> f b
omap :: MonoFunctor mono => (Element mono -> Element mono) -> mono -> mono
So there is no type-change from a
to b
, the contained type must stay the same (Element mono -> Element mono
).
Here is the MonoFunctor typeclass definition
class MonoFunctor mono where
omap :: (Element mono -> Element mono) -> mono -> mono
default omap :: (Functor f, Element (f a) ~ a, f a ~ mono) => (a -> a) -> f a -> f a
omap = fmap
And we can write some instances
instance MonoFunctor T.Text where
omap = T.map
instance MonoFunctor [a]
The list definition was able to default to using fmap
so no body was needed.
MonoFoldable
Same as Foldable, but also operates over monomorphic containers.
MonoFoldable is the heart of the power of mono-traversable (and arguably the package should be named mono-foldable) because anything that can be done with Foldable
can be done with MonoFoldable
.
The reason why is that a monomorphic container can never change its type.
So omap
is a restricted fmap
.
However, folding generates a new structure, so we have no such concerns.
In the classy-prelude package, map is set to fmap
and omap must be used separately.
However, foldMap is set to just use the mono-traversable version: ofoldMap
class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
...
class MonoFoldable mono where
ofoldMap :: Monoid m => (Element mono -> m) -> mono -> m
ofoldr :: (Element mono -> b -> b) -> b -> mono -> b
...
There are additional Typeclasses which build on MonoFoldable
class (MonoFoldable mono, Monoid mono) => MonoFoldableMonoid mono where
oconcatMap :: (Element mono -> mono) -> mono -> mono
class (MonoFoldable mono, Ord (Element mono)) => MonoFoldableOrd mono where
maximumEx :: mono -> Element mono
minimumEx :: mono -> Element mono
class MonoPointed mono where
opoint :: Element mono -> mono
MonoPointed abstracts over the concept of a singleton. For any Applicative
, opoint
is the same as pure
from Applicative. Since mono-traversable did not bother with a MonoApplicative
typeclass, we added MonoPointed
to still have the functionality of pure
.
MonoTraversable
MonoTraversable
is Traversable
for monomorphic containers, just as
MonoFunctor
is Functor
for monomorphic containers.
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
...
class (MonoFunctor mono, MonoFoldable mono) => MonoTraversable mono where
otraverse :: Applicative f => (Element mono -> f (Element mono)) -> mono -> f mono
...
Containers
- SetContainer: unifies operations across
Set
andMap
- PolyMap: differenceMap and intersectionMap
- IsSet: unifies operations across different
Set
s - IsMap: unifies operations across different
Map
s - MonoZip: zip operations on MonoFunctors.
Note that because Set
is not a Functor (and therefore neither a MonoFunctor nor MonoTraversable), one must use setFromList
and setToList
to omap
or otraverse
over the elements of a Set
.
Sequences
IsSequence
contains list-like operations.
-- | Sequence Laws:
--
-- > fromList . otoList = id
-- > fromList (x <> y) = fromList x <> fromList y
-- > otoList (fromList x <> fromList y) = x <> y
class (Monoid seq, MonoTraversable seq, SemiSequence seq, MonoPointed seq) => IsSequence seq where
fromList :: [Element seq] -> seq
break :: (Element seq -> Bool) -> seq -> (seq, seq)
...
The laws state that an IsSequence is a list-like (sequential) structure.
- an
IsSequence
is not just something that can be converted to a list (MonoFoldable
), but something that can be created from a list. - Converting to and from a list does not change the
IsSequence
, and it doesn’t even change theIsSequence
if you do the conversions on chunks of theIsSequence
.
SemiSequence is required by IsSequence. It is conceptually the same as IsSequence, but contains operations that can also be used on a NonEmpty
or a MinLen
(which are SemiGroups) because they do not reduce the number of elements in the sequence.
There are some more typeclasess that build on top of IsSequence.
class (IsSequence seq, Eq (Element seq)) => EqSequence seq where
class (EqSequence seq, MonoFoldableOrd seq) => OrdSequence seq where
class (IsSequence t, IsString t, Element t ~ Char) => Textual t where
words :: t -> [t]
unwords :: [t] -> t
lines :: t -> [t]
unlines :: [t] -> t
toLower :: t -> t
toUpper :: t -> t
...
Textual functions are always safe to use with Unicode (it is possible to misuse other functions that operate on individual characters).
MinLen
Did you notice minimumEx and maximumEx from above? Ex stands for ‘Exception’. An exception will occur if you call minimumEx on an empty list. MinLen is a tool to guarantee that this never occurs, and instead to prove that there are one or more elements in your list.
minimumEx :: MonoFoldable mono => mono -> Element mono
-- | like Data.List, but not partial on a MonoFoldable
minimum :: MonoFoldableOrd mono => MinLen (Succ nat) mono -> Element mono
minimum = minimumEx . unMinLen
newtype MinLen nat mono = MinLen { unMinLen :: mono }
deriving (Eq, Ord, Read, Show, Data, Typeable, Functor)
-- Type level naturals
data Zero = Zero
data Succ nat = Succ nat
The minimum
function exposed from MinLen
is very similar to minimumEx
, but has a MinLen
wrapper that ensures it will never throw an exception.
MinLen
is a newtype with a phantom type that contains information about the minimum number of elements we know are in the structure. That is done through type-level Peano numbers.
What do we know about the input to minimum? If nat is Zero, then it reduces to MinLen (Succ Zero) mono
. Succ means successor, and the successor of 0 is 1, so the data structure has a minimum length of 1.
Lets see this in practice
> minimum []
<interactive>:3:9:
Couldn't match expected type ‘MinLen (Succ nat0) mono’
with actual type ‘[t0]’
> minimum [1,2,3]
-- same error as above
> minimum (toMinList (3 :| [2,1]))
1
> minimum (3 `mlcons` toMinLenZero [2,1])
1
Here we used Data.List.NonEmpty combined with toMinList or we just work with a List and prove through the usage of cons that it has more than one element.
Adding instances
If you have a polymorphic data type which is a member of one of the relevant typeclasses (Functor, Foldable, Traversable), it’s quite easy to add an instance for MonoFunctor, MonoFoldable or MonoTraversable.
You just have to declare the proper type instance:
{-# LANGUAGE TypeFamilies #-}
type instance Element (CustomType a) = a
And then, we can use the default implementation to declare instances:
instance MonoFunctor (CustomType a)
instance MonoFoldable (CustomType a)
instance MonoTraversable (CustomType a)
Now you are ready to use CustomType a
with the functions defined in this package.
Note: if your type is a monomorphic container without the proper typeclasses, then you will have to provide an implementation rather than using the default. However, this should be fairly simple, as can be seen in the code
mono-traversable versus lens Traversal
lens is a library with a lot of functionality covering a variety of patterns. One piece of functionality it exposes is Fold
and Traversal
which can also be used to deal with monomorphic containers.
You could prefer mono-traversable to using this part of lens because
- Familiar API - If you know
Foldable
, you can useMonoFoldable
just as easily - mono-traversable’s typeclass based approach means many methods are included in the class but can be given specialised optimized implementations
- You don’t explicitly pass around the
Traversal
The last point is also a point of inflexibility and points to a use case where you could prefer using a lens Traversal
. mono-traversable treats ByteString
as a sequence of bytes. If you want to treat it as both bytes and characters, mono-traversable would require a newtype wrapper around ByteString
, whereas a lens Traversal
would use a different traversal function.
mono-traversable is only an alternative for Fold
and Traversal
, not for Lens
, Prism
, Iso
, Getter
, Setter
, Review
, or Equality
.
Changes
ChangeLog for mono-traversable
1.0.15.3
- Compile with GHC 9.2 (
Option
removed frombase-4.16
) #199
1.0.15.2
1.0.15.1
- Remove whitespace after
@
in as-patterns for GHC HEAD #186
1.0.15.0
- Added
toNonEmpty
toData.NonNull
#185
1.0.14.0
- Added
WrappedMono
toData.MonoTraversable
#182
1.0.13.0
- Added
WrappedPoly
toData.MonoTraversable
#180
1.0.12.0
- Added
filterSet
toData.Containers
- Use container specific implementations for
filterSet
andfilterMap
#178
1.0.11.0
- Adding monomorphic instances for GHC.Generics and Data.Proxy types #175
1.0.10.0
1.0.9.0
- Added
filterMap
toData.Containers
#167
1.0.8.1
- Compat with gauge 0.1 and 0.2
1.0.8.0
- Switch to gauge
- Relax constraint on
singleton
toMonoPointed
#156
1.0.7.0
1.0.6.0
- Add
mapNonNull
function toData.NonNull
#150
1.0.5.0
- Move
oelem
andonotElem
into theMonoFoldable
class #133- Change
instance MonoFoldable (Set e)
toinstance Ord e => MonoFoldable (Set e)
- Change
1.0.4.0
- Add
dropEnd
function to theIsSequence
class, and a specialized implementation forText
1.0.3.0
- Add
ensurePrefix
andensureSuffix
functions #141
1.0.2.1
- Fix test suite for foldl 1.3
1.0.2
IsSequence
class: addlengthIndex
#127
1.0.1.3
- Make ‘olength’ for Set and Map O(1) #125
1.0.1.2
- Support for GHC 8.2
1.0.1.1
- Fix typo in rewrite rule
1.0.1
- Add
replaceElem
andreplaceSeq
#107
1.0.0.1
- Add missing export #101
1.0.0
- Implement the cleanups described in #95
- Split out
Data.MinLen
tominlen
package, and haveData.NonNull
stand on its own - Remove
Data.ByteVector
- Split out extra typeclass instances to
mono-traversable-instances
- Split out
- Remove the
Eq
andOrd
specific classes, and instead use rewrite rules - Provide the
Data.MonoTraversable.Unprefixed
module - Generalize
unwords
andunlines
#87 - Add
tailMay
andinitMay
#89
0.10.2
- Add
delete
anddeleteBy
methods to EqSequence #94
0.10.1.1
- Remove unneeded INLINEs #90
0.10.1
- Allow comonad-5 #86
0.10.0.1
- Instance for Data.Sequence.Seq is incorrect. #83
0.10.0
- Remove
Functor
instance forMinLen
#82
0.9.3
- Added
intercalate
,splitWhen
,splitElem
, andsplitSeq
#80
0.9.2.1
- Tweak test suite for 32-bit systems #78
0.9.2
- MonoComonad
0.9.1
- Fill in missing Mono* instances #72
0.9.0.1
- Documentation improvements
0.9.0
- Better fixity for mlcons #56
0.8.0.1
README updates
0.8.0
A new MonoFoldableEq class that takes elem
and notElem
from EqSequence
.
EqSequence
now inherits from MonoFoldableEq
.
For most users that do not define instances this should not be a breaking change.
However, any instance of EqSequence
now needs to definie MonoFoldableEq
.
0.7.0
- Work on better polymorphic containers
- Rename
mapKeysWith
toomapKeysWith
- Add new class
BiPolyMap
- Add
keys
toIsSet
- New class
HasKeysSet
- Rename
- Added
index
,indexEx
andunsafeIndex
. - Added
sortOn