deferred-folds 0.9.7 → 0.9.7.1

raw patch · 2 files changed

+53/−1 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• deferred-folds.cabal +1/−1
• library/DeferredFolds/Types.hs +52/−0

@@ -1,5 +1,5 @@ name: deferred-folds-version: 0.9.7+version: 0.9.7.1 category: Folding synopsis: Abstractions over deferred folds description:

@@ -63,6 +63,58 @@ -} newtype UnfoldlM m a = UnfoldlM (forall x. (x -> a -> m x) -> x -> m x) +{-|+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 `Data.List.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+-} newtype Unfoldr a = Unfoldr (forall x. (a -> x -> x) -> x -> x)  newtype UnfoldrM m a = UnfoldrM (forall x. (a -> x -> m x) -> x -> m x)