deferred-folds (empty) → 0.1

raw patch · 5 files changed

+184/−0 lines, 5 filesdep +basedep +foldlsetup-changed

Dependencies added: base, foldl

Files

• LICENSE +22/−0
• Setup.hs +2/−0
• deferred-folds.cabal +47/−0
• library/DeferredFolds/Prelude.hs +21/−0
• library/DeferredFolds/ToBeFoldled.hs +92/−0

@@ -0,0 +1,22 @@+Copyright (c) 2018, Metrix.AI++Permission is hereby granted, free of charge, to any person+obtaining a copy of this software and associated documentation+files (the "Software"), to deal in the Software without+restriction, including without limitation the rights to use,+copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the+Software is furnished to do so, subject to the following+conditions:++The above copyright notice and this permission notice shall be+included in all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES+OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT+HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,+WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR+OTHER DEALINGS IN THE SOFTWARE.

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,47 @@+name:+  deferred-folds+version:+  0.1+category:+  Fold+synopsis:+  Abstractions over deferred folds+homepage:+  https://github.com/metrix-ai/deferred-folds +bug-reports:+  https://github.com/metrix-ai/deferred-folds/issues +author:+  Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer:+  Metrix.AI Ninjas <ninjas@metrix.ai>+copyright:+  (c) 2018, Metrix.AI+license:+  MIT+license-file:+  LICENSE+build-type:+  Simple+cabal-version:+  >=1.10++source-repository head+  type:+    git+  location:+    git://github.com/metrix-ai/deferred-folds.git++library+  hs-source-dirs:+    library+  default-extensions:+    Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, PatternGuards, PatternSynonyms, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeFamilies, TypeOperators, UnboxedTuples+  default-language:+    Haskell2010+  exposed-modules:+    DeferredFolds.ToBeFoldled+  other-modules:+    DeferredFolds.Prelude+  build-depends:+    base >=4.7 && <5,+    foldl >=1 && <2

@@ -0,0 +1,21 @@+module DeferredFolds.Prelude+(+  module Exports,+)+where+++-- base+-------------------------+import Prelude as Exports hiding ((<>))+import Foreign as Exports hiding (void)+import Data.Monoid as Exports hiding ((<>), First(..), Last(..))+import Data.Semigroup as Exports+import Data.Foldable as Exports+import Data.Traversable as Exports+import Control.Applicative as Exports+import Control.Monad as Exports++-- foldl+-------------------------+import Control.Foldl as Exports (Fold(..))

@@ -0,0 +1,92 @@+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)