deferred-folds-0.9.17: Abstractions over deferred folds
Safe HaskellNone
LanguageHaskell2010

DeferredFolds.Types

Synopsis

Documentation

newtype Unfoldl a Source #

A projection on data, which only knows how to execute a strict left-fold.

It is a monad and a monoid, and is very useful for efficiently aggregating the projections on data intended for left-folding, since its concatenation (<>) has complexity of O(1).

Intuition

The intuition for this abstraction can be derived from lists.

Let's consider the foldl` function for lists:

foldl' :: (b -> a -> b) -> b -> [a] -> b

If we reverse its parameters we get

foldl' :: [a] -> (b -> a -> b) -> b -> b

Which in Haskell is essentially the same as

foldl' :: [a] -> (forall b. (b -> a -> b) -> b -> b)

We can isolate that part into an abstraction:

newtype Unfoldl a = Unfoldl (forall b. (b -> a -> b) -> b -> b)

Then we get to this simple morphism:

list :: [a] -> Unfoldl a
list list = Unfoldl (\ step init -> foldl' step init list)

We can do the same with say Data.Text.Text:

text :: Text -> Unfoldl Char
text text = Unfoldl (\ step init -> Data.Text.foldl' step init text)

And then we can use those both to concatenate with just an O(1) cost:

abcdef :: Unfoldl Char
abcdef = list ['a', 'b', 'c'] <> text "def"

Please notice that up until this moment no actual data materialization has happened and hence no traversals have appeared. All that we've done is just composed a function, which only specifies which parts of data structures to traverse to perform a left-fold. Only at the moment where the actual folding will happen will we actually traverse the source data. E.g., using the "fold" function:

abcdefLength :: Int
abcdefLength = fold Control.Foldl.length abcdef

Constructors

Unfoldl (forall x. (x -> a -> x) -> x -> x) 

Instances

Instances details
Monad Unfoldl Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Methods

(>>=) :: Unfoldl a -> (a -> Unfoldl b) -> Unfoldl b Source #

(>>) :: Unfoldl a -> Unfoldl b -> Unfoldl b Source #

return :: a -> Unfoldl a Source #

Functor Unfoldl Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Methods

fmap :: (a -> b) -> Unfoldl a -> Unfoldl b Source #

(<$) :: a -> Unfoldl b -> Unfoldl a Source #

Applicative Unfoldl Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Methods

pure :: a -> Unfoldl a Source #

(<*>) :: Unfoldl (a -> b) -> Unfoldl a -> Unfoldl b Source #

liftA2 :: (a -> b -> c) -> Unfoldl a -> Unfoldl b -> Unfoldl c Source #

(*>) :: Unfoldl a -> Unfoldl b -> Unfoldl b Source #

(<*) :: Unfoldl a -> Unfoldl b -> Unfoldl a Source #

Foldable Unfoldl Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Methods

fold :: Monoid m => Unfoldl m -> m Source #

foldMap :: Monoid m => (a -> m) -> Unfoldl a -> m Source #

foldMap' :: Monoid m => (a -> m) -> Unfoldl a -> m Source #

foldr :: (a -> b -> b) -> b -> Unfoldl a -> b Source #

foldr' :: (a -> b -> b) -> b -> Unfoldl a -> b Source #

foldl :: (b -> a -> b) -> b -> Unfoldl a -> b Source #

foldl' :: (b -> a -> b) -> b -> Unfoldl a -> b Source #

foldr1 :: (a -> a -> a) -> Unfoldl a -> a Source #

foldl1 :: (a -> a -> a) -> Unfoldl a -> a Source #

toList :: Unfoldl a -> [a] Source #

null :: Unfoldl a -> Bool Source #

length :: Unfoldl a -> Int Source #

elem :: Eq a => a -> Unfoldl a -> Bool Source #

maximum :: Ord a => Unfoldl a -> a Source #

minimum :: Ord a => Unfoldl a -> a Source #

sum :: Num a => Unfoldl a -> a Source #

product :: Num a => Unfoldl a -> a Source #

Alternative Unfoldl Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

MonadPlus Unfoldl Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Methods

mzero :: Unfoldl a Source #

mplus :: Unfoldl a -> Unfoldl a -> Unfoldl a Source #

IsList (Unfoldl a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Associated Types

type Item (Unfoldl a) Source #

Methods

fromList :: [Item (Unfoldl a)] -> Unfoldl a Source #

fromListN :: Int -> [Item (Unfoldl a)] -> Unfoldl a Source #

toList :: Unfoldl a -> [Item (Unfoldl a)] Source #

Eq a => Eq (Unfoldl a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Methods

(==) :: Unfoldl a -> Unfoldl a -> Bool Source #

(/=) :: Unfoldl a -> Unfoldl a -> Bool Source #

Show a => Show (Unfoldl a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Semigroup (Unfoldl a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

Methods

(<>) :: Unfoldl a -> Unfoldl a -> Unfoldl a Source #

sconcat :: NonEmpty (Unfoldl a) -> Unfoldl a Source #

stimes :: Integral b => b -> Unfoldl a -> Unfoldl a Source #

Monoid (Unfoldl a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

type Item (Unfoldl a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldl

type Item (Unfoldl a) = a

newtype UnfoldlM m a Source #

A monadic variation of DeferredFolds.Unfoldl

Constructors

UnfoldlM (forall x. (x -> a -> m x) -> x -> m x) 

Instances

Instances details
MonadTrans UnfoldlM Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

lift :: Monad m => m a -> UnfoldlM m a Source #

Monad m => Monad (UnfoldlM m) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

(>>=) :: UnfoldlM m a -> (a -> UnfoldlM m b) -> UnfoldlM m b Source #

(>>) :: UnfoldlM m a -> UnfoldlM m b -> UnfoldlM m b Source #

return :: a -> UnfoldlM m a Source #

Functor m => Functor (UnfoldlM m) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

fmap :: (a -> b) -> UnfoldlM m a -> UnfoldlM m b Source #

(<$) :: a -> UnfoldlM m b -> UnfoldlM m a Source #

Monad m => Applicative (UnfoldlM m) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

pure :: a -> UnfoldlM m a Source #

(<*>) :: UnfoldlM m (a -> b) -> UnfoldlM m a -> UnfoldlM m b Source #

liftA2 :: (a -> b -> c) -> UnfoldlM m a -> UnfoldlM m b -> UnfoldlM m c Source #

(*>) :: UnfoldlM m a -> UnfoldlM m b -> UnfoldlM m b Source #

(<*) :: UnfoldlM m a -> UnfoldlM m b -> UnfoldlM m a Source #

Foldable (UnfoldlM Identity) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

fold :: Monoid m => UnfoldlM Identity m -> m Source #

foldMap :: Monoid m => (a -> m) -> UnfoldlM Identity a -> m Source #

foldMap' :: Monoid m => (a -> m) -> UnfoldlM Identity a -> m Source #

foldr :: (a -> b -> b) -> b -> UnfoldlM Identity a -> b Source #

foldr' :: (a -> b -> b) -> b -> UnfoldlM Identity a -> b Source #

foldl :: (b -> a -> b) -> b -> UnfoldlM Identity a -> b Source #

foldl' :: (b -> a -> b) -> b -> UnfoldlM Identity a -> b Source #

foldr1 :: (a -> a -> a) -> UnfoldlM Identity a -> a Source #

foldl1 :: (a -> a -> a) -> UnfoldlM Identity a -> a Source #

toList :: UnfoldlM Identity a -> [a] Source #

null :: UnfoldlM Identity a -> Bool Source #

length :: UnfoldlM Identity a -> Int Source #

elem :: Eq a => a -> UnfoldlM Identity a -> Bool Source #

maximum :: Ord a => UnfoldlM Identity a -> a Source #

minimum :: Ord a => UnfoldlM Identity a -> a Source #

sum :: Num a => UnfoldlM Identity a -> a Source #

product :: Num a => UnfoldlM Identity a -> a Source #

Monad m => Alternative (UnfoldlM m) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

empty :: UnfoldlM m a Source #

(<|>) :: UnfoldlM m a -> UnfoldlM m a -> UnfoldlM m a Source #

some :: UnfoldlM m a -> UnfoldlM m [a] Source #

many :: UnfoldlM m a -> UnfoldlM m [a] Source #

Monad m => MonadPlus (UnfoldlM m) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

mzero :: UnfoldlM m a Source #

mplus :: UnfoldlM m a -> UnfoldlM m a -> UnfoldlM m a Source #

IsList (UnfoldlM Identity a) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Associated Types

type Item (UnfoldlM Identity a) Source #

Eq a => Eq (UnfoldlM Identity a) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Show a => Show (UnfoldlM Identity a) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Monad m => Semigroup (UnfoldlM m a) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

(<>) :: UnfoldlM m a -> UnfoldlM m a -> UnfoldlM m a Source #

sconcat :: NonEmpty (UnfoldlM m a) -> UnfoldlM m a Source #

stimes :: Integral b => b -> UnfoldlM m a -> UnfoldlM m a Source #

Monad m => Monoid (UnfoldlM m a) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

Methods

mempty :: UnfoldlM m a Source #

mappend :: UnfoldlM m a -> UnfoldlM m a -> UnfoldlM m a Source #

mconcat :: [UnfoldlM m a] -> UnfoldlM m a Source #

type Item (UnfoldlM Identity a) Source # 
Instance details

Defined in DeferredFolds.Defs.UnfoldlM

type Item (UnfoldlM Identity a) = a

newtype Unfoldr a Source #

A projection on data, which only knows how to execute a right-fold.

It is a monad and a monoid, and is very useful for efficiently aggregating the projections on data intended for right-folding, since its concatenation (<>) has complexity of O(1).

Intuition

The intuition of what this abstraction is all about can be derived from lists.

Let's consider the foldr function for lists:

foldr :: (a -> b -> b) -> b -> [a] -> b

If we reverse its parameters we get

foldr :: [a] -> (a -> b -> b) -> b -> b

Which in Haskell is essentially the same as

foldr :: [a] -> (forall b. (a -> b -> b) -> b -> b)

We can isolate that part into an abstraction:

newtype Unfoldr a = Unfoldr (forall b. (a -> b -> b) -> b -> b)

Then we get to this simple morphism:

list :: [a] -> Unfoldr a
list list = Unfoldr (\ step init -> foldr step init list)

We can do the same with say Data.Text.Text:

text :: Text -> Unfoldr Char
text text = Unfoldr (\ step init -> Data.Text.foldr step init text)

And then we can use those both to concatenate with just an O(1) cost:

abcdef :: Unfoldr Char
abcdef = list ['a', 'b', 'c'] <> text "def"

Please notice that up until this moment no actual data materialization has happened and hence no traversals have appeared. All that we've done is just composed a function, which only specifies which parts of data structures to traverse to perform a right-fold. Only at the moment where the actual folding will happen will we actually traverse the source data. E.g., using the "fold" function:

abcdefLength :: Int
abcdefLength = fold Control.Foldl.length abcdef

Constructors

Unfoldr (forall x. (a -> x -> x) -> x -> x) 

Instances

Instances details
Monad Unfoldr Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

(>>=) :: Unfoldr a -> (a -> Unfoldr b) -> Unfoldr b Source #

(>>) :: Unfoldr a -> Unfoldr b -> Unfoldr b Source #

return :: a -> Unfoldr a Source #

Functor Unfoldr Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

fmap :: (a -> b) -> Unfoldr a -> Unfoldr b Source #

(<$) :: a -> Unfoldr b -> Unfoldr a Source #

Applicative Unfoldr Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

pure :: a -> Unfoldr a Source #

(<*>) :: Unfoldr (a -> b) -> Unfoldr a -> Unfoldr b Source #

liftA2 :: (a -> b -> c) -> Unfoldr a -> Unfoldr b -> Unfoldr c Source #

(*>) :: Unfoldr a -> Unfoldr b -> Unfoldr b Source #

(<*) :: Unfoldr a -> Unfoldr b -> Unfoldr a Source #

Foldable Unfoldr Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

fold :: Monoid m => Unfoldr m -> m Source #

foldMap :: Monoid m => (a -> m) -> Unfoldr a -> m Source #

foldMap' :: Monoid m => (a -> m) -> Unfoldr a -> m Source #

foldr :: (a -> b -> b) -> b -> Unfoldr a -> b Source #

foldr' :: (a -> b -> b) -> b -> Unfoldr a -> b Source #

foldl :: (b -> a -> b) -> b -> Unfoldr a -> b Source #

foldl' :: (b -> a -> b) -> b -> Unfoldr a -> b Source #

foldr1 :: (a -> a -> a) -> Unfoldr a -> a Source #

foldl1 :: (a -> a -> a) -> Unfoldr a -> a Source #

toList :: Unfoldr a -> [a] Source #

null :: Unfoldr a -> Bool Source #

length :: Unfoldr a -> Int Source #

elem :: Eq a => a -> Unfoldr a -> Bool Source #

maximum :: Ord a => Unfoldr a -> a Source #

minimum :: Ord a => Unfoldr a -> a Source #

sum :: Num a => Unfoldr a -> a Source #

product :: Num a => Unfoldr a -> a Source #

Traversable Unfoldr Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

traverse :: Applicative f => (a -> f b) -> Unfoldr a -> f (Unfoldr b) Source #

sequenceA :: Applicative f => Unfoldr (f a) -> f (Unfoldr a) Source #

mapM :: Monad m => (a -> m b) -> Unfoldr a -> m (Unfoldr b) Source #

sequence :: Monad m => Unfoldr (m a) -> m (Unfoldr a) Source #

Alternative Unfoldr Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

MonadPlus Unfoldr Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

mzero :: Unfoldr a Source #

mplus :: Unfoldr a -> Unfoldr a -> Unfoldr a Source #

IsList (Unfoldr a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Associated Types

type Item (Unfoldr a) Source #

Methods

fromList :: [Item (Unfoldr a)] -> Unfoldr a Source #

fromListN :: Int -> [Item (Unfoldr a)] -> Unfoldr a Source #

toList :: Unfoldr a -> [Item (Unfoldr a)] Source #

Eq a => Eq (Unfoldr a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

(==) :: Unfoldr a -> Unfoldr a -> Bool Source #

(/=) :: Unfoldr a -> Unfoldr a -> Bool Source #

Show a => Show (Unfoldr a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Semigroup (Unfoldr a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

Methods

(<>) :: Unfoldr a -> Unfoldr a -> Unfoldr a Source #

sconcat :: NonEmpty (Unfoldr a) -> Unfoldr a Source #

stimes :: Integral b => b -> Unfoldr a -> Unfoldr a Source #

Monoid (Unfoldr a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

type Item (Unfoldr a) Source # 
Instance details

Defined in DeferredFolds.Defs.Unfoldr

type Item (Unfoldr a) = a

newtype UnfoldrM m a Source #

Constructors

UnfoldrM (forall x. (a -> x -> m x) -> x -> m x)