yaya-unsafe 0.2.0.1 → 0.3.3.0
raw patch · 9 files changed
+632/−214 lines, 9 filesdep +doctestdep +yaya-unsafedep −eitherdep ~basedep ~yayabuild-type:Customsetup-changed
Dependencies added: doctest, yaya-unsafe
Dependencies removed: either
Dependency ranges changed: base, yaya
Files
- CHANGELOG.md +22/−0
- README.md +1/−0
- Setup.hs +17/−0
- src/Yaya/Unsafe/Applied.hs +15/−0
- src/Yaya/Unsafe/Fold.hs +147/−62
- src/Yaya/Unsafe/Fold/Instances.hs +97/−34
- src/Yaya/Unsafe/Zoo.hs +111/−70
- tests/doctests.hs +12/−0
- yaya-unsafe.cabal +210/−48
CHANGELOG.md view
@@ -1,36 +1,58 @@ # Changelog+ All notable changes to this project will be documented in this file. The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), and this project adheres to the [Haskell Package Versioning Policy](https://pvp.haskell.org/). +## 0.2.0.2 – 2023–12–21++### Changed++- updated formatting for newer Ormolu+ ## 0.2.0.1 – 2020–05–18+ ### Changed+ - Turned on StrictData ## 0.2.0.0 – 2020–05–14+ ### Changed+ - updated in sync with polykinding changes in yaya-0.3.0.0 ## 0.1.1.3 – 2020–05–14+ ### Changed+ - enabled and fixed warnings ## 0.1.1.2 – 2019–11–08+ ### Changed+ - improved documentation ## 0.1.1.1 – 2019–11–08+ ### Added+ - tests for `law_cataCompose` (which bumps the yaya-hedgehog dependency for tests) ## 0.1.1.0 – 2019–01–08+ ### Added+ - lower bounds on internal yaya dependencies ### Changed+ - weakened constraints on a couple operations ## 0.1.0.0 – 2019–01–04+ ### Added+ - everything (this is the initial release)
README.md view
@@ -3,6 +3,7 @@ Unsafe extensions to the Yaya recursion scheme library. This includes+ - `Recursive` instances for lazily-recursive types - `Corecursive` instances for strictly-recursive types - operations on trees that can’t be implemented in a total fashion.
+ Setup.hs view
@@ -0,0 +1,17 @@+-- __NB__: `custom-setup` doesn’t have any way to specify extensions, so any we+-- want need to be specified here.+{-# LANGUAGE PackageImports #-}+{-# LANGUAGE Unsafe #-}+{-# LANGUAGE NoImplicitPrelude #-}+{-# OPTIONS_GHC -Weverything #-}+-- Warns even when `Unsafe` is explicit, not inferred. See+-- https://gitlab.haskell.org/ghc/ghc/-/issues/16689+{-# OPTIONS_GHC -Wno-unsafe #-}++module Main (main) where++import safe "base" System.IO (IO)+import "cabal-doctest" Distribution.Extra.Doctest (defaultMainWithDoctests)++main :: IO ()+main = defaultMainWithDoctests "doctests"
+ src/Yaya/Unsafe/Applied.hs view
@@ -0,0 +1,15 @@+{-# LANGUAGE Safe #-}++module Yaya.Unsafe.Applied+ ( unsafeFromList,+ )+where++import "yaya" Yaya.Fold (Steppable (embed))+import "yaya" Yaya.Pattern (XNor)+import "this" Yaya.Unsafe.Fold (unsafeCata)++-- | An unsafe implementation of `GHC.Exts.fromList` for `Steppable`+-- fixed-points of `XNor`.+unsafeFromList :: (Steppable (->) t (XNor a)) => [a] -> t+unsafeFromList = unsafeCata embed
src/Yaya/Unsafe/Fold.hs view
@@ -1,99 +1,184 @@+{-# LANGUAGE Safe #-}+ -- | Definitions and instances that use direct recursion, which (because of -- laziness) can lead to non-termination.-module Yaya.Unsafe.Fold where+module Yaya.Unsafe.Fold+ ( anaM,+ corecursivePrism,+ ganaM,+ ghylo,+ ghyloM,+ hylo,+ hyloM,+ stream',+ streamAna,+ streamGApo,+ unsafeAna,+ unsafeCata,+ )+where -import Control.Arrow-import Control.Comonad-import Control.Lens-import Control.Monad-import Data.Functor.Compose+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.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 "yaya" Yaya.Fold+ ( Algebra,+ AlgebraM,+ Coalgebra,+ CoalgebraM,+ CoalgebraPrism,+ Corecursive (ana),+ DistributiveLaw,+ GAlgebra,+ GAlgebraM,+ GCoalgebra,+ GCoalgebraM,+ Projectable (project),+ Recursive (cata),+ Steppable (embed),+ lowerAlgebra,+ lowerAlgebraM,+ lowerCoalgebra,+ lowerCoalgebraM,+ )+import "yaya" Yaya.Pattern (Maybe, Pair, maybe, uncurry) -import Yaya.Fold+-- | Instances leak transitively, so while "Yaya.Unsafe.Fold.Instances" exists,+-- it should only be used when it is unavoidable. If you are explicitly+-- folding a structure unsafely, use this function instead of importing that+-- module.+unsafeAna :: (Steppable (->) t f, Functor f) => Coalgebra (->) f a -> a -> t+unsafeAna = hylo embed --- | This can’t be implemented in a total fashion. There is a _similar_ approach+-- | Instances leak transitively, so while "Yaya.Unsafe.Fold.Instances" exists,+-- it should only be used when it is unavoidable. If you are explicitly+-- unfolding a structure unsafely, use this function instead of importing that+-- module.+--+-- Should one prefer `unsafeAna` or `unsafeCata` in cases where both are+-- applicable?+-- - one may provide weaker constraints than the other in certain cases (e.g.,+-- on its own, `unsafeCata` only requires `Projectable` on the source, but+-- `unsafeAna` requires `Steppable` on the target. Depending on what other+-- constraints already exist on the function, either one may ultimately be+-- less constrained.+-- - they may fail differently: `unsafeCata` (folding a potentially-infinite+-- structure) is likely to result in non-termination, whereas `unsafeAna`+-- (building a potentially-infinite structure strictly) is likely to use up+-- the memory or overflow the stack.+unsafeCata :: (Projectable (->) t f, Functor f) => Algebra (->) f a -> t -> a+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.-anaM :: (Monad m, Steppable (->) t f, Traversable f) => CoalgebraM (->) m f a -> a -> m t+anaM ::+ (Monad m, Steppable (->) t f, Traversable f) =>+ CoalgebraM (->) m f a ->+ a ->+ m t anaM = hyloM (pure . embed) -ganaM- :: (Monad m, Monad n, Traversable n, Steppable (->) t f, Traversable f)- => DistributiveLaw (->) n f- -> GCoalgebraM (->) m n f a- -> a -> m t+ganaM ::+ (Monad m, Monad n, Traversable n, Steppable (->) t f, Traversable f) =>+ DistributiveLaw (->) n f ->+ GCoalgebraM (->) m n f a ->+ a ->+ m t ganaM k ψ = anaM (lowerCoalgebraM k ψ) . pure -- | Fusion of an 'ana' and 'cata'.-hylo :: Functor f => Algebra (->) f b -> Coalgebra (->) f a -> a -> b+hylo :: (Functor f) => Algebra (->) f b -> Coalgebra (->) f a -> a -> b hylo φ ψ = go where go = φ . fmap go . ψ -ghylo- :: (Comonad w, Monad m, Functor f)- => DistributiveLaw (->) f w- -> DistributiveLaw (->) m f- -> GAlgebra (->) w f b- -> GCoalgebra (->) m f a- -> a -> b+ghylo ::+ (Comonad w, Monad m, Functor f) =>+ DistributiveLaw (->) f w ->+ DistributiveLaw (->) m f ->+ GAlgebra (->) w f b ->+ GCoalgebra (->) m f a ->+ a ->+ b ghylo w m φ ψ = extract . hylo (lowerAlgebra w φ) (lowerCoalgebra m ψ) . pure -hyloM- :: (Monad m, Traversable f)- => AlgebraM (->) m f b- -> CoalgebraM (->) m f a- -> a -> m b+hyloM ::+ (Monad m, Traversable f) =>+ AlgebraM (->) m f b ->+ CoalgebraM (->) m f a ->+ a ->+ m b hyloM φ ψ = hylo (φ <=< sequenceA <=< getCompose) (Compose . ψ) -ghyloM- :: (Comonad w, Traversable w, Monad m, Traversable f, Monad n, Traversable n)- => DistributiveLaw (->) f w- -> DistributiveLaw (->) n f- -> GAlgebraM (->) m w f b- -> GCoalgebraM (->) m n f a- -> a -> m b+ghyloM ::+ (Comonad w, Traversable w, Monad m, Traversable f, Monad n, Traversable n) =>+ DistributiveLaw (->) f w ->+ DistributiveLaw (->) n f ->+ GAlgebraM (->) m w f b ->+ GCoalgebraM (->) m n f a ->+ a ->+ m b ghyloM w n φ ψ = fmap extract . hyloM (lowerAlgebraM w φ) (lowerCoalgebraM n ψ) . pure -stream'- :: (Projectable (->) t f, Steppable (->) u g, Functor g)- => CoalgebraM (->) Maybe g b- -> (b -> ((b -> b, t) -> u) -> f t -> u)- -> b- -> t -> u+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 where go c x =- maybe (f c (uncurry go . ((&) c *** id)) (project x))- (embed . fmap (flip go x))- (ψ c)+ maybe+ (f c (uncurry go . first (c &)) (project x))+ (embed . fmap (`go` x))+ (ψ c) -- | Gibbons’ metamorphism. It lazily folds a (necessarily infinite) value, -- incrementally re-expanding that value into some new representation.-streamAna- :: (Projectable (->) t f, Steppable (->) u g, Functor g)- => CoalgebraM (->) Maybe g b- -> AlgebraM (->) ((,) (b -> b)) f t- -> b- -> t -> u-streamAna ψ φ = stream' ψ (\_ f -> f . φ)+--+-- __NB__: See https://gist.github.com/sellout/4709e723cb649110af00217486c4466b+-- for some commentary and explanation.+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) -- | 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.-streamGApo- :: (Projectable (->) t f, Steppable (->) u g, Corecursive (->) u g, Functor g)- => Coalgebra (->) g b- -> CoalgebraM (->) Maybe g b- -> (f t -> Maybe (b -> b, t))- -> b- -> t -> u-streamGApo ψ' ψ φ = stream' ψ (\c f -> maybe (ana ψ' c) f . φ)+--+-- __NB__: See https://gist.github.com/sellout/4709e723cb649110af00217486c4466b+-- for some commentary and explanation.+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+streamGApo flush process accum =+ stream' process (\c f -> maybe (ana flush c) f . accum) -corecursivePrism- :: (Steppable (->) t f, Recursive (->) t f, Corecursive (->) t f, Traversable f)- => CoalgebraPrism f a- -> Prism' a t+corecursivePrism ::+ (Steppable (->) t f, Recursive (->) t f, Traversable f) =>+ CoalgebraPrism f a ->+ Prism' a t corecursivePrism alg = prism (cata (review alg)) (anaM (matching alg))
src/Yaya/Unsafe/Fold/Instances.hs view
@@ -1,41 +1,81 @@-{-# options_ghc -Wno-orphans #-}+{-# LANGUAGE CPP #-} +-- __NB__: base-4.17 moves `IsList` to its own module, which avoids the unsafety+-- of importing "GHC.Exts". With prior versions of base, we at least+-- mark the module @Trustworthy@.+#if MIN_VERSION_base(4, 17, 0)+{-# LANGUAGE Safe #-}+#else+{-# LANGUAGE Trustworthy #-}+#endif+{-# LANGUAGE TypeFamilies #-}+{-# OPTIONS_GHC -Wno-orphans #-}+ -- | Type class instances that use direct recursion in a potentially partial -- way. This is separated from the rest of `Yaya.Unsafe.Fold` because you can -- neither control nor qualify the import of instances. Therefore this module--- is _extra_ dangerous, as having these instances available applies to the+-- is /extra/ dangerous, as having these instances available applies to the -- entire module they’re imported into. ----- This contains instances that you might _expect_ to see, but which aren’t--- actually total. For example, folding a lazy list `[a]` is _not_ guaranteed+-- This contains instances that you might /expect/ to see, but which aren’t+-- actually total. For example, folding a lazy list @[a]@ is /not/ guaranteed -- to terminate.-module Yaya.Unsafe.Fold.Instances where+module Yaya.Unsafe.Fold.Instances+ ( seqFreeT,+ )+where -import Control.Comonad.Cofree-import Control.Comonad.Env-import Control.Monad.Trans.Free-import Data.Functor.Classes-import Data.List.NonEmpty+import safe "base" Control.Category (Category ((.)))+import safe "base" Data.Eq (Eq ((==)))+import safe "base" Data.Foldable (Foldable)+import safe "base" Data.Function (flip)+import safe "base" Data.Functor (Functor, (<$>))+import safe "base" Data.Functor.Classes (Eq1, Show1)+import safe "base" Data.List.NonEmpty (NonEmpty) -import Yaya.Fold-import Yaya.Fold.Native-import Yaya.Pattern-import qualified Yaya.Unsafe.Fold as Unsafe+-- See comment on @{-# LANGUAGE Safe #-}@ above.+#if MIN_VERSION_base(4, 17, 0)+import "base" GHC.IsList (IsList (Item, fromList, fromListN, toList))+#else+import "base" GHC.Exts (IsList (Item, fromList, fromListN, toList))+#endif+import safe "base" Text.Show (Show (showsPrec))+import safe "comonad" Control.Comonad.Env (EnvT)+import safe "free" Control.Comonad.Cofree (Cofree)+import safe "free" Control.Monad.Trans.Free (Free, FreeF (Free, Pure), free)+import safe "yaya" Yaya.Fold+ ( Corecursive (ana),+ DistributiveLaw,+ Mu,+ Nu,+ Projectable (project),+ Recursive (cata),+ Steppable (embed),+ recursiveEq,+ recursiveShowsPrec,+ )+import safe "yaya" Yaya.Fold.Native (Cofix, Fix)+import safe "yaya" Yaya.Pattern (AndMaybe, XNor)+import safe "this" Yaya.Unsafe.Applied (unsafeFromList)+import safe qualified "this" Yaya.Unsafe.Fold as Unsafe -instance Functor f => Recursive (->) (Fix f) f where+instance (Functor f) => Corecursive (->) (Fix f) f where+ ana = Unsafe.hylo embed++instance (Functor f) => Recursive (->) (Cofix f) f where cata = flip Unsafe.hylo project -instance (Functor f, Foldable f, Eq1 f) => Eq (Fix f) where+instance (Functor f, Foldable f, Eq1 f) => Eq (Cofix f) where (==) = recursiveEq -instance (Functor f, Show1 f) => Show (Fix f) where+instance (Functor f, Show1 f) => Show (Cofix f) where showsPrec = recursiveShowsPrec -instance Functor f => Corecursive (->) (Mu f) f where- ana = Unsafe.hylo embed+instance (Functor f) => Corecursive (->) (Mu f) f where+ ana = Unsafe.unsafeAna -instance Functor f => Recursive (->) (Nu f) f where- cata = flip Unsafe.hylo project+instance (Functor f) => Recursive (->) (Nu f) f where+ cata = Unsafe.unsafeCata instance (Functor f, Foldable f, Eq1 f) => Eq (Nu f) where (==) = recursiveEq@@ -44,25 +84,48 @@ showsPrec = recursiveShowsPrec instance Recursive (->) [a] (XNor a) where- cata = flip Unsafe.hylo project+ cata = Unsafe.unsafeCata instance Recursive (->) (NonEmpty a) (AndMaybe a) where- cata = flip Unsafe.hylo project+ cata = Unsafe.unsafeCata -instance Functor f => Recursive (->) (Cofree f a) (EnvT a f) where- cata = flip Unsafe.hylo project+instance (Functor f) => Recursive (->) (Cofree f a) (EnvT a f) where+ cata = Unsafe.unsafeCata -instance Functor f => Recursive (->) (Free f a) (FreeF f a) where- cata = flip Unsafe.hylo project+instance (Functor f) => Recursive (->) (Free f a) (FreeF f a) where+ cata = Unsafe.unsafeCata -- TODO: If we can generalize this to an arbitrary 'Recursive (->) t (FreeF h a)' -- then it would no longer be unsafe.-seqFreeT- :: (Functor f, Functor h)- => DistributiveLaw (->) h f- -> DistributiveLaw (->) (Free h) f+seqFreeT ::+ (Functor f, Functor h) =>+ DistributiveLaw (->) h f ->+ DistributiveLaw (->) (Free h) f seqFreeT k = cata- (\case- Pure a -> free . Pure <$> a- Free ft -> free . Free <$> k ft)+ ( \case+ Pure a -> free . Pure <$> a+ Free ft -> free . Free <$> k ft+ )++-- | `fromList` in this instance is unsafe, but `fromListN` is safe, because we+-- have a finite length to fold.+--+-- This means that most uses of @OverloadedLists@ should be fine, but not the+-- range (`..`) syntax.+instance IsList (Fix (XNor a)) where+ type Item (Fix (XNor a)) = a+ fromList = unsafeFromList+ fromListN = fromListN+ toList = toList++-- | `fromList` in this instance is unsafe, but `fromListN` is safe, because we+-- have a finite length to fold.+--+-- This means that most uses of @OverloadedLists@ should be fine, but not the+-- range (`..`) syntax.+instance IsList (Mu (XNor a)) where+ type Item (Mu (XNor a)) = a+ fromList = unsafeFromList+ fromListN = fromListN+ toList = toList
src/Yaya/Unsafe/Zoo.hs view
@@ -1,65 +1,104 @@-module Yaya.Unsafe.Zoo where+{-# LANGUAGE Safe #-} -import Control.Arrow-import Control.Comonad.Cofree-import Control.Comonad.Env-import Control.Monad.Trans.Free-import Data.Functor.Compose-import Data.Functor.Identity-import Data.Bitraversable+module Yaya.Unsafe.Zoo+ ( chrono,+ codyna,+ coelgot,+ cotraverse,+ dyna,+ elgot,+ fstream,+ futu,+ gpostpro,+ gprepro,+ stream,+ zygoHistoPrepro,+ )+where -import Yaya.Fold-import Yaya.Fold.Native-import Yaya.Pattern-import qualified Yaya.Unsafe.Fold as Unsafe-import qualified Yaya.Unsafe.Fold.Instances as Unsafe -- NB: extremely unsafe+import "base" Control.Applicative (Applicative (pure))+import "base" Control.Category (Category (id, (.)))+import "base" Control.Monad (Monad)+import "base" Data.Bifunctor (Bifunctor (second))+import "base" Data.Bitraversable (Bitraversable (bitraverse))+import "base" Data.Function (const, flip)+import "base" Data.Functor (Functor (fmap))+import "base" Data.Functor.Compose (Compose (Compose, getCompose))+import "base" Data.Functor.Identity (Identity (Identity, runIdentity))+import "base" Data.Traversable (Traversable)+import "comonad" Control.Comonad (Comonad)+import "comonad" Control.Comonad.Env (EnvT)+import "free" Control.Comonad.Cofree (Cofree)+import "free" Control.Monad.Trans.Free (Free)+import "yaya" Yaya.Fold+ ( Algebra,+ Coalgebra,+ Corecursive (ana),+ DistributiveLaw,+ ElgotAlgebra,+ ElgotCoalgebra,+ GAlgebra,+ GCoalgebra,+ Projectable (project),+ Recursive (cata),+ Steppable (embed),+ distEnvT,+ distIdentity,+ gana,+ seqIdentity,+ )+import "yaya" Yaya.Fold.Common (diagonal, fromEither)+import "yaya" Yaya.Fold.Native (distCofreeT)+import "yaya" Yaya.Pattern (Either, Maybe (Nothing), Pair ((:!:)), XNor (Both, Neither))+import qualified "this" Yaya.Unsafe.Fold as Unsafe+import qualified "this" Yaya.Unsafe.Fold.Instances as Unsafe -- FIXME: extremely unsafe -chrono- :: Functor f- => GAlgebra (->) (Cofree f) f b- -> GCoalgebra (->) (Free f) f a- -> a- -> b+chrono ::+ (Functor f) =>+ GAlgebra (->) (Cofree f) f b ->+ GCoalgebra (->) (Free f) f a ->+ a ->+ b chrono = Unsafe.ghylo (distCofreeT id) (Unsafe.seqFreeT id) -codyna :: Functor f => Algebra (->) f b -> GCoalgebra (->) (Free f) f a -> a -> b+codyna :: (Functor f) => Algebra (->) f b -> GCoalgebra (->) (Free f) f a -> a -> b codyna φ = Unsafe.ghylo distIdentity (Unsafe.seqFreeT id) (φ . fmap runIdentity) -- | [Recursion Schemes for Dynamic Programming](https://www.researchgate.net/publication/221440162_Recursion_Schemes_for_Dynamic_Programming)-dyna :: Functor f => GAlgebra (->) (Cofree f) f b -> Coalgebra (->) f a -> a -> b+dyna :: (Functor f) => GAlgebra (->) (Cofree f) f b -> Coalgebra (->) f a -> a -> b dyna φ ψ = Unsafe.ghylo (distCofreeT id) seqIdentity φ (fmap Identity . ψ) -- | Unlike most `Unsafe.hylo`s, `elgot` composes an algebra and coalgebra in a -- way that allows information to move between them. The coalgebra can return, -- effectively, a pre-folded branch, short-circuiting parts of the process.-elgot :: Functor f => Algebra (->) f b -> ElgotCoalgebra (->) (Either b) f a -> a -> b-elgot φ ψ = Unsafe.hylo ((id ||| φ) . getCompose) (Compose . ψ)+elgot :: (Functor f) => Algebra (->) f b -> ElgotCoalgebra (->) (Either b) f a -> a -> b+elgot φ ψ = Unsafe.hylo (fromEither . second φ . getCompose) (Compose . ψ) -- | The dual of `elgot`, `coelgot` allows the /algebra/ to short-circuit in -- some cases – operating directly on a part of the seed.-coelgot :: Functor f => ElgotAlgebra (->) ((,) a) f b -> Coalgebra (->) f a -> a -> b-coelgot φ ψ = Unsafe.hylo (φ . getCompose) (Compose . (id &&& ψ))+coelgot :: (Functor f) => ElgotAlgebra (->) (Pair a) f b -> Coalgebra (->) f a -> a -> b+coelgot φ ψ = Unsafe.hylo (φ . getCompose) (Compose . second ψ . diagonal) futu :: (Corecursive (->) t f, Functor f) => GCoalgebra (->) (Free f) f a -> a -> t futu = gana (Unsafe.seqFreeT id) -gprepro- :: (Steppable (->) t f, Recursive (->) t f, Functor f, Comonad w)- => DistributiveLaw (->) f w- -> GAlgebra (->) w f a- -> (forall x. f x -> f x)- -> t- -> a+gprepro ::+ (Steppable (->) t f, Recursive (->) t f, Functor f, Comonad w) =>+ DistributiveLaw (->) f w ->+ GAlgebra (->) w f a ->+ (forall x. f x -> f x) ->+ t ->+ a gprepro k φ e = Unsafe.ghylo k seqIdentity φ (fmap (Identity . cata (embed . e)) . project) -gpostpro- :: (Steppable (->) t f, Corecursive (->) t f, Functor f, Monad m)- => DistributiveLaw (->) m f- -> (forall x. f x -> f x)- -> GCoalgebra (->) m f a- -> a- -> t+gpostpro ::+ (Steppable (->) t f, Corecursive (->) t f, Functor f, Monad m) =>+ DistributiveLaw (->) m f ->+ (forall x. f x -> f x) ->+ GCoalgebra (->) m f a ->+ a ->+ t gpostpro k e = Unsafe.ghylo distIdentity k (embed . fmap (ana (e . project) . runIdentity)) @@ -69,22 +108,24 @@ -- | Basically the definition from Gibbons’ paper, except the flusher (@h@) is a -- `Coalgebra` instead of an `unfold`.-fstream- :: Coalgebra (->) (XNor c) b- -> (b -> a -> b)- -> Coalgebra (->) (XNor c) b- -> b- -> [a]- -> [c]+fstream ::+ Coalgebra (->) (XNor c) b ->+ (b -> a -> b) ->+ Coalgebra (->) (XNor c) b ->+ b ->+ [a] ->+ [c] fstream f g h = Unsafe.streamGApo- h- (\b -> case f b of- Neither -> Nothing- other -> Just other)- (\case- Neither -> Nothing- Both a x' -> Just (flip g a, x'))+ h+ ( \b -> case f b of+ Neither -> Nothing+ other -> pure other+ )+ ( \case+ Neither -> Nothing+ Both a x' -> pure (flip g a :!: x')+ ) -- snoc :: [a] -> a -> [a] -- snoc x a = x ++ [a]@@ -93,24 +134,24 @@ -- x = stream project snoc [] [1, 2, 3, 4, 5] -- TODO: Weaken `Monad` constraint to `Applicative`.-cotraverse- :: ( Steppable (->) t (f a)- , Steppable (->) u (f b)- , Corecursive (->) u (f b)- , Bitraversable f- , Traversable (f b)- , Monad m)- => (a -> m b)- -> t- -> m u+cotraverse ::+ ( Steppable (->) t (f a),+ Steppable (->) u (f b),+ Bitraversable f,+ Traversable (f b),+ Monad m+ ) =>+ (a -> m b) ->+ t ->+ m u cotraverse f = Unsafe.anaM (bitraverse f pure . project) -- | Zygohistomorphic prepromorphism – everyone’s favorite recursion scheme joke.-zygoHistoPrepro- :: (Steppable (->) t f, Recursive (->) t f, Functor f)- => (f b -> b)- -> (f (EnvT b (Cofree f) a) -> a)- -> (forall c. f c -> f c)- -> t- -> a+zygoHistoPrepro ::+ (Steppable (->) t f, Recursive (->) t f, Functor f) =>+ (f b -> b) ->+ (f (EnvT b (Cofree f) a) -> a) ->+ (forall c. f c -> f c) ->+ t ->+ a zygoHistoPrepro φ' = gprepro (distEnvT φ' (distCofreeT id))
+ tests/doctests.hs view
@@ -0,0 +1,12 @@+{-# LANGUAGE Unsafe #-}++module Main (main) where++import "base" Data.Function (($))+import "base" Data.Semigroup (Semigroup ((<>)))+import "base" System.IO (IO)+import "doctest" Test.DocTest (doctest)+import "this" Build_doctests (flags, module_sources, pkgs)++main :: IO ()+main = doctest $ flags <> pkgs <> module_sources
yaya-unsafe.cabal view
@@ -1,52 +1,214 @@-name: yaya-unsafe-version: 0.2.0.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 extends Yaya to provide those operations. It’s in a- separate package (and modules) in order to make sure its- use is very intentional and also relatively obvious to- those reading your code. It’s recommended that you import- these modules qualified and, in particular, all the type- class instances here have been pulled into a separate- module to avoid accidentally bringing them into scope.-homepage: https://github.com/sellout/yaya#readme-author: Greg Pfeil-maintainer: greg@technomadic.org-copyright: 2017 Greg Pfeil-license: AGPL-3-license-file: LICENSE-category: Recursion-build-type: Simple-extra-source-files: CHANGELOG.md- , README.md-cabal-version: >=1.10+cabal-version: 3.0 -library- hs-source-dirs: src- exposed-modules: Yaya.Unsafe.Fold- , Yaya.Unsafe.Fold.Instances- , Yaya.Unsafe.Zoo- build-depends: base >= 4.7 && < 5- , bifunctors- , comonad- , either- , free- , lens- , yaya >= 0.3.0- default-extensions: ConstraintKinds- , DeriveTraversable- , FlexibleContexts- , FlexibleInstances- , FunctionalDependencies- , LambdaCase- , MultiParamTypeClasses- , RankNTypes- , ScopedTypeVariables- , StrictData- , TupleSections- default-language: Haskell2010+name: yaya-unsafe+version: 0.3.3.0+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+ extends Yaya to provide those operations. It’s in a separate+ package (and modules) in order to make sure its use is very+ intentional and also relatively obvious to those reading your code.+ It’s recommended that you import these modules qualified and, in+ particular, all the type class instances here have been pulled into+ a separate module to avoid accidentally bringing them into scope.+author: Greg Pfeil <greg@technomadic.org>+maintainer: Greg Pfeil <greg@technomadic.org>+copyright: 2017 Greg Pfeil+homepage: https://github.com/sellout/yaya#readme+bug-reports: https://github.com/sellout/yaya/issues+category: Recursion+build-type: Custom+license: AGPL-3.0-or-later+license-files:+ LICENSE+extra-source-files:+ CHANGELOG.md+ README.md+tested-with:+ GHC == {+-- GHCup Nixpkgs+ 8.6.1,+ 8.8.1, 8.8.4,+ 8.10.1,+ 9.0.1,+ 9.2.1,+ 9.4.1, 9.4.8,+ 9.6.1,+ 9.8.1+ } source-repository head- type: git+ type: git location: https://github.com/sellout/yaya++-- This mimics the GHC2021 extension+-- (https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/control.html?highlight=doandifthenelse#extension-GHC2021),+-- but supporting compilers back to GHC 7.10. If the oldest supported compiler+-- is GHC 9.2, then this stanza can be removed and `import: GHC2021` can be+-- replaced by `default-language: GHC2021`.+common GHC2021+ default-language: Haskell2010+ default-extensions:+ BangPatterns+ BinaryLiterals+ ConstraintKinds+ DeriveDataTypeable+ DeriveGeneric+ -- DeriveLift -- uncomment if the oldest supported version is GHC 8.10.1++ DeriveTraversable+ DerivingStrategies+ DoAndIfThenElse+ EmptyCase+ ExistentialQuantification+ FlexibleContexts+ FlexibleInstances+ GADTSyntax+ GeneralizedNewtypeDeriving+ HexFloatLiterals+ -- ImportQualifiedPost -- uncomment if the oldest supported version is GHC 8.10.1++ InstanceSigs+ LambdaCase+ MagicHash+ MonadComprehensions+ MonomorphismRestriction+ MultiParamTypeClasses+ NamedFieldPuns+ NamedWildCards+ NumericUnderscores+ PolyKinds+ PostfixOperators+ RankNTypes+ ScopedTypeVariables+ StandaloneDeriving+ -- StandaloneKindSignatures -- uncomment if the oldest supported version is GHC 8.10.1++ TupleSections+ TypeApplications+ TypeOperators+ UnicodeSyntax+ NoExplicitNamespaces++common defaults+ import: GHC2021+ build-depends:+ base ^>= {4.12.0, 4.13.0, 4.14.0, 4.15.0, 4.16.0, 4.17.0, 4.18.0, 4.19.0},+ ghc-options:+ -Weverything+ -- Type inference good.+ -Wno-missing-local-signatures+ -- Warns even when `Unsafe` is explicit, not inferred. See+ -- https://gitlab.haskell.org/ghc/ghc/-/issues/16689+ -Wno-unsafe+ -- TODO: prune these warnings+ -Wno-all-missed-specialisations+ -fpackage-trust+ -trust base+ if impl(ghc < 8.8.1)+ ghc-options:+ -- This used to warn even when `Safe` was explicit.+ -Wno-safe+ if impl(ghc >= 8.10.1)+ ghc-options:+ -- If we didn’t allow inferred-safe imports, nothing would be `Safe`.+ -Wno-inferred-safe-imports+ -- We support GHC versions without qualified-post.+ -Wno-prepositive-qualified-module+ -- `-trust` triggers this warning when applied to transitive dependencies.+ -Wno-unused-packages+ if impl(ghc >= 9.2.1)+ ghc-options:+ -- We support GHC versions without kind signatures.+ -Wno-missing-kind-signatures+ if impl(ghc >= 9.8.1)+ ghc-options:+ -- We support GHC versions without kind signatures.+ -Wno-missing-poly-kind-signatures+ -- Inference good.+ -Wno-missing-role-annotations+ default-extensions:+ DefaultSignatures+ ExplicitNamespaces+ FunctionalDependencies+ LiberalTypeSynonyms+ -- replace with `LexicalNegation` if the oldest supported version is GHC 9.0.1++ NegativeLiterals+ PackageImports+ ParallelListComp+ -- QualifiedDo - uncomment if the oldest supported version is GHC 9.0.1++ RecursiveDo+ -- RequiredTypeArguments - uncomment if the oldest supported version is GHC 9.10.1++ RoleAnnotations+ StrictData+ TemplateHaskellQuotes+ TransformListComp+ NoGeneralizedNewtypeDeriving+ NoImplicitPrelude+ NoMonomorphismRestriction+ NoPatternGuards+ NoTypeApplications++custom-setup+ setup-depends:+ -- TODO: Remove `Cabal` dep once haskell/cabal#3751 is fixed.+ Cabal ^>= {3.0.0, 3.2.0, 3.4.0, 3.6.0, 3.8.0, 3.10.0},+ base ^>= {4.12.0, 4.13.0, 4.14.0, 4.15.0, 4.16.0, 4.17.0, 4.18.0, 4.19.0},+ cabal-doctest ^>= 1.0.0++library+ import: defaults+ hs-source-dirs:+ src+ exposed-modules:+ Yaya.Unsafe.Applied+ Yaya.Unsafe.Fold+ Yaya.Unsafe.Fold.Instances+ Yaya.Unsafe.Zoo+ build-depends:+ bifunctors,+ comonad,+ free,+ lens,+ yaya >= 0.5.1,+ ghc-options:+ -trust adjunctions+ -trust array+ -trust base-orphans+ -trust binary+ -trust bytestring+ -trust containers+ -trust distributive+ -trust exceptions+ -trust ghc-prim+ -trust lens+ -trust profunctors+ -trust semigroupoids+ -trust stm+ -trust text+ -trust transformers-compat+ if impl(ghc < 9.6)+ ghc-options:+ -trust foldable1-classes-compat++test-suite doctests+ import: defaults+ type: exitcode-stdio-1.0+ hs-source-dirs: tests+ main-is: doctests.hs+ build-depends:+ doctest ^>= {0.15.0, 0.16.0, 0.17.0, 0.18.0, 0.19.0, 0.20.0, 0.21.0, 0.22.0},+ yaya-unsafe,+ -- TODO: The sections below here are necessary because we don’t have control+ -- over the generated `Build_doctests.hs` file. So we have to silence+ -- all of its warnings one way or another.+ ghc-options:+ -Wno-missing-export-lists+ -Wno-missing-import-lists+ -Wno-safe+ if impl(ghc >= 8.8.1)+ ghc-options:+ -- This used to warn even when `Safe` was explicit.+ -Wno-missing-deriving-strategies+ default-extensions:+ -- Since we can’t add `{-# LANGUAGE Safe -#}` to the generated+ -- “Build_doctests.hs”, we set it here, and that means it has to match+ -- doctests.hs, which is `Unsafe`.+ Unsafe