yaya-unsafe 0.4.1.0 → 0.4.1.1

raw patch · 3 files changed

+136/−44 lines, 3 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• src/Yaya/Unsafe/Fold.hs +126/−40
• src/Yaya/Unsafe/Zoo.hs +9/−3
• yaya-unsafe.cabal +1/−1

@@ -21,13 +21,12 @@ import "base" Control.Applicative (Applicative (pure)) import "base" Control.Category (Category ((.))) import "base" Control.Monad (Monad, (<=<))-import "base" Data.Bifunctor (Bifunctor (first))-import "base" Data.Function (flip)+import "base" Data.Function (flip, ($)) import "base" Data.Functor (Functor (fmap)) import "base" Data.Functor.Compose (Compose (Compose, getCompose)) import "base" Data.Traversable (Traversable (sequenceA)) import "comonad" Control.Comonad (Comonad (extract))-import "lens" Control.Lens (Prism', matching, prism, review, (&))+import "lens" Control.Lens (Prism', matching, prism, review) import "yaya" Yaya.Fold   ( Algebra,     AlgebraM,@@ -77,9 +76,9 @@ unsafeCata = flip hylo project  -- | This can’t be implemented in a total fashion. There is a /similar/ approach---   that can be total – with `ψ :: CoalgebraM (->) m f a`, `ana (Compose . ψ)`---   results in something like `Nu (Compose m f)` which is akin to an effectful---   stream.+--   that can be total – with @ψ :: `CoalgebraM` (->) m f a@, @`ana` (`Compose`+--  . ψ)@ results in something like @`Nu` (`Compose` m f)@ which is akin to an+--   effectful stream. anaM ::   (Monad m, Steppable (->) t f, Traversable f) =>   CoalgebraM (->) m f a ->@@ -95,7 +94,7 @@   m t ganaM k ψ = anaM (lowerCoalgebraM k ψ) . pure --- | Fusion of an 'ana' and 'cata'.+-- | Fusion of an 'ana' and a 'cata'. hylo :: (Functor f) => Algebra (->) f b -> Coalgebra (->) f a -> a -> b hylo φ ψ = go   where@@ -131,54 +130,141 @@ ghyloM w n φ ψ =   fmap extract . hyloM (lowerAlgebraM w φ) (lowerCoalgebraM n ψ) . pure +-- | This is the core operation for all metamorphisms. It generally shouldn’t be+--   used directly, but is exposed in case you come up with a novel accumulation+--   function to use.+--+--   Metamorphisms are conceptually a fold followed by an unfold (effectively+--   the reverse of a hylomorphism). Many are equivalent to @`ana` ψ `.` `cata`+--   φ@, but some can be processed incrementally, forming a family of+--   “[streaming+--   metamorphisms](https://www.cs.ox.ac.uk/jeremy.gibbons/publications/metamorphisms-scp.pdf)”,+--   which are the ones captured here.+--+--  __FIXME__: What happens when this is given a branching structure? Where does+--             that cause a problem?+--+--  __NB__: See https://gist.github.com/sellout/4709e723cb649110af00217486c4466b+--          for some commentary and explanation. stream' ::-  (Projectable (->) t f, Steppable (->) u g, Functor g) =>-  CoalgebraM (->) Maybe g b ->-  (b -> (Pair (b -> b) t -> u) -> f t -> u) ->-  b ->-  t ->-  u-stream' ψ f = go+  ( Projectable (->) input inputf,+    Steppable (->) output outputf,+    Functor outputf+  ) =>+  -- | Lazily processes the state into additional output elements. This should+  --   return `Nothing` when the state doesn’t allow any more output to be+  --   generated, causing control to be transferred back to the accumulator+  --   algebra.+  --+  -- > state -> Maybe (outputf state)+  CoalgebraM (->) Maybe outputf state ->+  -- | The general state accumulation function, this is specialized in the other+  --   @stream*@ functions. Given a state and a continuation function, converts+  --   the entire input to output.+  --+  --  __TODO__: Consider whether it’d be useful/possible to use+  --+  --          > forall x. state -> ((state -> state) -> x -> output) -> inputf x -> output+  --+  --            to prevent the function from consuming more than one element of+  --            the input per call.+  (state -> ((state -> state) -> input -> output) -> inputf input -> output) ->+  -- | The initial state.+  state ->+  -- | The `Recursive` (well, `Projectable`) input.+  input ->+  -- | The `Corecursive` (well, `Steppable`) output.+  output+stream' process accum = go   where-    go c x =+    go state input =       maybe-        (f c (uncurry go . first (c &)) (project x))-        (embed . fmap (`go` x))-        (ψ c)+        (accum state (go . ($ state)) (project input))+        (embed . fmap (`go` input))+        $ process state  -- | Gibbons’ metamorphism. It lazily folds a (necessarily infinite) value,---   incrementally re-expanding that value into some new representation.+--   incrementally re-expanding that value into some new representation. See+--  `stream'` for more on metamorphisms. -----  __NB__: See https://gist.github.com/sellout/4709e723cb649110af00217486c4466b---          for some commentary and explanation.+--  __FIXME__: What happens when this is given a finite structure?+--+--   The “Ana” in the name parallels the naming of `streamGApo`, where this form+--   lacks the helper algebra, in the same way that `ana` lacks the helper+--   algebra that `Yaya.Zoo.gapo` has. streamAna ::-  (Projectable (->) t f, Steppable (->) u g, Functor g) =>-  CoalgebraM (->) Maybe g b ->-  AlgebraM (->) (Pair (b -> b)) f t ->-  b ->-  t ->-  u-streamAna process accum = stream' process (\_ f -> f . accum)+  ( Projectable (->) input inputf,+    Steppable (->) output outputf,+    Functor outputf+  ) =>+  -- | Lazily processes the state into additional output elements. This should+  --   return `Nothing` when the state doesn’t allow any more output to be+  --   generated, causing control to be transferred back to the accumulator+  --   algebra.+  --+  -- > state -> Maybe (outputf state)+  CoalgebraM (->) Maybe outputf state ->+  -- | Accumulates more elements from the input into the state. It returns a+  --   function to modify the previous state as well as the remaining input.+  --   This passes control back to the processing coalgebra after each call,+  --   allowing as much output to be generated from as little input as possible.+  --+  -- > inputf input -> (state -> state, input)+  AlgebraM (->) (Pair (state -> state)) inputf input ->+  -- | The initial state.+  state ->+  -- | The `Recursive` (well, `Projectable`) input.+  input ->+  -- | The `Corecursive` (well, `Steppable`) output.+  output+streamAna process accum = stream' process $ \_state cont -> uncurry cont . accum  -- | Another form of Gibbons’ metamorphism. This one can be applied to non- --   infinite inputs and takes an additional “flushing” coalgebra to be applied---   after all the input has been consumed.+--   after all the input has been consumed. See `stream'` for more on+--  metamorphisms. -----  __NB__: See https://gist.github.com/sellout/4709e723cb649110af00217486c4466b---          for some commentary and explanation.+--   The “GApo” in the name comes from the parallel with `Yaya.Zoo.gapo`, where+--   a “helper” `Coalgebra` (the “flusher” in this case) can be applied when the+--   primary algebra “fails”. This is also why the arguments are re-ordered+--   relative to Gibbons’ `Yaya.Unsafe.Zoo.fstream` – to make the parallel with+--   @gapo@ more obvious. streamGApo ::-  (Projectable (->) t f, Steppable (->) u g, Corecursive (->) u g, Functor g) =>-  Coalgebra (->) g b ->-  CoalgebraM (->) Maybe g b ->-  (f t -> Maybe (Pair (b -> b) t)) ->-  b ->-  t ->-  u+  ( Projectable (->) input inputf,+    Steppable (->) output outputf,+    Corecursive (->) output outputf,+    Functor outputf+  ) =>+  -- | The flushing coalgebra that consumes the remaining state after the input+  --   has been fully consumed.+  Coalgebra (->) outputf state ->+  -- | Lazily processes the state into additional output elements. This should+  --   return `Nothing` when the state doesn’t allow any more output to be+  --   generated, causing control to be transferred back to the accumulator+  --   algebra.+  --+  -- > state -> Maybe (outputf state)+  CoalgebraM (->) Maybe outputf state ->+  -- | Accumulates more elements from the input into the state. It returns a+  --   function to modify the previous state as well as the remaining input.+  --   This passes control back to the processing coalgebra after each call,+  --   allowing as much output to be generated from as little input as possible.+  --   This should return `Nothing` when the input is consumed, causing control+  --   to be transferred to the flushing coalgebra instead of the processing+  --   coalgebra.+  (inputf input -> Maybe (Pair (state -> state) input)) ->+  -- | The initial state.+  state ->+  -- | The `Recursive` (well, `Projectable`) input.+  input ->+  -- | The `Corecursive` output.+  output streamGApo flush process accum =-  stream' process (\c f -> maybe (ana flush c) f . accum)+  stream' process $+    \state cont -> maybe (ana flush state) (uncurry cont) . accum  corecursivePrism ::   (Steppable (->) t f, Recursive (->) t f, Traversable f) =>   CoalgebraPrism f a ->   Prism' a t-corecursivePrism alg = prism (cata (review alg)) (anaM (matching alg))+corecursivePrism alg = prism (cata $ review alg) (anaM $ matching alg)

@@ -102,15 +102,21 @@ gpostpro k e =   Unsafe.ghylo distIdentity k (embed . fmap (ana (e . project) . runIdentity)) --- | The metamorphism definition from Gibbons’ paper.+-- | The metamorphism definition from [Gibbons’+--   paper](https://www.cs.ox.ac.uk/jeremy.gibbons/publications/metamorphisms-scp.pdf). stream :: Coalgebra (->) (XNor c) b -> (b -> a -> b) -> b -> [a] -> [c] stream f g = fstream f g (const Neither) --- | Basically the definition from Gibbons’ paper, except the flusher (@h@) is a---  `Coalgebra` instead of an `unfold`.+-- | Basically the definition from [Gibbons’+--   paper](https://www.cs.ox.ac.uk/jeremy.gibbons/publications/metamorphisms-scp.pdf),+--   except the flusher is a `Coalgebra` instead of an unfold.+--+--   The implementation shows how `Unsafe.streamGApo` generalizes Gibbons’+--  `fstream` (and `Unsafe.stream'` even more so). fstream ::   Coalgebra (->) (XNor c) b ->   (b -> a -> b) ->+  -- | The flusher.   Coalgebra (->) (XNor c) b ->   b ->   [a] ->

@@ -1,7 +1,7 @@ cabal-version:  3.0  name:        yaya-unsafe-version:     0.4.1.0+version:     0.4.1.1 synopsis:    Non-total extensions to the Yaya recursion scheme library. description: Yaya is designed as a _total_ library. However, it is often              expedient to use partial operations in some cases, and this package