deferred-folds 0.1 → 0.2

raw patch · 3 files changed

+95/−95 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• deferred-folds.cabal +3/−3
• library/DeferredFolds/FoldlView.hs +92/−0
• library/DeferredFolds/ToBeFoldled.hs +0/−92

@@ -1,9 +1,9 @@ name:   deferred-folds version:-  0.1+  0.2 category:-  Fold+  Folding synopsis:   Abstractions over deferred folds homepage:@@ -39,7 +39,7 @@   default-language:     Haskell2010   exposed-modules:-    DeferredFolds.ToBeFoldled+    DeferredFolds.FoldlView   other-modules:     DeferredFolds.Prelude   build-depends:

@@ -0,0 +1,92 @@+module DeferredFolds.FoldlView+where++import DeferredFolds.Prelude+import qualified DeferredFolds.Prelude as A+++{-|+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 of what this abstraction is all about can be derived from lists.++Let's consider the `Data.List.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 FoldlView a = FoldlView (forall b. (b -> a -> b) -> b -> b)++Then we get to this simple morphism:++>foldl' :: [a] -> FoldlView a++-}+newtype FoldlView input =+  FoldlView (forall output. (output -> input -> output) -> output -> output)++deriving instance Functor FoldlView++instance Applicative FoldlView where+  pure x =+    FoldlView (\ step init -> step init x)+  (<*>) = ap++instance Alternative FoldlView where+  empty =+    FoldlView (const id)+  {-# INLINE (<|>) #-}+  (<|>) (FoldlView left) (FoldlView right) =+    FoldlView (\ step init -> right step (left step init))++instance Monad FoldlView where+  return = pure+  (>>=) (FoldlView left) rightK =+    FoldlView $ \ step init ->+    let+      newStep output x =+        case rightK x of+          FoldlView right ->+            right step output+      in left newStep init++instance MonadPlus FoldlView where+  mzero = empty+  mplus = (<|>)++instance Semigroup (FoldlView a) where+  (<>) = (<|>)++instance Monoid (FoldlView a) where+  mempty = empty+  mappend = (<>)++{-| Perform a strict left fold -}+{-# INLINE foldl' #-}+foldl' :: (output -> input -> output) -> output -> FoldlView input -> output+foldl' step init (FoldlView run) = run step init++{-| Apply a Gonzalez fold -}+{-# INLINE fold #-}+fold :: Fold input output -> FoldlView input -> output+fold (Fold step init extract) (FoldlView run) = extract (run step init)++{-| Construct from any foldable -}+{-# INLINE foldable #-}+foldable :: Foldable foldable => foldable a -> FoldlView a+foldable foldable = FoldlView (\ step init -> A.foldl' step init foldable)

@@ -1,92 +0,0 @@-module DeferredFolds.ToBeFoldled-where--import DeferredFolds.Prelude-import qualified DeferredFolds.Prelude as A---{-|-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 of what this abstraction is all about can be derived from lists.--Let's consider the `Data.List.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 ToBeFoldled a = ToBeFoldled (forall b. (b -> a -> b) -> b -> b)--Then we get to this simple morphism:-->foldl' :: [a] -> ToBeFoldled a---}-newtype ToBeFoldled input =-  ToBeFoldled (forall output. (output -> input -> output) -> output -> output)--deriving instance Functor ToBeFoldled--instance Applicative ToBeFoldled where-  pure x =-    ToBeFoldled (\ step init -> step init x)-  (<*>) = ap--instance Alternative ToBeFoldled where-  empty =-    ToBeFoldled (const id)-  {-# INLINE (<|>) #-}-  (<|>) (ToBeFoldled left) (ToBeFoldled right) =-    ToBeFoldled (\ step init -> right step (left step init))--instance Monad ToBeFoldled where-  return = pure-  (>>=) (ToBeFoldled left) rightK =-    ToBeFoldled $ \ step init ->-    let-      newStep output x =-        case rightK x of-          ToBeFoldled right ->-            right step output-      in left newStep init--instance MonadPlus ToBeFoldled where-  mzero = empty-  mplus = (<|>)--instance Semigroup (ToBeFoldled a) where-  (<>) = (<|>)--instance Monoid (ToBeFoldled a) where-  mempty = empty-  mappend = (<>)--{-| Perform a strict left fold -}-{-# INLINE foldl' #-}-foldl' :: (output -> input -> output) -> output -> ToBeFoldled input -> output-foldl' step init (ToBeFoldled run) = run step init--{-| Apply a Gonzalez fold -}-{-# INLINE fold #-}-fold :: Fold input output -> ToBeFoldled input -> output-fold (Fold step init extract) (ToBeFoldled run) = extract (run step init)--{-| Construct from any foldable -}-{-# INLINE foldable #-}-foldable :: Foldable foldable => foldable a -> ToBeFoldled a-foldable foldable = ToBeFoldled (\ step init -> A.foldl' step init foldable)