-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Standard library for linear types. -- -- Please see README.md. @package linear-base @version 0.3.0 -- | This module provides type-level helpers and classes to deal with n-ary -- functions. -- -- See make, elim and elim for use-cases. module Data.Arity.Linear data Peano Z :: Peano S :: Peano -> Peano -- | Converts a GHC type-level Nat to a structural type-level -- natural (Peano). type family NatToPeano n -- | Converts a structural type-level natural (Peano) to a GHC -- type-level Nat. type family PeanoToNat n -- | FunN n a b represents a function taking n -- linear arguments of type a and returning a result of type -- b. type family FunN n a b -- | The Arity type family exists to help the type checker fill in -- blanks. Chances are that you can safely ignore Arity completely -- if it's in the type of a function you care. But read on if you are -- curious. -- -- The idea is that in a function like elim some of the type -- arguments are redundant. The function has an ambiguous type, so you -- will always have to help the compiler either with a type annotation or -- a type application. But there are several complete ways to do so. In -- elim, if you give the values of n, a, and -- b, then you can deduce the value of f (indeed, it's -- FunN n a b). With Arity we can go in the other -- direction: if b and f are both known, then we know -- that n is Arity b f -- -- Arity returns a Nat rather than a Peano because -- the result is never consumed. It exists to infer arguments to -- functions such as elim from the other arguments if they are -- known. -- -- Arity could theorically be an associated type family to -- the IsFunN type class. But it's better to make it a closed type -- family (which can't be associated to a type class) because it lets us -- give a well-defined error case. In addition, GHC cannot see that 0 -- /= 1 + (? :: Nat) and as a result we get some overlap which is -- only allowed in (ordered) closed type families. type family Arity b f -- | The IsFun type class is meant to help the type checker fill -- in blanks. Chances are that you can safely ignore IsFun -- completely if it's in the type of a function you care. But read on if -- you are curious. -- -- The type class IsFun is a kind of inverse to FunN, it -- is meant to be read as IsFunN a b f if and only if -- there exists n such that f = FunN n a b -- (n can be retrieved as Arity b f or -- ArityV f). -- -- The reason why Arity (read its documentation first) is not -- sufficient for our purpose, is that it can find n if -- f is a linear function of the appropriate shape. But what if -- f is partially undetermined? Then it is likely that -- Arity will be stuck. But we know, for instance, that if f = -- a1 %1 -> a2 %1 -> c then we must have a1 ~ a2. The -- trick is that instance resolution of IsFun will add -- unification constraints that the type checker has to solve. Look in -- particular at the instance IsFunN a b (a' %p -> -- f)): it matches liberally, so triggers on quite underdetermined -- f, but has equality constraints in its context which will -- help the type checker. class IsFunN a b f -- | This module provides linear functions on the standard Bool -- type. module Data.Bool.Linear data Bool False :: Bool True :: Bool -- | True iff both are True. NOTE: this is strict -- and not lazy! (&&) :: Bool %1 -> Bool %1 -> Bool infixr 3 && -- | True iff either is True NOTE: this is strict -- and not lazy! (||) :: Bool %1 -> Bool %1 -> Bool infixr 2 || -- | not b is True iff b is False NOTE: -- this is strict and not lazy! not :: Bool %1 -> Bool -- | otherwise is defined as the value True. It helps to make -- guards more readable. eg. -- -- 
--   f x | x < 0     = ...
--       | otherwise = ...
--
otherwise :: Bool -- | FixupMetaData a g copies the metadata from the -- GHC.Generics.Generic representation of -- a to the representation g. -- -- FixupMetaData1 f g does something similar when f -- Any is an instance of Generic and g is a -- Rep1. See the individual type documentation for details. -- -- This is intended to help users instantiate Rep and Rep1 -- for types with nonlinear or multiplicity-polymorphic fields. -- --

Suggested use

-- -- You will need to derive a GHC.Generics.Generic -- instance for the type. This is used to obtain the correct metadata. -- -- Next you need to construct a Rep and/or Rep1 for -- your type, ignoring the metadata. -- -- Constructing the actual representations can be a bit annoying, but GHC -- can help. -- --

For Rep

-- -- Once you have derived GHC.Generics.Generic for -- your type, define a value like -- -- 
--   test :: Rep T a
--   test = _
--
-- -- Then compile. The stripped representation you need will be in the -- error message. -- --

For Rep1

-- -- Construct a type with the same shape as the one you wish to -- instantiate, but with only linear fields. Strictness annotations and -- UNPACK pragmas are irrelevant here. -- -- Instantiate Generics.Linear.Generic1 for the -- lookalike using deriveGeneric1 and follow the same procedure as -- above (but with Rep1 T, of course) to get a -- metadata-stripped representation. -- --

For either

-- -- To avoid confusion, replace at least the package and module names in -- the representation with Any. Wrap MP1 around any -- nonlinear/representation polymorphic fields, just under the -- S1 type constructor. The first type argument of MP1 -- will indicate the multiplicity. module Prelude.Linear.GenericUtil -- | FixupMetaData a g copies the metadata from the -- GHC.Generics.Generic representation of -- a to the representation g. It also checks that the -- structure of Rep a is the same as g, except that -- g may have MP1 applications under some S1 -- constructors. -- --

Example

-- -- 
--   instance Generic (Ur a) where
--     type Rep (Ur a) = FixupMetaData (Ur a)
--           (D1 Any
--             (C1 Any
--               (S1 Any
--                 (MP1 'Many (Rec0 a)))))
--
type FixupMetaData (a :: Type) (g :: Type -> Type) = Fixup (Rep a) g -- | FixupMetaData1 f g copies the metadata from the -- GHC.Generics.Generic representation of f -- Any to the representation g. It also checks that -- the overall structure of Rep (f Any) is the same as -- g, but does not check that their fields match. -- --

Example

-- -- 
--   instance Generic1 Ur where
--     type Rep1 Ur = FixupMetaData1 Ur
--            (D1 Any
--               (C1 Any
--                  (S1 Any
--                     (MP1 'Many Par1))))
--
type FixupMetaData1 (f :: k -> Type) (g :: k -> Type) = Fixup1 (Rep (f Any)) g type family RemoveMetaData (f :: k -> Type) :: k -> Type -- | Prior to GHC 9.4, linear-base defined its own versions of -- Generically and Generically1. As a temporary -- workaround to enable compilation on both GHC 9.4 and 9.2, this module -- exposes linear-base's own implementations of those types, while the -- 9.4 version simply re-exports Generics.Linear. module Prelude.Linear.Internal.Generically -- | A datatype whose instances are defined generically, using the -- Generic representation. Generic instances can be derived via -- Generically A using -XDerivingVia. newtype Generically a Generically :: a -> Generically a -- | A type whose instances are defined generically, using the -- Generic1 representation. Generically1 is a higher-kinded -- version of Generically. -- -- Generic instances can be derived for type constructors via -- Generically1 F using -XDerivingVia. newtype Generically1 f a Generically1 :: f a -> Generically1 f a module Prelude.Linear.Generically unGenerically :: Generically a %1 -> a unGenerically1 :: Generically1 f a %1 -> f a -- | As of GHC 9.4, ~ is a type operator exported from -- Equality rather than a language construct. As a temporary -- workaround to enable compilation on both GHC 9.4 and 9.2, this module -- is empty, while the GHC 9.4 version re-exports the new type operator. -- As a result, files which depend on this module will likely have -- -Wno-unused-imports enabled (and potentially also -Wno-dodgy exports -- if they re-export it). These should be removed once support for GHC -- 9.2 is dropped. module Prelude.Linear.Internal.TypeEq -- | An ergonomic class for unsatisfiable constraints. This is based on the -- trivial-constraint package and the Unsatisfiable -- proposal Once that proposal is implemented, we can use it. module Prelude.Linear.Unsatisfiable -- | An unsatisfiable constraint with a user-provided error message. Under -- an Unsatisfiable constraint, users can use -- unsatisfiable to get a value of any type (and runtime -- representation) they desire. For example, -- -- 
--   instance Unsatisfiable
--     ('Text "V1 cannot have an Applicative instance because it cannot implement pure")
--       => Applicative V1 where
--     pure = unsatisfiable
--     (*) = unsatisfiable
--
class (Bottom, TypeError e) => Unsatisfiable (e :: ErrorMessage) -- | Produce a value of any type (and runtime representation) under an -- Unsatisfiable or Bottom constraint. unsatisfiable :: forall {rep} (a :: TYPE rep). Bottom => a -- | A constraint that cannot be satisfied. Users should normally use -- Unsatisfiable instead of using this class directly. class Any => Bottom -- | Unsafe coercions for linearly typed code. -- -- Use this module to coerce non-linear functions to be linear or values -- bound linearly to be another type. All functions in this module -- are unsafe. -- -- Hence: -- -- module Unsafe.Linear -- | Linearly typed unsafeCoerce coerce :: forall a b. a %1 -> b -- | Converts an unrestricted function into a linear function toLinear :: forall (r1 :: RuntimeRep) (r2 :: RuntimeRep) (a :: TYPE r1) (b :: TYPE r2) p x. (a %p -> b) %1 -> a %x -> b -- | Like toLinear but for two-argument functions toLinear2 :: forall (r1 :: RuntimeRep) (r2 :: RuntimeRep) (r3 :: RuntimeRep) (a :: TYPE r1) (b :: TYPE r2) (c :: TYPE r3) p q x y. (a %p -> b %q -> c) %1 -> a %x -> b %y -> c -- | Like toLinear but for three-argument functions toLinear3 :: forall (r1 :: RuntimeRep) (r2 :: RuntimeRep) (r3 :: RuntimeRep) (r4 :: RuntimeRep) (a :: TYPE r1) (b :: TYPE r2) (c :: TYPE r3) (d :: TYPE r4) p q r x y z. (a %p -> b %q -> c %r -> d) %1 -> a %x -> b %y -> c %z -> d -- | toLinearN subsumes the functionality of toLinear1, -- toLinear2, and toLinear3. In particular, toLinearN -- @n unsafely changes the multiplicities of the first n -- arrows from any multiplicity to any other multiplicity. To be explicit -- about how each multiplicity is being changed, you can use additional -- type arguments. -- --

Examples

-- -- 
--   toLinearN @2 :: (a %m-> b %n-> Int) %1-> a %x-> b %y-> Int
--   toLinearN @3 @(_ %m-> _ -> _ %1-> _) @(_ %1-> _ %1-> _ %x-> _)
--     :: (a %m-> b -> c %1-> d) %1-> (a %1-> b %1-> c %x-> d)
--   toLinear3 = toLinearN @3
--
toLinearN :: forall n f g. ToLinearN n f g => f %1 -> g -- | ToLinearN n f g means that f and g are the -- same with the possible exception of the multiplicities of the first -- n arrows. class ToLinearN n f g -- | Given that f and g are the same, with the possible -- exception of the multiplicities of the first n arrows, -- unsafeLinearityProofN @n @f @g is a fake proof that -- f and g are identical. This is used primarily in the -- definition of toLinearN, but it can also be used, for example, -- to coerce a container of functions: -- -- 
--   linearMany :: forall a b c. [a -> b -> c] %1-> [a %1-> b %1-> c]
--   linearMany = castWithUnsafe (applyUnsafe (UnsafeRefl []) $
--     unsafeLinearityProofN 2 (a -> b -> c) (a %1-> b %1-> c))
--   
--   applyUnsafe :: UnsafeEquality f g -> UnsafeEquality x y -> UnsafeEquality (f x) (g y)
--   applyUnsafe UnsafeRefl UnsafeRefl = UnsafeRefl
--   
--   castWithUnsafe :: UnsafeEquality x y -> x %1-> y
--   castWithUnsafe UnsafeRefl x = x
--
-- -- The rather explicit handling of coercions seems to be necessary, -- unfortunately, presumably due to the way GHC eagerly rejects equality -- constraints it sees as definitely unsatisfiable. unsafeLinearityProofN :: ToLinearN n f g => UnsafeEquality f g instance (Unsafe.Linear.ToLinearN' ni f g, ni GHC.Types.~ Unsafe.Linear.ToINat n) => Unsafe.Linear.ToLinearN n f g instance (a GHC.Types.~ b) => Unsafe.Linear.ToLinearN' 'Unsafe.Linear.Z a b instance (Unsafe.Linear.ToLinearN' k fb gb, x GHC.Types.~~ (a -> fb), y GHC.Types.~~ (a -> gb)) => Unsafe.Linear.ToLinearN' ('Unsafe.Linear.S k) x y -- | This module provides linear functions commonly used on tuples. module Data.Tuple.Linear fst :: Consumable b => (a, b) %1 -> a snd :: Consumable a => (a, b) %1 -> b swap :: (a, b) %1 -> (b, a) curry :: ((a, b) %p -> c) %q -> a %p -> b %p -> c uncurry :: (a %p -> b %p -> c) %q -> (a, b) %p -> c -- | This module provides linear versions of Monoid and related -- classes. module Data.Monoid.Linear -- | A linear monoid is a linear semigroup with an identity on the binary -- operation. -- -- Laws (same as Monoid): * ∀ x ∈ G, x <> mempty = mempty -- <> x = x class Semigroup a => Monoid a mempty :: Monoid a => a mconcat :: Monoid a => [a] %1 -> a mappend :: Monoid a => a %1 -> a %1 -> a -- | A linear semigroup a is a type with an associative binary -- operation <> that linearly consumes two as. -- -- Laws (same as Semigroup): * ∀ x ∈ G, y ∈ G, z ∈ G, x <> -- (y <> z) = (x <> y) <> z class Semigroup a (<>) :: Semigroup a => a %1 -> a %1 -> a infixr 6 <> -- | An Endo a is just a linear function of type a -- %1-> a. This has a classic monoid definition with id -- and (.). newtype Endo a Endo :: (a %1 -> a) -> Endo a -- | A linear application of an Endo. appEndo :: Endo a %1 -> a %1 -> a -- | DerivingVia combinator for Semigroup (resp. -- Monoid) given linear Semigroup (resp. Monoid). -- -- 
--   newtype Endo a = Endo (a %1-> a)
--     deriving (Prelude.Semigroup) via NonLinear (Endo a)
--
newtype NonLinear a NonLinear :: a -> NonLinear a -- | Boolean monoid under conjunction (&&). -- -- 
--   >>> getAll (All True <> mempty <> All False)
--   False
--
-- -- 
--   >>> getAll (mconcat (map (\x -> All (even x)) [2,4,6,7,8]))
--   False
--
newtype All All :: Bool -> All [getAll] :: All -> Bool -- | Boolean monoid under disjunction (||). -- -- 
--   >>> getAny (Any True <> mempty <> Any False)
--   True
--
-- -- 
--   >>> getAny (mconcat (map (\x -> Any (even x)) [2,4,6,7,8]))
--   True
--
newtype Any Any :: Bool -> Any [getAny] :: Any -> Bool newtype First a First :: a -> First a [getFirst] :: First a -> a newtype Last a Last :: a -> Last a [getLast] :: Last a -> a -- | The dual of a Monoid, obtained by swapping the arguments of -- mappend. -- -- 
--   >>> getDual (mappend (Dual "Hello") (Dual "World"))
--   "WorldHello"
--
newtype Dual a Dual :: a -> Dual a [getDual] :: Dual a -> a -- | Monoid under addition. -- -- 
--   >>> getSum (Sum 1 <> Sum 2 <> mempty)
--   3
--
newtype Sum a Sum :: a -> Sum a [getSum] :: Sum a -> a -- | Monoid under multiplication. -- -- 
--   >>> getProduct (Product 3 <> Product 4 <> mempty)
--   12
--
newtype Product a Product :: a -> Product a [getProduct] :: Product a -> a -- |

The control functor hierarchy

-- -- The functors in this module are called control functors, which are -- different from the data functors in Data.Functor.Linear. -- -- This distinction and the use-cases of each group of functors is -- explained in this blog post. module Control.Functor.Linear -- | Control linear functors. The functor of type f a holds only -- one value of type a and represents a computation producing an -- a with an effect. All control functors are data functors, but -- not all data functors are control functors. class Functor f => Functor f -- | Map a linear function g over a control functor f a. -- Note that g is used linearly over the single a in -- f a. fmap :: Functor f => (a %1 -> b) %1 -> f a %1 -> f b (<$>) :: Functor f => (a %1 -> b) %1 -> f a %1 -> f b infixl 4 <$> -- | 
--   (<&>) = flip fmap
--   
--
(<&>) :: Functor f => f a %1 -> (a %1 -> b) %1 -> f b infixl 1 <&> -- | Linearly typed replacement for the standard (<$) function. (<$) :: (Functor f, Consumable b) => a %1 -> f b %1 -> f a infixl 4 <$ -- | Discard a consumable value stored in a control functor. void :: (Functor f, Consumable a) => f a %1 -> f () -- | Apply the control fmap over a data functor. dataFmapDefault :: Functor f => (a %1 -> b) -> f a %1 -> f b -- | Control linear applicative functors. These represent effectful -- computations that could produce continuations that can be applied with -- <*>. class (Applicative f, Functor f) => Applicative f -- | Inject (and consume) a value into an applicative control functor. pure :: Applicative f => a %1 -> f a -- | Apply the linear function in a control applicative functor to the -- value of type a in another functor. This is essentialy -- composing two effectful computations, one that produces a function -- f :: a %1-> b and one that produces a value of type -- a into a single effectful computation that produces a value -- of type b. (<*>) :: Applicative f => f (a %1 -> b) %1 -> f a %1 -> f b -- | liftA2 g consumes g linearly as it lifts it over two -- functors: liftA2 g :: f a %1-> f b %1-> f c. liftA2 :: Applicative f => (a %1 -> b %1 -> c) %1 -> f a %1 -> f b %1 -> f c infixl 4 <*> -- | Apply the control pure over a data applicative. dataPureDefault :: Applicative f => a -> f a -- | Control linear monads. A linear monad is one in which you sequence -- linear functions in a context, i.e., you sequence functions of the -- form a %1-> m b. class Applicative m => Monad m -- | x >>= g applies a linear function g -- linearly (i.e., using it exactly once) on the value of type a -- inside the value of type m a (>>=) :: Monad m => m a %1 -> (a %1 -> m b) %1 -> m b (>>) :: Monad m => m () %1 -> m a %1 -> m a infixl 1 >> infixl 1 >>= return :: Monad m => a %1 -> m a -- | Given an effect-producing computation that produces an -- effect-producing computation that produces an a, simplify it -- to an effect-producing computation that produces an a. join :: Monad m => m (m a) %1 -> m a -- | Use this operator to define Applicative instances in terms of Monad -- instances. ap :: Monad m => m (a %1 -> b) %1 -> m a %1 -> m b -- | Fold from left to right with a linear monad. This is a linear version -- of foldM. foldM :: forall m a b. Monad m => (b %1 -> a %1 -> m b) -> b %1 -> [a] %1 -> m b -- | This class handles pattern-matching failure in do-notation. See -- Control.Monad.Fail for details. class Monad m => MonadFail m fail :: MonadFail m => String -> m a -- | This is a newtype for deriving Data.XXX classes from Control.XXX -- classes. newtype Data f a Data :: f a -> Data f a type Reader r = ReaderT r Identity reader :: Monad m => (r %1 -> a) %1 -> ReaderT r m a runReader :: Reader r a %1 -> r %1 -> a mapReader :: (a %1 -> b) %1 -> Reader r a %1 -> Reader r b withReader :: (r' %1 -> r) %1 -> Reader r a %1 -> Reader r' a -- | A linear reader monad transformer. This reader monad requires that use -- of the read-only state is explict. -- -- The monad instance requires that r be Dupable. This -- means that you should use the linear reader monad just like the -- non-linear monad, except that the type system ensures that you -- explicity use or discard the read-only state (with the -- Consumable instance). newtype ReaderT r m a ReaderT :: (r %1 -> m a) -> ReaderT r m a -- | Provide an intial read-only state and run the monadic computation in a -- reader monad transformer runReaderT :: ReaderT r m a %1 -> r %1 -> m a mapReaderT :: (m a %1 -> n b) %1 -> ReaderT r m a %1 -> ReaderT r n b withReaderT :: (r' %1 -> r) %1 -> ReaderT r m a %1 -> ReaderT r' m a ask :: Applicative m => ReaderT r m r local :: (r %1 -> r) %1 -> ReaderT r m a %1 -> ReaderT r m a asks :: Monad m => (r %1 -> a) %1 -> ReaderT r m a type State s = StateT s Identity state :: Applicative m => (s %1 -> (a, s)) %1 -> StateT s m a runState :: State s a %1 -> s %1 -> (a, s) -- | Use with care! This consumes the final state, so might be costly at -- runtime. evalState :: Consumable s => State s a %1 -> s %1 -> a execState :: State s () %1 -> s %1 -> s mapState :: ((a, s) %1 -> (b, s)) %1 -> State s a %1 -> State s b withState :: (s %1 -> s) %1 -> State s a %1 -> State s a -- | A (strict) linear state monad transformer. newtype StateT s m a StateT :: (s %1 -> m (a, s)) -> StateT s m a runStateT :: StateT s m a %1 -> s %1 -> m (a, s) -- | Use with care! This consumes the final state, so might be costly at -- runtime. evalStateT :: (Functor m, Consumable s) => StateT s m a %1 -> s %1 -> m a execStateT :: Functor m => StateT s m () %1 -> s %1 -> m s mapStateT :: (m (a, s) %1 -> n (b, s)) %1 -> StateT s m a %1 -> StateT s n b withStateT :: (s %1 -> s) %1 -> StateT s m a %1 -> StateT s m a get :: (Applicative m, Dupable s) => StateT s m s put :: (Applicative m, Consumable s) => s %1 -> StateT s m () modify :: Applicative m => (s %1 -> s) %1 -> StateT s m () gets :: (Applicative m, Dupable s) => (s %1 -> a) %1 -> StateT s m a class (forall m. Monad m => Monad (t m)) => MonadTrans t lift :: (MonadTrans t, Monad m) => m a %1 -> t m a -- | This is a newtype for deriving Data.XXX classes from Control.XXX -- classes. newtype Data f a Data :: f a -> Data f a -- | This module defines vectors of known length which can hold linear -- values. -- -- Having a known length matters with linear types, because many common -- vector operations (like zip) are not total with linear types. -- -- Make these vectors by giving any finite number of arguments to -- make and use them with elim: -- -- 
--   >>> :set -XLinearTypes
--   
--   >>> :set -XTypeApplications
--   
--   >>> :set -XTypeInType
--   
--   >>> :set -XTypeFamilies
--   
--   >>> import Prelude.Linear
--   
--   >>> import qualified Data.V.Linear as V
--   
--   >>> :{
--    doSomething :: Int %1-> Int %1-> Bool
--    doSomething x y = x + y > 0
--   :}
--
-- -- 
--   >>> :{
--    isTrue :: Bool
--    isTrue = V.elim doSomething (build 4 9)
--      where
--        build :: Int %1-> Int %1-> V.V 2 Int
--        build = V.make
--   :}
--
-- -- A much more expensive library of vectors of known size (including -- matrices and tensors of all dimensions) is the linear -- library on Hackage (that's linear in the sense of linear -- algebra, rather than linear types). module Data.V.Linear -- | V n a represents an immutable sequence of n -- elements of type a (like a n-tuple), with a linear -- Applicative instance. data V (n :: Nat) (a :: Type) -- | Returns an empty V. empty :: forall a. V 0 a consume :: V 0 a %1 -> () map :: (a %1 -> b) -> V n a %1 -> V n b pure :: forall n a. KnownNat n => a -> V n a (<*>) :: V n (a %1 -> b) %1 -> V n a %1 -> V n b infixl 4 <*> -- | Splits the head and tail of the V, returning an unboxed tuple. uncons# :: 1 <= n => V n a %1 -> (# a, V (n - 1) a #) -- | Splits the head and tail of the V, returning a boxed tuple. uncons :: 1 <= n => V n a %1 -> (a, V (n - 1) a) -- | Elim n a b is used to implement elim without -- recursion so that we can guarantee that elim will be inlined -- and unrolled. -- -- Elim is solely used in the signature of elim. class Elim n a b -- | Takes a function of type a %1 -> a %1 -> ... %1 -> a %1 -- -> b, and returns a b . The V n a is -- used to supply all the items of type a required by the -- function. -- -- For instance: -- -- 
--   elim @1 :: (a %1 -> b) %1 -> V 1 a %1 -> b
--   elim @2 :: (a %1 -> a %1 -> b) %1 -> V 2 a %1 -> b
--   elim @3 :: (a %1 -> a %1 -> a %1 -> b) %1 -> V 3 a %1 -> b
--
-- -- It is not always necessary to give the arity argument. It can be -- inferred from the function argument. -- -- About the constraints of this function (they won't get in your way): -- -- elim :: forall (n :: Nat) a b f. (n ~ PeanoToNat (NatToPeano n), Elim (NatToPeano n) a b, IsFunN a b f, f ~ FunN (NatToPeano n) a b, n ~ Arity b f) => f %1 -> V n a %1 -> b -- | Prepends the given element to the V. cons :: forall n a. a %1 -> V (n - 1) a %1 -> V n a -- | Creates a V of the specified size by consuming a -- Replicator. fromReplicator :: forall n a. KnownNat n => Replicator a %1 -> V n a -- | Produces a V n a from a Dupable value -- a. dupV :: forall n a. (KnownNat n, Dupable a) => a %1 -> V n a -- | Returns the type-level Nat of the context as a term-level -- integer. theLength :: forall n. KnownNat n => Int -- | Make m n a is used to avoid recursion in the -- implementation of make so that make can be inlined. -- -- Make is solely used in the signature of that function. class Make m n a -- | Builds a n-ary constructor for V n a (i.e. a function -- taking n linear arguments of type a and returning a -- V n a). -- -- 
--   myV :: V 3 Int
--   myV = make 1 2 3
--
-- -- About the constraints of this function (they won't get in your way): -- -- make :: forall (n :: Nat) a f. (n ~ PeanoToNat (NatToPeano n), Make (NatToPeano n) (NatToPeano n) a, IsFunN a (V n a) f, f ~ FunN (NatToPeano n) a (V n a), n ~ ArityV f) => f -- | The ArityV type family exists to help the type checker compute -- the arity n ~ Arity b f when b ~ V n -- a. type family ArityV f -- |

The data functor hierarchy

-- -- This module defines the data functor library. Unlike in the case of -- non-linear, unrestricted, functors, there is a split between data -- functors, which represent containers, and control functors which -- represent effects. Please read this blog post. For more -- details, see Control.Functor.Linear. -- -- -- -- This module also defines genericTraverse for types implementing -- Generic1. module Data.Functor.Linear -- | Linear Data Functors should be thought of as containers holding values -- of type a over which you are able to apply a linear function -- of type a %1-> b on each value of type a -- in the functor and consume a given functor of type f a. class Functor f fmap :: Functor f => (a %1 -> b) -> f a %1 -> f b (<$>) :: Functor f => (a %1 -> b) -> f a %1 -> f b infixl 4 <$> -- | Replace all occurances of b with the given a and -- consume the functor f b. (<$) :: (Functor f, Consumable b) => a -> f b %1 -> f a infixl 4 <$ -- | Discard a consumable value stored in a data functor. void :: (Functor f, Consumable a) => f a %1 -> f () -- | Data Applicative-s can be seen as containers which can be -- zipped together. A prime example of data Applicative are -- vectors of known length (ZipLists would be, if it were not -- for the fact that zipping them together drops values, which we are not -- allowed to do in a linear container). -- -- In fact, an applicative functor is precisely a functor equipped with -- (pure and) liftA2 :: (a %1-> b %1-> c) -> f a %1-> f b -- %1-> f c. In the case where f = [], the signature of -- liftA2 would specialise to that of zipWith. -- -- Intuitively, the type of liftA2 means that Applicatives -- can be seen as containers whose "number" of elements is known at -- compile-time. This includes vectors of known length but excludes -- Maybe, since this may contain either zero or one value. -- Similarly, ((->) r) forms a Data Applicative, since -- this is a (possibly infinitary) container indexed by r, while -- lists do not, since they may contain any number of elements. -- --

Remarks for the mathematically inclined

-- -- An Applicative is, as in the restricted case, a lax monoidal -- endofunctor of the category of linear types. That is, it is equipped -- with -- -- -- -- It is a simple exercise to verify that these are equivalent to the -- definition of Applicative. Hence that the choice of linearity -- of the various arrow is indeed natural. class Functor f => Applicative f pure :: Applicative f => a -> f a (<*>) :: Applicative f => f (a %1 -> b) %1 -> f a %1 -> f b liftA2 :: Applicative f => (a %1 -> b %1 -> c) -> f a %1 -> f b %1 -> f c infixl 4 <*> -- | The Const functor. newtype Const a (b :: k) Const :: a -> Const a (b :: k) [getConst] :: Const a (b :: k) -> a -- | A linear data traversible is a functor of type t a where you -- can apply a linear effectful action of type a %1-> f b on -- each value of type a and compose this to perform an action on -- the whole functor, resulting in a value of type f (t b). -- -- To learn more about Traversable, see here: -- -- class Functor t => Traversable t traverse :: (Traversable t, Applicative f) => (a %1 -> f b) -> t a %1 -> f (t b) sequence :: (Traversable t, Applicative f) => t (f a) %1 -> f (t a) -- | Implementation of traverse for types which derive (linear) -- Generic1. -- -- ### Performance note -- -- At present, this function does not perform well for recursive types -- like lists; it will not specialize to either -- -- ### Example -- -- 
--   data T
--   $(deriveGeneric1 ''T)
--   
--   instance Traversable T where
--     traverse = genericTraverse
--
-- -- Note that, contrary to many other classes in linear-base, we can't -- define `Traversable T` using deriving via, because the role of -- t, in the type of traverse, is nominal. genericTraverse :: (Generic1 t, GTraversable (Rep1 t), Applicative f) => (a %1 -> f b) -> t a %1 -> f (t b) -- | This type class derives the definition of genericTraverse by -- induction on the generic representation of a type. class GTraversable t mapM :: (Traversable t, Monad m) => (a %1 -> m b) -> t a %1 -> m (t b) sequenceA :: (Traversable t, Applicative f) => t (f a) %1 -> f (t a) for :: (Traversable t, Applicative f) => t a %1 -> (a %1 -> f b) -> f (t b) forM :: (Traversable t, Monad m) => t a %1 -> (a %1 -> m b) -> m (t b) mapAccumL :: Traversable t => (a %1 -> b %1 -> (a, c)) -> a %1 -> t b %1 -> (a, t c) mapAccumR :: Traversable t => (a %1 -> b %1 -> (a, c)) -> a %1 -> t b %1 -> (a, t c) -- | This module provides essential tools for doing non-linear things in -- linear code. -- --

Critical Definition: Restricted

-- -- In a linear function f :: a %1-> b, the argument -- a must be used in a linear way. Its use is restricted -- while an argument in a non-linear function is unrestricted. -- -- Hence, a linear function with an argument of Ur a -- (Ur is short for unrestricted) can use the a -- in an unrestricted way. That is, we have the following equivalence: -- -- 
--   (Ur a %1-> b) ≌ (a -> b)
--
-- --

Consumable, Dupable, Moveable classes

-- -- Use these classes to perform some non-linear action on linearly bound -- values. -- -- If a type is Consumable, you can consume it in a linear -- function that doesn't need that value to produce it's result: -- -- 
--   fst :: Consumable b => (a,b) %1-> a
--   fst (a,b) = withConsume (consume b) a
--     where
--       withConsume :: () %1-> a %1-> a
--       withConsume () x = x
--
-- -- If a type is Dupable, you can duplicate it as much as -- you like. -- -- 
--   -- checkIndex ix size_of_array
--   checkIndex :: Int %1-> Int %1-> Bool
--   checkIndex ix size = withDuplicate (dup2 ix) size
--     where
--       withDuplicate :: (Int, Int) %1-> Int %1-> Bool
--       withDuplicate (ix,ix') size = (0 <= ix) && (ix < size)
--       (<) :: Int %1-> Int %1-> Bool
--       (<) = ...
--   
--       (<=) :: Int %1-> Int %1-> Bool
--       (<=) = ...
--   
--       (&&) :: Bool %1-> Bool %1-> Bool
--       (&&) = ...
--
-- -- If a type is Moveable, you can move it inside -- Ur and use it in any non-linear way you would like. -- -- 
--   diverge :: Int %1-> Bool
--   diverge ix = fromMove (move ix)
--     where
--       fromMove :: Ur Int %1-> Bool
--       fromMove (Ur 0) = True
--       fromMove (Ur 1) = True
--       fromMove (Ur x) = False
--
module Data.Unrestricted.Linear -- | Ur a represents unrestricted values of type a in a -- linear context. The key idea is that because the contructor holds -- a with a regular arrow, a function that uses Ur a -- linearly can use a however it likes. -- -- 
--   someLinear :: Ur a %1-> (a,a)
--   someLinear (Ur a) = (a,a)
--
data Ur a [Ur] :: a -> Ur a -- | Get an a out of an Ur a. If you call this function -- on a linearly bound Ur a, then the a you get out has -- to be used linearly, for example: -- -- 
--   restricted :: Ur a %1-> b
--   restricted x = f (unur x)
--     where
--       -- f __must__ be linear
--       f :: a %1-> b
--       f x = ...
--
unur :: Ur a %1 -> a -- | Lifts a function on a linear Ur a. lift :: (a -> b) -> Ur a %1 -> Ur b -- | Lifts a function to work on two linear Ur a. lift2 :: (a -> b -> c) -> Ur a %1 -> Ur b %1 -> Ur c -- | UrT transforms linear control monads to non-linear monads. -- -- newtype UrT m a UrT :: m (Ur a) -> UrT m a -- | Linearly unwrap the UrT newtype wrapper. runUrT :: UrT m a %1 -> m (Ur a) -- | Lift a computation to the UrT monad, provided that the type -- a can be used unrestricted. liftUrT :: (Movable a, Functor m) => m a %1 -> UrT m a -- | Extract the inner computation linearly, the inverse of liftUrT. -- -- 
--   evalUrT (liftUrT m) = m
--
evalUrT :: Functor m => UrT m a %1 -> m a class Consumable a consume :: Consumable a => a %1 -> () -- | The laws of Dupable are dual to those of Monoid: -- -- -- -- where the (≃) sign represents equality up to type -- isomorphism. -- -- -- -- (Laws 1-2 and 5-6 are equivalent) -- -- Implementation of Dupable for Movable types should be -- done with deriving via AsMovable. -- -- Implementation of Dupable for other types can be done with -- deriving via Generically. Note that at present this -- mechanism can have performance problems for recursive parameterized -- types. Specifically, the methods will not specialize to underlying -- Dupable instances. See this GHC issue. class Consumable a => Dupable a -- | Creates a Replicator for the given a. -- -- You usually want to define this method using Replicator's -- Applicative instance. For instance, here is an implementation -- of Dupable [a]: -- -- 
--   instance Dupable a => Dupable [a] where
--     dupR [] = pure []
--     dupR (a : as) = (:) <$> dupR a <*> dupR as
--
dupR :: Dupable a => a %1 -> Replicator a -- | Creates two as from a Dupable a, in a linear -- fashion. dup2 :: Dupable a => a %1 -> (a, a) -- | Use Movable a to represent a type which can be used -- many times even when given linearly. Simple data types such as -- Bool or [] are Movable. Though, bear in mind -- that this typically induces a deep copy of the value. -- -- Formally, Movable a is the class of coalgebras -- of the Ur comonad. That is -- -- -- -- Additionally, a Movable instance must be compatible with its -- Dupable parent instance. That is: -- -- class Dupable a => Movable a move :: Movable a => a %1 -> Ur a -- | Consume the first argument and return the second argument. This is -- like seq but the first argument is restricted to be -- Consumable. lseq :: Consumable a => a %1 -> b %1 -> b infixr 0 `lseq` -- | Creates two as from a Dupable a. Same -- function as dup2. dup :: Dupable a => a %1 -> (a, a) -- | Creates 3 as from a Dupable a, in a linear -- fashion. dup3 :: Dupable a => a %1 -> (a, a, a) -- | Creates 4 as from a Dupable a, in a linear -- fashion. dup4 :: Dupable a => a %1 -> (a, a, a, a) -- | Creates 5 as from a Dupable a, in a linear -- fashion. dup5 :: Dupable a => a %1 -> (a, a, a, a, a) -- | Creates 6 as from a Dupable a, in a linear -- fashion. dup6 :: Dupable a => a %1 -> (a, a, a, a, a, a) -- | Creates 7 as from a Dupable a, in a linear -- fashion. dup7 :: Dupable a => a %1 -> (a, a, a, a, a, a, a) -- | Newtype that must be used with DerivingVia to get efficient -- Dupable and Consumable implementations for -- Movable types. newtype AsMovable a AsMovable :: a -> AsMovable a newtype MovableMonoid a MovableMonoid :: a -> MovableMonoid a module Data.Ord.Linear -- | Linear Orderings -- -- Linear orderings provide a strict order. The laws for (<=) -- for all <math>: -- -- -- -- and these "agree" with <: -- -- -- -- Unlike in the non-linear setting, a linear compare doesn't -- follow from <= since it requires calls: one to -- <= and one to ==. However, from a linear -- compare it is easy to implement the others. Hence, the -- minimal complete definition only contains compare. class Eq a => Ord a -- | compare x y returns an Ordering which is one of -- GT (greater than), EQ (equal), or LT (less -- than) which should be understood as "x is (compare x y) y". compare :: Ord a => a %1 -> a %1 -> Ordering (<=) :: Ord a => a %1 -> a %1 -> Bool (<) :: Ord a => a %1 -> a %1 -> Bool (>) :: Ord a => a %1 -> a %1 -> Bool (>=) :: Ord a => a %1 -> a %1 -> Bool infix 4 >= infix 4 `compare` infix 4 > infix 4 <= infix 4 < data Ordering LT :: Ordering EQ :: Ordering GT :: Ordering -- | min x y returns the smaller input, or y in case of a -- tie. min :: (Dupable a, Ord a) => a %1 -> a %1 -> a -- | max x y returns the larger input, or y in case of a -- tie. max :: (Dupable a, Ord a) => a %1 -> a %1 -> a -- | Testing equality on values. -- -- The laws are that (==) and (/=) are compatible and (==) is an -- equivalence relation. So, for all x, y, z, -- -- class Eq a (==) :: Eq a => a %1 -> a %1 -> Bool (/=) :: Eq a => a %1 -> a %1 -> Bool infix 4 == infix 4 /= -- | This module contains useful functions for working with Eithers. module Data.Either.Linear -- | The Either type represents values with two possibilities: a -- value of type Either a b is either Left -- a or Right b. -- -- The Either type is sometimes used to represent a value which is -- either correct or an error; by convention, the Left constructor -- is used to hold an error value and the Right constructor is -- used to hold a correct value (mnemonic: "right" also means "correct"). -- --

Examples

-- -- The type Either String Int is the type -- of values which can be either a String or an Int. The -- Left constructor can be used only on Strings, and the -- Right constructor can be used only on Ints: -- -- 
--   >>> let s = Left "foo" :: Either String Int
--   
--   >>> s
--   Left "foo"
--   
--   >>> let n = Right 3 :: Either String Int
--   
--   >>> n
--   Right 3
--   
--   >>> :type s
--   s :: Either String Int
--   
--   >>> :type n
--   n :: Either String Int
--
-- -- The fmap from our Functor instance will ignore -- Left values, but will apply the supplied function to values -- contained in a Right: -- -- 
--   >>> let s = Left "foo" :: Either String Int
--   
--   >>> let n = Right 3 :: Either String Int
--   
--   >>> fmap (*2) s
--   Left "foo"
--   
--   >>> fmap (*2) n
--   Right 6
--
-- -- The Monad instance for Either allows us to chain -- together multiple actions which may fail, and fail overall if any of -- the individual steps failed. First we'll write a function that can -- either parse an Int from a Char, or fail. -- -- 
--   >>> import Data.Char ( digitToInt, isDigit )
--   
--   >>> :{
--       let parseEither :: Char -> Either String Int
--           parseEither c
--             | isDigit c = Right (digitToInt c)
--             | otherwise = Left "parse error"
--   
--   >>> :}
--
-- -- The following should work, since both '1' and '2' -- can be parsed as Ints. -- -- 
--   >>> :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x <- parseEither '1'
--             y <- parseEither '2'
--             return (x + y)
--   
--   >>> :}
--
-- -- 
--   >>> parseMultiple
--   Right 3
--
-- -- But the following should fail overall, since the first operation where -- we attempt to parse 'm' as an Int will fail: -- -- 
--   >>> :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x <- parseEither 'm'
--             y <- parseEither '2'
--             return (x + y)
--   
--   >>> :}
--
-- -- 
--   >>> parseMultiple
--   Left "parse error"
--
data Either a b Left :: a -> Either a b Right :: b -> Either a b -- | Linearly consume an Either by applying the first linear -- function on a value constructed with Left and the second -- linear function on a value constructed with Right. either :: (a %1 -> c) -> (b %1 -> c) -> Either a b %1 -> c -- | Get all the left elements in order, and consume the right ones. lefts :: Consumable b => [Either a b] %1 -> [a] -- | Get all the right elements in order, and consume the left ones. rights :: Consumable a => [Either a b] %1 -> [b] -- | Get the left element of a consumable Either with a default fromLeft :: (Consumable a, Consumable b) => a %1 -> Either a b %1 -> a -- | Get the right element of a consumable Either with a default fromRight :: (Consumable a, Consumable b) => b %1 -> Either a b %1 -> b -- | Partition and consume a list of Eithers into two lists with -- all the lefts in one and the rights in the second, in the order they -- appeared in the initial list. partitionEithers :: [Either a b] %1 -> ([a], [b]) -- | This module defines a stream-like type named Replicator, which -- is mainly used in the definition of the Dupable class to -- provide efficient linear duplication. The API of Replicator is -- close to the one of an infinite stream: it can either produce a new -- value linearly (with next or next#), or be linearly -- discarded (with consume or extract). -- -- A crucial aspect, from a performance standpoint, is that the -- pure function (which takes an unrestricted argument) is -- implemented efficiently: the Replicator returns the same -- value on each call to next. That is, the pointer is always -- shared. This will allow Movable types to be given an efficient -- instance of Dupable. Instances of both Movable and -- Dupable typically involve deep copies. The implementation of -- pure lets us make sure that, for Movable types, only -- one deep copy is performed, rather than one per additional replica. -- -- Strictly speaking, the implementation of (<*>) plays a -- role in all this as well: For two pure Replicators -- fs and as, fs <*> as is a pure -- Replicator. Together, pure and (<*>) form -- the Applicative instance of Replicator. module Data.Replicator.Linear -- | Replicator is a stream-like data structure used to linearly -- duplicate values. data Replicator a consume :: Replicator a %1 -> () duplicate :: Replicator a %1 -> Replicator (Replicator a) map :: (a %1 -> b) -> Replicator a %1 -> Replicator b pure :: a -> Replicator a (<*>) :: Replicator (a %1 -> b) %1 -> Replicator a %1 -> Replicator b infixl 4 <*> -- | Extracts the next item from the "infinite stream" -- Replicator a. next :: Replicator a %1 -> (a, Replicator a) -- | Extracts the next item from the "infinite stream" -- Replicator a. Same function as next, but -- returning an unboxed tuple. next# :: Replicator a %1 -> (# a, Replicator a #) -- | take n as is a list of size n, containing -- n replicas from as. take :: Int -> Replicator a %1 -> [a] -- | Returns the next item from Replicator a and -- efficiently consumes the replicator at the same time. extract :: Replicator a %1 -> a -- | Comonadic extend function. -- -- 
--   extend f = map f . duplicate
--
extend :: (Replicator a %1 -> b) -> Replicator a %1 -> Replicator b -- | Elim n a b is used to implement elim without -- recursion so that we can guarantee that elim will be inlined -- and unrolled. -- -- Elim is solely used in the signature of elim. class Elim n a b -- | Takes a function of type a %1 -> a %1 -> ... %1 -> a %1 -- -> b, and returns a b . The replicator is used to -- supply all the items of type a required by the function. -- -- For instance: -- -- 
--   elim @1 :: (a %1 -> b) %1 -> Replicator a %1 -> b
--   elim @2 :: (a %1 -> a %1 -> b) %1 -> Replicator a %1 -> b
--   elim @3 :: (a %1 -> a %1 -> a %1 -> b) %1 -> Replicator a %1 -> b
--
-- -- It is not always necessary to give the arity argument. It can be -- inferred from the function argument. -- -- 
--   elim (,) :: Replicator a %1 -> (a, a)
--   elim (,,) :: Replicator a %1 -> (a, a, a)
--
-- -- About the constraints of this function (they won't get in your way): -- -- elim :: forall (n :: Nat) a b f. (Elim (NatToPeano n) a b, IsFunN a b f, f ~ FunN (NatToPeano n) a b, n ~ Arity b f) => f %1 -> Replicator a %1 -> b -- | This module provides linear functions on the standard Maybe -- type. module Data.Maybe.Linear -- | The Maybe type encapsulates an optional value. A value of type -- Maybe a either contains a value of type a -- (represented as Just a), or it is empty (represented -- as Nothing). Using Maybe is a good way to deal with -- errors or exceptional cases without resorting to drastic measures such -- as error. -- -- The Maybe type is also a monad. It is a simple kind of error -- monad, where all errors are represented by Nothing. A richer -- error monad can be built using the Either type. data Maybe a Nothing :: Maybe a Just :: a -> Maybe a -- | maybe b f m returns (f a) where a is in -- m if it exists and b otherwise maybe :: b -> (a %1 -> b) -> Maybe a %1 -> b -- | fromMaybe default m is the a in m if it -- exists and the default otherwise fromMaybe :: a -> Maybe a %1 -> a -- | maybeToList m creates a singleton or an empty list based on -- the Maybe a. maybeToList :: Maybe a %1 -> [a] -- | catMaybes xs discards the Nothings in xs -- and extracts the as catMaybes :: [Maybe a] %1 -> [a] -- | 
--   mapMaybe f xs = catMaybes (map f xs)
--
mapMaybe :: (a %1 -> Maybe b) -> [a] %1 -> [b] -- | This module provides a linear Num class with instances. Import -- this module to use linear versions of (+), (-), etc, -- on numeric types like Int and Double. -- --

The Typeclass Hierarchy

-- -- The Num class is broken up into several instances. Here is the -- basic hierarchy: -- -- module Data.Num.Linear class (Ring a, FromInteger a) => Num a abs :: Num a => a %1 -> a signum :: Num a => a %1 -> a -- | A type that can be added linearly. The operation (+) is -- associative and commutative, i.e., for all a, b, -- c -- -- 
--   (a + b) + c = a + (b + c)
--   a + b = b + c
--
class Additive a (+) :: Additive a => a %1 -> a %1 -> a infixl 6 + -- | An Additive type with an identity on (+). class Additive a => AddIdentity a zero :: AddIdentity a => a -- | An AddIdentity with inverses that satisfies the laws of an -- abelian group class AddIdentity a => AdditiveGroup a negate :: AdditiveGroup a => a %1 -> a (-) :: AdditiveGroup a => a %1 -> a %1 -> a infixl 6 - -- | A numeric type with an associative (*) operation class Multiplicative a (*) :: Multiplicative a => a %1 -> a %1 -> a infixl 7 * -- | A Multiplicative type with an identity for (*) class Multiplicative a => MultIdentity a one :: MultIdentity a => a -- | A semiring class. This is basically a numeric type with -- mutliplication, addition and with identities for each. The laws: -- -- 
--   zero * x = zero
--   a * (b + c) = (a * b) + (a * c)
--
class (AddIdentity a, MultIdentity a) => Semiring a -- | A Ring instance is a numeric type with (+), -- (-), (*) and all the following properties: a group -- with (+) and a MultIdentity with (*) along -- with distributive laws. class (AdditiveGroup a, Semiring a) => Ring a -- | A numeric type that Integers can be embedded into while -- satisfying all the typeclass laws Integers obey. That is, if -- there's some property like commutivity of integers x + y == y + -- x, then we must have: -- -- 
--   fromInteger x + fromInteger y == fromInteger y + fromInteger x
--
-- -- For mathy folk: fromInteger should be a homomorphism over -- (+) and (*). class FromInteger a fromInteger :: FromInteger a => Integer %1 -> a -- | A newtype wrapper to give the underlying monoid for an additive -- structure. -- -- Deprecated because Sum (reexported as Sum) now has a -- linear Semigroup and Monoid instance. -- | Deprecated: Use Sum (reexported as Sum) instead newtype Adding a -- | Deprecated: Use Sum (reexported as Sum) instead Adding :: a -> Adding a -- | Deprecated: Use Sum (reexported as Sum) and -- pattern-match to extract the inner value linearly getAdded :: Adding a %1 -> a -- | A newtype wrapper to give the underlying monoid for a multiplicative -- structure. -- -- Deprecated because Product (reexported as Product) now -- has a linear Semigroup and Monoid instance. -- | Deprecated: Use Product (reexported as Product) -- instead newtype Multiplying a -- | Deprecated: Use Product (reexported as Product) -- instead Multiplying :: a -> Multiplying a -- | Deprecated: Use Product (reexported as Product) and -- pattern-match to extract the inner value linearly getMultiplied :: Multiplying a %1 -> a instance GHC.Num.Num a => GHC.Num.Num (Data.Num.Linear.MovableNum a) instance Data.Unrestricted.Linear.Internal.Movable.Movable a => Data.Unrestricted.Linear.Internal.Movable.Movable (Data.Num.Linear.MovableNum a) instance Data.Unrestricted.Linear.Internal.Dupable.Dupable a => Data.Unrestricted.Linear.Internal.Dupable.Dupable (Data.Num.Linear.MovableNum a) instance Data.Unrestricted.Linear.Internal.Consumable.Consumable a => Data.Unrestricted.Linear.Internal.Consumable.Consumable (Data.Num.Linear.MovableNum a) instance Data.Num.Linear.AddIdentity a => GHC.Base.Monoid (Data.Num.Linear.Adding a) instance Data.Num.Linear.Additive a => GHC.Base.Semigroup (Data.Num.Linear.Adding a) instance GHC.Show.Show a => GHC.Show.Show (Data.Num.Linear.Adding a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Num.Linear.Adding a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Num.Linear.Adding a) instance Data.Num.Linear.MultIdentity a => GHC.Base.Monoid (Data.Num.Linear.Multiplying a) instance Data.Num.Linear.Multiplicative a => GHC.Base.Semigroup (Data.Num.Linear.Multiplying a) instance GHC.Show.Show a => GHC.Show.Show (Data.Num.Linear.Multiplying a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Num.Linear.Multiplying a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Num.Linear.Multiplying a) instance Data.Num.Linear.Additive GHC.Types.Int instance Data.Num.Linear.Additive GHC.Types.Double instance Data.Num.Linear.AddIdentity GHC.Types.Int instance Data.Num.Linear.AddIdentity GHC.Types.Double instance Data.Num.Linear.AdditiveGroup GHC.Types.Int instance Data.Num.Linear.AdditiveGroup GHC.Types.Double instance Data.Num.Linear.Multiplicative GHC.Types.Int instance Data.Num.Linear.Multiplicative GHC.Types.Double instance Data.Num.Linear.MultIdentity GHC.Types.Int instance Data.Num.Linear.MultIdentity GHC.Types.Double instance Data.Num.Linear.Semiring GHC.Types.Int instance Data.Num.Linear.Semiring GHC.Types.Double instance Data.Num.Linear.Ring GHC.Types.Int instance Data.Num.Linear.Ring GHC.Types.Double instance Data.Num.Linear.FromInteger GHC.Types.Int instance Data.Num.Linear.FromInteger GHC.Types.Double instance Data.Num.Linear.Num GHC.Types.Int instance Data.Num.Linear.Num GHC.Types.Double instance Data.Num.Linear.Multiplicative a => Data.Monoid.Linear.Internal.Semigroup.Semigroup (Data.Num.Linear.Multiplying a) instance Data.Num.Linear.MultIdentity a => Data.Monoid.Linear.Internal.Monoid.Monoid (Data.Num.Linear.Multiplying a) instance Data.Num.Linear.Additive a => Data.Monoid.Linear.Internal.Semigroup.Semigroup (Data.Num.Linear.Adding a) instance Data.Num.Linear.AddIdentity a => Data.Monoid.Linear.Internal.Monoid.Monoid (Data.Num.Linear.Adding a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.Additive (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.AddIdentity (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.AdditiveGroup (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.Multiplicative (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.MultIdentity (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.Semiring (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.Ring (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.FromInteger (Data.Num.Linear.MovableNum a) instance (Data.Unrestricted.Linear.Internal.Movable.Movable a, GHC.Num.Num a) => Data.Num.Linear.Num (Data.Num.Linear.MovableNum a) instance Data.Num.Linear.MultIdentity a => Data.Monoid.Linear.Internal.Monoid.Monoid (Data.Semigroup.Internal.Product a) instance Data.Num.Linear.Multiplicative a => Data.Monoid.Linear.Internal.Semigroup.Semigroup (Data.Semigroup.Internal.Product a) instance Data.Num.Linear.AddIdentity a => Data.Monoid.Linear.Internal.Monoid.Monoid (Data.Semigroup.Internal.Sum a) instance Data.Num.Linear.Additive a => Data.Monoid.Linear.Internal.Semigroup.Semigroup (Data.Semigroup.Internal.Sum a) -- | Linear versions of List functions. -- -- This module only contains minimal amount of documentation; consult the -- original Data.List module for more detailed information. module Data.List.Linear (++) :: [a] %1 -> [a] %1 -> [a] infixr 5 ++ map :: (a %1 -> b) -> [a] %1 -> [b] -- | filter p xs returns a list with elements satisfying the -- predicate. -- -- See mapMaybe if you do not want the Dupable constraint. filter :: Dupable a => (a %1 -> Bool) -> [a] %1 -> [a] -- | <math>. Extract the first element of a list, which must be -- non-empty. -- -- 
--   >>> head [1, 2, 3]
--   1
--   
--   >>> head [1..]
--   1
--   
--   >>> head []
--   *** Exception: Prelude.head: empty list
--
head :: [a] -> a uncons :: [a] %1 -> Maybe (a, [a]) -- | <math>. Extract the elements after the head of a list, which -- must be non-empty. -- -- 
--   >>> tail [1, 2, 3]
--   [2,3]
--   
--   >>> tail [1]
--   []
--   
--   >>> tail []
--   *** Exception: Prelude.tail: empty list
--
tail :: [a] -> [a] -- | <math>. Extract the last element of a list, which must be finite -- and non-empty. -- -- 
--   >>> last [1, 2, 3]
--   3
--   
--   >>> last [1..]
--   * Hangs forever *
--   
--   >>> last []
--   *** Exception: Prelude.last: empty list
--
last :: [a] -> a -- | <math>. Return all the elements of a list except the last one. -- The list must be non-empty. -- -- 
--   >>> init [1, 2, 3]
--   [1,2]
--   
--   >>> init [1]
--   []
--   
--   >>> init []
--   *** Exception: Prelude.init: empty list
--
init :: [a] -> [a] reverse :: [a] %1 -> [a] -- | <math>. lookup key assocs looks up a key in an -- association list. -- -- 
--   >>> lookup 2 []
--   Nothing
--   
--   >>> lookup 2 [(1, "first")]
--   Nothing
--   
--   >>> lookup 2 [(1, "first"), (2, "second"), (3, "third")]
--   Just "second"
--
lookup :: Eq a => a -> [(a, b)] -> Maybe b -- | Return the length of the given list alongside with the list itself. length :: [a] %1 -> (Ur Int, [a]) -- | Test whether the structure is empty. The default implementation is -- Left-associative and lazy in both the initial element and the -- accumulator. Thus optimised for structures where the first element can -- be accessed in constant time. Structures where this is not the case -- should have a non-default implementation. -- --

Examples

-- -- Basic usage: -- -- 
--   >>> null []
--   True
--
-- -- 
--   >>> null [1]
--   False
--
-- -- null is expected to terminate even for infinite structures. The -- default implementation terminates provided the structure is bounded on -- the left (there is a leftmost element). -- -- 
--   >>> null [1..]
--   False
--
null :: Foldable t => t a -> Bool traverse' :: Applicative f => (a %1 -> f b) -> [a] %1 -> f [b] -- | NOTE: This does not short-circuit and always traverses the -- entire list to consume the rest of the elements. take :: Consumable a => Int -> [a] %1 -> [a] drop :: Consumable a => Int -> [a] %1 -> [a] splitAt :: Int -> [a] %1 -> ([a], [a]) -- | span, applied to a predicate p and a list xs, -- returns a tuple where first element is longest prefix (possibly empty) -- of xs of elements that satisfy p and second element -- is the remainder of the list. span :: Dupable a => (a %1 -> Bool) -> [a] %1 -> ([a], [a]) partition :: Dupable a => (a %1 -> Bool) -> [a] %1 -> ([a], [a]) -- | NOTE: This does not short-circuit and always traverses the -- entire list to consume the rest of the elements. takeWhile :: Dupable a => (a %1 -> Bool) -> [a] %1 -> [a] dropWhile :: Dupable a => (a %1 -> Bool) -> [a] %1 -> [a] -- | The find function takes a predicate and a structure and returns -- the leftmost element of the structure matching the predicate, or -- Nothing if there is no such element. -- --

Examples

-- -- Basic usage: -- -- 
--   >>> find (> 42) [0, 5..]
--   Just 45
--
-- -- 
--   >>> find (> 12) [1..7]
--   Nothing
--
find :: Foldable t => (a -> Bool) -> t a -> Maybe a -- | The intersperse function takes an element and a list and -- intersperses that element between the elements of the list. intersperse :: a -> [a] %1 -> [a] -- | intercalate xs xss is equivalent to (concat (intersperse -- xs xss)). It inserts the list xs in between the lists in xss and -- concatenates the result. intercalate :: [a] -> [[a]] %1 -> [a] -- | The transpose function transposes the rows and columns of its -- argument. transpose :: [[a]] %1 -> [[a]] foldl :: (b %1 -> a %1 -> b) -> b %1 -> [a] %1 -> b foldl' :: (b %1 -> a %1 -> b) -> b %1 -> [a] %1 -> b foldl1 :: HasCallStack => (a %1 -> a %1 -> a) -> [a] %1 -> a foldl1' :: HasCallStack => (a %1 -> a %1 -> a) -> [a] %1 -> a foldr :: (a %1 -> b %1 -> b) -> b %1 -> [a] %1 -> b foldr1 :: HasCallStack => (a %1 -> a %1 -> a) -> [a] %1 -> a -- | Map each element of the structure to a monoid, and combine the -- results. foldMap :: Monoid m => (a %1 -> m) -> [a] %1 -> m -- | A variant of foldMap that is strict in the accumulator. foldMap' :: Monoid m => (a %1 -> m) -> [a] %1 -> m concat :: [[a]] %1 -> [a] concatMap :: (a %1 -> [b]) -> [a] %1 -> [b] -- | NOTE: This does not short-circuit, and always consumes the -- entire container. and :: [Bool] %1 -> Bool -- | NOTE: This does not short-circuit, and always consumes the -- entire container. or :: [Bool] %1 -> Bool -- | NOTE: This does not short-circuit, and always consumes the -- entire container. any :: (a %1 -> Bool) -> [a] %1 -> Bool -- | NOTE: This does not short-circuit, and always consumes the -- entire container. all :: (a %1 -> Bool) -> [a] %1 -> Bool sum :: AddIdentity a => [a] %1 -> a product :: MultIdentity a => [a] %1 -> a scanl :: Dupable b => (b %1 -> a %1 -> b) -> b %1 -> [a] %1 -> [b] scanl1 :: Dupable a => (a %1 -> a %1 -> a) -> [a] %1 -> [a] scanr :: Dupable b => (a %1 -> b %1 -> b) -> b %1 -> [a] %1 -> [b] scanr1 :: Dupable a => (a %1 -> a %1 -> a) -> [a] %1 -> [a] repeat :: Dupable a => a %1 -> [a] replicate :: Dupable a => Int -> a %1 -> [a] cycle :: (HasCallStack, Dupable a) => [a] %1 -> [a] iterate :: Dupable a => (a %1 -> a) -> a %1 -> [a] unfoldr :: (b %1 -> Maybe (a, b)) -> b %1 -> [a] -- | The sort function implements a stable sorting algorithm. It is -- a special case of sortBy, which allows the programmer to supply -- their own comparison function. -- -- Elements are arranged from lowest to highest, keeping duplicates in -- the order they appeared in the input. -- -- 
--   >>> sort [1,6,4,3,2,5]
--   [1,2,3,4,5,6]
--
sort :: Ord a => [a] -> [a] -- | Sort a list by comparing the results of a key function applied to each -- element. sortOn f is equivalent to sortBy (comparing -- f), but has the performance advantage of only evaluating -- f once for each element in the input list. This is called the -- decorate-sort-undecorate paradigm, or Schwartzian transform. -- -- Elements are arranged from lowest to highest, keeping duplicates in -- the order they appeared in the input. -- -- 
--   >>> sortOn fst [(2, "world"), (4, "!"), (1, "Hello")]
--   [(1,"Hello"),(2,"world"),(4,"!")]
--
sortOn :: Ord b => (a -> b) -> [a] -> [a] -- | <math>. The insert function takes an element and a list -- and inserts the element into the list at the first position where it -- is less than or equal to the next element. In particular, if the list -- is sorted before the call, the result will also be sorted. It is a -- special case of insertBy, which allows the programmer to supply -- their own comparison function. -- -- 
--   >>> insert 4 [1,2,3,5,6,7]
--   [1,2,3,4,5,6,7]
--
insert :: Ord a => a -> [a] -> [a] zip :: (Consumable a, Consumable b) => [a] %1 -> [b] %1 -> [(a, b)] -- | Same as zip, but returns the leftovers instead of consuming -- them. zip' :: [a] %1 -> [b] %1 -> ([(a, b)], Maybe (Either (NonEmpty a) (NonEmpty b))) zip3 :: (Consumable a, Consumable b, Consumable c) => [a] %1 -> [b] %1 -> [c] %1 -> [(a, b, c)] zipWith :: (Consumable a, Consumable b) => (a %1 -> b %1 -> c) -> [a] %1 -> [b] %1 -> [c] -- | Same as zipWith, but returns the leftovers instead of consuming -- them. zipWith' :: (a %1 -> b %1 -> c) -> [a] %1 -> [b] %1 -> ([c], Maybe (Either (NonEmpty a) (NonEmpty b))) zipWith3 :: forall a b c d. (Consumable a, Consumable b, Consumable c) => (a %1 -> b %1 -> c %1 -> d) -> [a] %1 -> [b] %1 -> [c] %1 -> [d] unzip :: [(a, b)] %1 -> ([a], [b]) unzip3 :: [(a, b, c)] %1 -> ([a], [b], [c]) instance Data.Monoid.Linear.Internal.Semigroup.Semigroup (GHC.Base.NonEmpty a) instance Data.Monoid.Linear.Internal.Semigroup.Semigroup [a] instance Data.Monoid.Linear.Internal.Monoid.Monoid [a] -- | This module provides a replacement for Prelude with support -- for linear programming via linear versions of standard data types, -- functions and type classes. -- -- A simple example: -- -- 
--   >>> :set -XLinearTypes
--   
--   >>> :set -XNoImplicitPrelude
--   
--   >>> import Prelude.Linear
--   
--   >>> :{
--     boolToInt :: Bool %1-> Int
--     boolToInt False = 0
--     boolToInt True = 1
--   :}
--
-- -- 
--   >>> :{
--     makeInt :: Either Int Bool %1-> Int
--     makeInt = either id boolToInt
--   :}
--
-- -- This module is designed to be imported unqualifed. module Prelude.Linear -- | The character type Char is an enumeration whose values -- represent Unicode (or equivalently ISO/IEC 10646) code points (i.e. -- characters, see http://www.unicode.org/ for details). This set -- extends the ISO 8859-1 (Latin-1) character set (the first 256 -- characters), which is itself an extension of the ASCII character set -- (the first 128 characters). A character literal in Haskell has type -- Char. -- -- To convert a Char to or from the corresponding Int value -- defined by Unicode, use toEnum and fromEnum from the -- Enum class respectively (or equivalently ord and -- chr). data Char -- | Extract the first component of a pair. fst :: (a, b) -> a -- | Extract the second component of a pair. snd :: (a, b) -> b curry :: ((a, b) %p -> c) %q -> a %p -> b %p -> c uncurry :: (a %p -> b %p -> c) %q -> (a, b) %p -> c -- | Class Enum defines operations on sequentially ordered types. -- -- The enumFrom... methods are used in Haskell's translation of -- arithmetic sequences. -- -- Instances of Enum may be derived for any enumeration type -- (types whose constructors have no fields). The nullary constructors -- are assumed to be numbered left-to-right by fromEnum from -- 0 through n-1. See Chapter 10 of the Haskell -- Report for more details. -- -- For any type that is an instance of class Bounded as well as -- Enum, the following should hold: -- -- -- -- 
--   enumFrom     x   = enumFromTo     x maxBound
--   enumFromThen x y = enumFromThenTo x y bound
--     where
--       bound | fromEnum y >= fromEnum x = maxBound
--             | otherwise                = minBound
--
class Enum a -- | the successor of a value. For numeric types, succ adds 1. succ :: Enum a => a -> a -- | the predecessor of a value. For numeric types, pred subtracts -- 1. pred :: Enum a => a -> a -- | Convert from an Int. toEnum :: Enum a => Int -> a -- | Convert to an Int. It is implementation-dependent what -- fromEnum returns when applied to a value that is too large to -- fit in an Int. fromEnum :: Enum a => a -> Int -- | Used in Haskell's translation of [n..] with [n..] = -- enumFrom n, a possible implementation being enumFrom n = n : -- enumFrom (succ n). For example: -- -- enumFrom :: Enum a => a -> [a] -- | Used in Haskell's translation of [n,n'..] with [n,n'..] = -- enumFromThen n n', a possible implementation being -- enumFromThen n n' = n : n' : worker (f x) (f x n'), -- worker s v = v : worker s (s v), x = fromEnum n' - -- fromEnum n and f n y | n > 0 = f (n - 1) (succ y) | n < -- 0 = f (n + 1) (pred y) | otherwise = y For example: -- -- enumFromThen :: Enum a => a -> a -> [a] -- | Used in Haskell's translation of [n..m] with [n..m] = -- enumFromTo n m, a possible implementation being enumFromTo n -- m | n <= m = n : enumFromTo (succ n) m | otherwise = []. For -- example: -- -- enumFromTo :: Enum a => a -> a -> [a] -- | Used in Haskell's translation of [n,n'..m] with [n,n'..m] -- = enumFromThenTo n n' m, a possible implementation being -- enumFromThenTo n n' m = worker (f x) (c x) n m, x = -- fromEnum n' - fromEnum n, c x = bool (>=) ((x -- 0) f n y | n > 0 = f (n - 1) (succ y) | n < 0 = f (n + -- 1) (pred y) | otherwise = y and worker s c v m | c v m = v : -- worker s c (s v) m | otherwise = [] For example: -- -- enumFromThenTo :: Enum a => a -> a -> a -> [a] -- | The Bounded class is used to name the upper and lower limits of -- a type. Ord is not a superclass of Bounded since types -- that are not totally ordered may also have upper and lower bounds. -- -- The Bounded class may be derived for any enumeration type; -- minBound is the first constructor listed in the data -- declaration and maxBound is the last. Bounded may also -- be derived for single-constructor datatypes whose constituent types -- are in Bounded. class Bounded a minBound :: Bounded a => a maxBound :: Bounded a => a -- | A fixed-precision integer type with at least the range [-2^29 .. -- 2^29-1]. The exact range for a given implementation can be -- determined by using minBound and maxBound from the -- Bounded class. data Int -- | Arbitrary precision integers. In contrast with fixed-size integral -- types such as Int, the Integer type represents the -- entire infinite range of integers. -- -- Integers are stored in a kind of sign-magnitude form, hence do not -- expect two's complement form when using bit operations. -- -- If the value is small (fit into an Int), IS constructor -- is used. Otherwise Integer and IN constructors are used -- to store a BigNat representing respectively the positive or the -- negative value magnitude. -- -- Invariant: Integer and IN are used iff value doesn't fit -- in IS data Integer -- | Single-precision floating point numbers. It is desirable that this -- type be at least equal in range and precision to the IEEE -- single-precision type. data Float -- | Double-precision floating point numbers. It is desirable that this -- type be at least equal in range and precision to the IEEE -- double-precision type. data Double -- | Arbitrary-precision rational numbers, represented as a ratio of two -- Integer values. A rational number may be constructed using the -- % operator. type Rational = Ratio Integer -- | A Word is an unsigned integral type, with the same size as -- Int. data Word class (Num a, Ord a) => Real a -- | the rational equivalent of its real argument with full precision toRational :: Real a => a -> Rational -- | Integral numbers, supporting integer division. -- -- The Haskell Report defines no laws for Integral. However, -- Integral instances are customarily expected to define a -- Euclidean domain and have the following properties for the -- div/mod and quot/rem pairs, given suitable -- Euclidean functions f and g: -- -- -- -- An example of a suitable Euclidean function, for Integer's -- instance, is abs. class (Real a, Enum a) => Integral a -- | integer division truncated toward zero quot :: Integral a => a -> a -> a -- | integer remainder, satisfying -- -- 
--   (x `quot` y)*y + (x `rem` y) == x
--
rem :: Integral a => a -> a -> a -- | integer division truncated toward negative infinity div :: Integral a => a -> a -> a -- | integer modulus, satisfying -- -- 
--   (x `div` y)*y + (x `mod` y) == x
--
mod :: Integral a => a -> a -> a -- | simultaneous quot and rem quotRem :: Integral a => a -> a -> (a, a) -- | simultaneous div and mod divMod :: Integral a => a -> a -> (a, a) -- | conversion to Integer toInteger :: Integral a => a -> Integer infixl 7 `div` infixl 7 `mod` infixl 7 `quot` infixl 7 `rem` -- | Trigonometric and hyperbolic functions and related functions. -- -- The Haskell Report defines no laws for Floating. However, -- (+), (*) and exp are -- customarily expected to define an exponential field and have the -- following properties: -- -- class Fractional a => Floating a pi :: Floating a => a exp :: Floating a => a -> a log :: Floating a => a -> a sqrt :: Floating a => a -> a (**) :: Floating a => a -> a -> a logBase :: Floating a => a -> a -> a sin :: Floating a => a -> a cos :: Floating a => a -> a tan :: Floating a => a -> a asin :: Floating a => a -> a acos :: Floating a => a -> a atan :: Floating a => a -> a sinh :: Floating a => a -> a cosh :: Floating a => a -> a tanh :: Floating a => a -> a asinh :: Floating a => a -> a acosh :: Floating a => a -> a atanh :: Floating a => a -> a infixr 8 ** -- | Fractional numbers, supporting real division. -- -- The Haskell Report defines no laws for Fractional. However, -- (+) and (*) are customarily expected -- to define a division ring and have the following properties: -- -- -- -- Note that it isn't customarily expected that a type instance of -- Fractional implement a field. However, all instances in -- base do. class Num a => Fractional a -- | Fractional division. (/) :: Fractional a => a -> a -> a -- | Reciprocal fraction. recip :: Fractional a => a -> a -- | Conversion from a Rational (that is Ratio -- Integer). A floating literal stands for an application of -- fromRational to a value of type Rational, so such -- literals have type (Fractional a) => a. fromRational :: Fractional a => Rational -> a infixl 7 / -- | Extracting components of fractions. class (Real a, Fractional a) => RealFrac a -- | The function properFraction takes a real fractional number -- x and returns a pair (n,f) such that x = -- n+f, and: -- -- -- -- The default definitions of the ceiling, floor, -- truncate and round functions are in terms of -- properFraction. properFraction :: (RealFrac a, Integral b) => a -> (b, a) -- | truncate x returns the integer nearest x -- between zero and x truncate :: (RealFrac a, Integral b) => a -> b -- | round x returns the nearest integer to x; the -- even integer if x is equidistant between two integers round :: (RealFrac a, Integral b) => a -> b -- | ceiling x returns the least integer not less than -- x ceiling :: (RealFrac a, Integral b) => a -> b -- | floor x returns the greatest integer not greater than -- x floor :: (RealFrac a, Integral b) => a -> b -- | Efficient, machine-independent access to the components of a -- floating-point number. class (RealFrac a, Floating a) => RealFloat a -- | a constant function, returning the radix of the representation (often -- 2) floatRadix :: RealFloat a => a -> Integer -- | a constant function, returning the number of digits of -- floatRadix in the significand floatDigits :: RealFloat a => a -> Int -- | a constant function, returning the lowest and highest values the -- exponent may assume floatRange :: RealFloat a => a -> (Int, Int) -- | The function decodeFloat applied to a real floating-point -- number returns the significand expressed as an Integer and an -- appropriately scaled exponent (an Int). If -- decodeFloat x yields (m,n), then x -- is equal in value to m*b^^n, where b is the -- floating-point radix, and furthermore, either m and -- n are both zero or else b^(d-1) <= abs m < -- b^d, where d is the value of floatDigits -- x. In particular, decodeFloat 0 = (0,0). If the -- type contains a negative zero, also decodeFloat (-0.0) = -- (0,0). The result of decodeFloat x is -- unspecified if either of isNaN x or -- isInfinite x is True. decodeFloat :: RealFloat a => a -> (Integer, Int) -- | encodeFloat performs the inverse of decodeFloat in the -- sense that for finite x with the exception of -0.0, -- uncurry encodeFloat (decodeFloat x) = x. -- encodeFloat m n is one of the two closest -- representable floating-point numbers to m*b^^n (or -- ±Infinity if overflow occurs); usually the closer, but if -- m contains too many bits, the result may be rounded in the -- wrong direction. encodeFloat :: RealFloat a => Integer -> Int -> a -- | exponent corresponds to the second component of -- decodeFloat. exponent 0 = 0 and for finite -- nonzero x, exponent x = snd (decodeFloat x) -- + floatDigits x. If x is a finite floating-point -- number, it is equal in value to significand x * b ^^ -- exponent x, where b is the floating-point radix. -- The behaviour is unspecified on infinite or NaN values. exponent :: RealFloat a => a -> Int -- | The first component of decodeFloat, scaled to lie in the open -- interval (-1,1), either 0.0 or of absolute -- value >= 1/b, where b is the floating-point -- radix. The behaviour is unspecified on infinite or NaN -- values. significand :: RealFloat a => a -> a -- | multiplies a floating-point number by an integer power of the radix scaleFloat :: RealFloat a => Int -> a -> a -- | True if the argument is an IEEE "not-a-number" (NaN) value isNaN :: RealFloat a => a -> Bool -- | True if the argument is an IEEE infinity or negative infinity isInfinite :: RealFloat a => a -> Bool -- | True if the argument is too small to be represented in -- normalized format isDenormalized :: RealFloat a => a -> Bool -- | True if the argument is an IEEE negative zero isNegativeZero :: RealFloat a => a -> Bool -- | True if the argument is an IEEE floating point number isIEEE :: RealFloat a => a -> Bool -- | a version of arctangent taking two real floating-point arguments. For -- real floating x and y, atan2 y x -- computes the angle (from the positive x-axis) of the vector from the -- origin to the point (x,y). atan2 y x returns -- a value in the range [-pi, pi]. It follows the -- Common Lisp semantics for the origin when signed zeroes are supported. -- atan2 y 1, with y in a type that is -- RealFloat, should return the same value as atan -- y. A default definition of atan2 is provided, but -- implementors can provide a more accurate implementation. atan2 :: RealFloat a => a -> a -> a -- | the same as flip (-). -- -- Because - is treated specially in the Haskell grammar, -- (- e) is not a section, but an application of -- prefix negation. However, (subtract -- exp) is equivalent to the disallowed section. subtract :: Num a => a -> a -> a even :: Integral a => a -> Bool odd :: Integral a => a -> Bool -- | gcd x y is the non-negative factor of both x -- and y of which every common factor of x and -- y is also a factor; for example gcd 4 2 = 2, -- gcd (-4) 6 = 2, gcd 0 4 = 4. -- gcd 0 0 = 0. (That is, the common divisor -- that is "greatest" in the divisibility preordering.) -- -- Note: Since for signed fixed-width integer types, abs -- minBound < 0, the result may be negative if one of the -- arguments is minBound (and necessarily is if the other -- is 0 or minBound) for such types. gcd :: Integral a => a -> a -> a -- | lcm x y is the smallest positive integer that both -- x and y divide. lcm :: Integral a => a -> a -> a -- | raise a number to a non-negative integral power (^) :: (Num a, Integral b) => a -> b -> a infixr 8 ^ -- | raise a number to an integral power (^^) :: (Fractional a, Integral b) => a -> b -> a infixr 8 ^^ -- | general coercion from integral types fromIntegral :: (Integral a, Num b) => a -> b -- | general coercion to fractional types realToFrac :: (Real a, Fractional b) => a -> b -- | Linearly typed replacement for the standard (<*) function. (<*) :: (Applicative f, Consumable b) => f a %1 -> f b %1 -> f a infixl 4 <* id :: a %q -> a const :: a %q -> b -> a -- | Beware: (.) is not compatible with the standard one because -- it is higher-order and we don't have sufficient multiplicity -- polymorphism yet. (.) :: forall {rep} b (c :: TYPE rep) a q m n. (b %1 -> c) %q -> (a %1 -> b) %m -> a %n -> c infixr 9 . -- | Replacement for the flip function with generalized multiplicities. flip :: (a %p -> b %q -> c) %r -> b %q -> a %p -> c ($) :: forall {rep} a (b :: TYPE rep) p q. (a %p -> b) %q -> a %p -> b infixr 0 $ (&) :: forall {rep} a (b :: TYPE rep) p q. a %p -> (a %p -> b) %q -> b infixl 1 & -- | until p f yields the result of applying f -- until p holds. until :: (a -> Bool) -> (a -> a) -> a -> a -- | error stops execution and displays an error message. error :: forall (r :: RuntimeRep) (a :: TYPE r). HasCallStack => [Char] -> a -- | A variant of error that does not produce a stack trace. errorWithoutStackTrace :: forall (r :: RuntimeRep) (a :: TYPE r). [Char] -> a -- | A special case of error. It is expected that compilers will -- recognize this and insert error messages which are more appropriate to -- the context in which undefined appears. undefined :: forall (r :: RuntimeRep) (a :: TYPE r). HasCallStack => a -- | seq x y only forces x to head normal form, therefore -- is not guaranteed to consume x when the resulting computation -- is consumed. Therefore, seq cannot be linear in it's first -- argument. seq :: a -> b %q -> b infixr 0 `seq` ($!) :: forall {rep} a (b :: TYPE rep) p q. (a %p -> b) %q -> a %p -> b infixr 0 $! -- | The shows functions return a function that prepends the -- output String to an existing String. This allows -- constant-time concatenation of results using function composition. type ShowS = String -> String -- | Conversion of values to readable Strings. -- -- Derived instances of Show have the following properties, which -- are compatible with derived instances of Read: -- -- -- -- For example, given the declarations -- -- 
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--
-- -- the derived instance of Show is equivalent to -- -- 
--   instance (Show a) => Show (Tree a) where
--   
--          showsPrec d (Leaf m) = showParen (d > app_prec) $
--               showString "Leaf " . showsPrec (app_prec+1) m
--            where app_prec = 10
--   
--          showsPrec d (u :^: v) = showParen (d > up_prec) $
--               showsPrec (up_prec+1) u .
--               showString " :^: "      .
--               showsPrec (up_prec+1) v
--            where up_prec = 5
--
-- -- Note that right-associativity of :^: is ignored. For example, -- -- class Show a -- | Convert a value to a readable String. -- -- showsPrec should satisfy the law -- -- 
--   showsPrec d x r ++ s  ==  showsPrec d x (r ++ s)
--
-- -- Derived instances of Read and Show satisfy the -- following: -- -- -- -- That is, readsPrec parses the string produced by -- showsPrec, and delivers the value that showsPrec started -- with. showsPrec :: Show a => Int -> a -> ShowS -- | A specialised variant of showsPrec, using precedence context -- zero, and returning an ordinary String. show :: Show a => a -> String -- | The method showList is provided to allow the programmer to give -- a specialised way of showing lists of values. For example, this is -- used by the predefined Show instance of the Char type, -- where values of type String should be shown in double quotes, -- rather than between square brackets. showList :: Show a => [a] -> ShowS -- | equivalent to showsPrec with a precedence of 0. shows :: Show a => a -> ShowS -- | utility function converting a Char to a show function that -- simply prepends the character unchanged. showChar :: Char -> ShowS -- | utility function converting a String to a show function that -- simply prepends the string unchanged. showString :: String -> ShowS -- | utility function that surrounds the inner show function with -- parentheses when the Bool parameter is True. showParen :: Bool -> ShowS -> ShowS -- | A parser for a type a, represented as a function that takes a -- String and returns a list of possible parses as -- (a,String) pairs. -- -- Note that this kind of backtracking parser is very inefficient; -- reading a large structure may be quite slow (cf ReadP). type ReadS a = String -> [(a, String)] -- | Parsing of Strings, producing values. -- -- Derived instances of Read make the following assumptions, which -- derived instances of Show obey: -- -- -- -- For example, given the declarations -- -- 
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--
-- -- the derived instance of Read in Haskell 2010 is equivalent to -- -- 
--   instance (Read a) => Read (Tree a) where
--   
--           readsPrec d r =  readParen (d > app_prec)
--                            (\r -> [(Leaf m,t) |
--                                    ("Leaf",s) <- lex r,
--                                    (m,t) <- readsPrec (app_prec+1) s]) r
--   
--                         ++ readParen (d > up_prec)
--                            (\r -> [(u:^:v,w) |
--                                    (u,s) <- readsPrec (up_prec+1) r,
--                                    (":^:",t) <- lex s,
--                                    (v,w) <- readsPrec (up_prec+1) t]) r
--   
--             where app_prec = 10
--                   up_prec = 5
--
-- -- Note that right-associativity of :^: is unused. -- -- The derived instance in GHC is equivalent to -- -- 
--   instance (Read a) => Read (Tree a) where
--   
--           readPrec = parens $ (prec app_prec $ do
--                                    Ident "Leaf" <- lexP
--                                    m <- step readPrec
--                                    return (Leaf m))
--   
--                        +++ (prec up_prec $ do
--                                    u <- step readPrec
--                                    Symbol ":^:" <- lexP
--                                    v <- step readPrec
--                                    return (u :^: v))
--   
--             where app_prec = 10
--                   up_prec = 5
--   
--           readListPrec = readListPrecDefault
--
-- -- Why do both readsPrec and readPrec exist, and why does -- GHC opt to implement readPrec in derived Read instances -- instead of readsPrec? The reason is that readsPrec is -- based on the ReadS type, and although ReadS is mentioned -- in the Haskell 2010 Report, it is not a very efficient parser data -- structure. -- -- readPrec, on the other hand, is based on a much more efficient -- ReadPrec datatype (a.k.a "new-style parsers"), but its -- definition relies on the use of the RankNTypes language -- extension. Therefore, readPrec (and its cousin, -- readListPrec) are marked as GHC-only. Nevertheless, it is -- recommended to use readPrec instead of readsPrec -- whenever possible for the efficiency improvements it brings. -- -- As mentioned above, derived Read instances in GHC will -- implement readPrec instead of readsPrec. The default -- implementations of readsPrec (and its cousin, readList) -- will simply use readPrec under the hood. If you are writing a -- Read instance by hand, it is recommended to write it like so: -- -- 
--   instance Read T where
--     readPrec     = ...
--     readListPrec = readListPrecDefault
--
class Read a -- | attempts to parse a value from the front of the string, returning a -- list of (parsed value, remaining string) pairs. If there is no -- successful parse, the returned list is empty. -- -- Derived instances of Read and Show satisfy the -- following: -- -- -- -- That is, readsPrec parses the string produced by -- showsPrec, and delivers the value that showsPrec started -- with. readsPrec :: Read a => Int -> ReadS a -- | The method readList is provided to allow the programmer to give -- a specialised way of parsing lists of values. For example, this is -- used by the predefined Read instance of the Char type, -- where values of type String should be are expected to use -- double quotes, rather than square brackets. readList :: Read a => ReadS [a] -- | equivalent to readsPrec with a precedence of 0. reads :: Read a => ReadS a -- | readParen True p parses what p parses, -- but surrounded with parentheses. -- -- readParen False p parses what p -- parses, but optionally surrounded with parentheses. readParen :: Bool -> ReadS a -> ReadS a -- | The read function reads input from a string, which must be -- completely consumed by the input process. read fails with an -- error if the parse is unsuccessful, and it is therefore -- discouraged from being used in real applications. Use readMaybe -- or readEither for safe alternatives. -- -- 
--   >>> read "123" :: Int
--   123
--
-- -- 
--   >>> read "hello" :: Int
--   *** Exception: Prelude.read: no parse
--
read :: Read a => String -> a -- | The lex function reads a single lexeme from the input, -- discarding initial white space, and returning the characters that -- constitute the lexeme. If the input string contains only white space, -- lex returns a single successful `lexeme' consisting of the -- empty string. (Thus lex "" = [("","")].) If there is -- no legal lexeme at the beginning of the input string, lex fails -- (i.e. returns []). -- -- This lexer is not completely faithful to the Haskell lexical syntax in -- the following respects: -- -- lex :: ReadS String -- | A value of type IO a is a computation which, when -- performed, does some I/O before returning a value of type a. -- -- There is really only one way to "perform" an I/O action: bind it to -- Main.main in your program. When your program is run, the I/O -- will be performed. It isn't possible to perform I/O from an arbitrary -- function, unless that function is itself in the IO monad and -- called at some point, directly or indirectly, from Main.main. -- -- IO is a monad, so IO actions can be combined using -- either the do-notation or the >> and >>= -- operations from the Monad class. data IO a -- | Write a character to the standard output device (same as -- hPutChar stdout). putChar :: Char -> IO () -- | Write a string to the standard output device (same as hPutStr -- stdout). putStr :: String -> IO () -- | The same as putStr, but adds a newline character. putStrLn :: String -> IO () -- | The print function outputs a value of any printable type to the -- standard output device. Printable types are those that are instances -- of class Show; print converts values to strings for -- output using the show operation and adds a newline. -- -- For example, a program to print the first 20 integers and their powers -- of 2 could be written as: -- -- 
--   main = print ([(n, 2^n) | n <- [0..19]])
--
print :: Show a => a -> IO () -- | Read a character from the standard input device (same as -- hGetChar stdin). getChar :: IO Char -- | Read a line from the standard input device (same as hGetLine -- stdin). getLine :: IO String -- | The getContents operation returns all user input as a single -- string, which is read lazily as it is needed (same as -- hGetContents stdin). getContents :: IO String -- | The interact function takes a function of type -- String->String as its argument. The entire input from the -- standard input device is passed to this function as its argument, and -- the resulting string is output on the standard output device. interact :: (String -> String) -> IO () -- | File and directory names are values of type String, whose -- precise meaning is operating system dependent. Files can be opened, -- yielding a handle which can then be used to operate on the contents of -- that file. type FilePath = String -- | The readFile function reads a file and returns the contents of -- the file as a string. The file is read lazily, on demand, as with -- getContents. readFile :: FilePath -> IO String -- | The computation writeFile file str function writes the -- string str, to the file file. writeFile :: FilePath -> String -> IO () -- | The computation appendFile file str function appends -- the string str, to the file file. -- -- Note that writeFile and appendFile write a literal -- string to a file. To write a value of any printable type, as with -- print, use the show function to convert the value to a -- string first. -- -- 
--   main = appendFile "squares" (show [(x,x*x) | x <- [0,0.1..2]])
--
appendFile :: FilePath -> String -> IO () -- | The readIO function is similar to read except that it -- signals parse failure to the IO monad instead of terminating -- the program. readIO :: Read a => String -> IO a -- | The readLn function combines getLine and readIO. readLn :: Read a => IO a -- | Ur a represents unrestricted values of type a in a -- linear context. The key idea is that because the contructor holds -- a with a regular arrow, a function that uses Ur a -- linearly can use a however it likes. -- -- 
--   someLinear :: Ur a %1-> (a,a)
--   someLinear (Ur a) = (a,a)
--
data Ur a [Ur] :: a -> Ur a -- | Get an a out of an Ur a. If you call this function -- on a linearly bound Ur a, then the a you get out has -- to be used linearly, for example: -- -- 
--   restricted :: Ur a %1-> b
--   restricted x = f (unur x)
--     where
--       -- f __must__ be linear
--       f :: a %1-> b
--       f x = ...
--
unur :: Ur a %1 -> a class Consumable a consume :: Consumable a => a %1 -> () -- | The laws of Dupable are dual to those of Monoid: -- -- -- -- where the (≃) sign represents equality up to type -- isomorphism. -- -- -- -- (Laws 1-2 and 5-6 are equivalent) -- -- Implementation of Dupable for Movable types should be -- done with deriving via AsMovable. -- -- Implementation of Dupable for other types can be done with -- deriving via Generically. Note that at present this -- mechanism can have performance problems for recursive parameterized -- types. Specifically, the methods will not specialize to underlying -- Dupable instances. See this GHC issue. class Consumable a => Dupable a -- | Creates a Replicator for the given a. -- -- You usually want to define this method using Replicator's -- Applicative instance. For instance, here is an implementation -- of Dupable [a]: -- -- 
--   instance Dupable a => Dupable [a] where
--     dupR [] = pure []
--     dupR (a : as) = (:) <$> dupR a <*> dupR as
--
dupR :: Dupable a => a %1 -> Replicator a -- | Creates two as from a Dupable a, in a linear -- fashion. dup2 :: Dupable a => a %1 -> (a, a) -- | Use Movable a to represent a type which can be used -- many times even when given linearly. Simple data types such as -- Bool or [] are Movable. Though, bear in mind -- that this typically induces a deep copy of the value. -- -- Formally, Movable a is the class of coalgebras -- of the Ur comonad. That is -- -- -- -- Additionally, a Movable instance must be compatible with its -- Dupable parent instance. That is: -- -- class Dupable a => Movable a move :: Movable a => a %1 -> Ur a -- | Consume the first argument and return the second argument. This is -- like seq but the first argument is restricted to be -- Consumable. lseq :: Consumable a => a %1 -> b %1 -> b infixr 0 `lseq` -- | Creates two as from a Dupable a. Same -- function as dup2. dup :: Dupable a => a %1 -> (a, a) -- | Creates 3 as from a Dupable a, in a linear -- fashion. dup3 :: Dupable a => a %1 -> (a, a, a) -- | Convenience operator when a higher-order function expects a non-linear -- arrow but we have a linear arrow. forget :: forall {rep} a (b :: TYPE rep). (a %1 -> b) %1 -> a -> b -- | This module redefines IO with linear types. -- -- To use this IO, do the following: -- -- -- --

Example

-- -- 
--   import qualified System.IO.Linear as Linear
--   
--   main :: IO ()
--   main = Linear.withLinearIO $
--     Linear.fromSystemIOU $ putStrLn "hello world today"
--
-- --

Replacing The Original IO With This Module.

-- -- This module will be deprecated if the definition for IO found -- here is upstreamed in System.IO. When multiplicity-polymorphism -- is implemented, this module will supercede IO by providing a seamless -- replacement for System.IO that won't break non-linear code. module System.IO.Linear -- | This is the linear IO monad. It is a newtype around a function that -- transitions from one State# RealWorld to another, producing a -- value of type a along with it. The State# RealWorld -- is the state of the world/machine outside the program. -- -- The only way, such a computation is run is by putting it in -- Main.main somewhere. -- -- Note that this is the same definition as the standard IO monad, but -- with a linear arrow enforcing the implicit invariant that IO actions -- linearly thread the state of the real world. Hence, we can safely -- release the constructor to this newtype. newtype IO a IO :: (State# RealWorld %1 -> (# State# RealWorld, a #)) -> IO a -- | Coerces a standard IO action into a linear IO action. Note that the -- value a must be used linearly in the linear IO monad. fromSystemIO :: IO a %1 -> IO a -- | Coerces a standard IO action to a linear IO action, allowing you to -- use the result of type a in a non-linear manner by wrapping -- it inside Ur. fromSystemIOU :: IO a -> IO (Ur a) -- | Use at the top of main function in your program to switch to -- the linearly typed version of IO: -- -- 
--   main :: IO ()
--   main = Linear.withLinearIO $ do ...
--
withLinearIO :: IO (Ur a) -> IO a newIORef :: a -> IO (Ur (IORef a)) readIORef :: IORef a -> IO (Ur a) writeIORef :: IORef a -> a -> IO () throwIO :: Exception e => e -> IO a catch :: Exception e => IO (Ur a) -> (e -> IO (Ur a)) -> IO (Ur a) mask_ :: IO a -> IO a instance Data.Functor.Linear.Internal.Applicative.Applicative System.IO.Linear.IO instance Data.Functor.Linear.Internal.Functor.Functor System.IO.Linear.IO instance Control.Functor.Linear.Internal.Class.Functor System.IO.Linear.IO instance Control.Functor.Linear.Internal.Class.Applicative System.IO.Linear.IO instance Control.Functor.Linear.Internal.Class.Monad System.IO.Linear.IO instance Data.Monoid.Linear.Internal.Semigroup.Semigroup a => Data.Monoid.Linear.Internal.Semigroup.Semigroup (System.IO.Linear.IO a) instance Data.Monoid.Linear.Internal.Monoid.Monoid a => Data.Monoid.Linear.Internal.Monoid.Monoid (System.IO.Linear.IO a) -- | This module defines an IO monad for linearly working with system -- resources like files. It provides tools to take resources that are -- currently unsafely accessible from System.IO and use them in -- this monad. -- -- Import this module qualified to avoid name clashes. -- -- To use this RIO monad, create some RIO computation, run it to -- get a System.IO computation. -- --

A simple example

-- -- 
--   >>> :set -XLinearTypes
--   
--   >>> :set -XQualifiedDo
--   
--   >>> :set -XNoImplicitPrelude
--   
--   >>> import qualified System.IO.Resource.Linear as Linear
--   
--   >>> import qualified Control.Functor.Linear as Control
--   
--   >>> import qualified Data.Text as Text
--   
--   >>> import Prelude.Linear
--   
--   >>> import qualified Prelude
--   
--   >>> :{
--    linearWriteToFile :: IO ()
--    linearWriteToFile = Linear.run $ Control.do
--      handle1 <- Linear.openFile "/home/user/test.txt" Linear.WriteMode
--      handle2 <- Linear.hPutStrLn handle1 (Text.pack "hello there")
--      () <- Linear.hClose handle2
--      Control.return (Ur ())
--   :}
--
-- -- To enable do notation, QualifiedDo extension is used. But -- since QualifiedDo only modifies the desugaring of binds, we still need -- to qualify return. module System.IO.Resource.Linear -- | The resource-aware I/O monad. This monad guarantees that acquired -- resources are always released. data RIO a -- | Take a RIO computation with a value a that is not -- linearly bound and make it a System.IO computation. run :: RIO (Ur a) -> IO a type Handle = Resource Handle -- | See System.IO.openFile openFile :: FilePath -> IOMode -> RIO Handle -- | See System.IO.openBinaryFile openBinaryFile :: FilePath -> IOMode -> RIO Handle -- | See openFile data IOMode ReadMode :: IOMode WriteMode :: IOMode AppendMode :: IOMode ReadWriteMode :: IOMode -- | Specialised alias for release hClose :: Handle %1 -> RIO () hIsEOF :: Handle %1 -> RIO (Ur Bool, Handle) hGetChar :: Handle %1 -> RIO (Ur Char, Handle) hPutChar :: Handle %1 -> Char -> RIO Handle hGetLine :: Handle %1 -> RIO (Ur Text, Handle) hPutStr :: Handle %1 -> Text -> RIO Handle hPutStrLn :: Handle %1 -> Text -> RIO Handle -- | See System.IO.hSeek. hSeek :: Handle %1 -> SeekMode -> Integer -> RIO Handle -- | A mode that determines the effect of hSeek hdl mode i. data SeekMode -- | the position of hdl is set to i. AbsoluteSeek :: SeekMode -- | the position of hdl is set to offset i from the -- current position. RelativeSeek :: SeekMode -- | the position of hdl is set to offset i from the end -- of the file. SeekFromEnd :: SeekMode -- | See System.IO.hTell. hTell :: Handle %1 -> RIO (Ur Integer, Handle) -- | The type of system resources. To create and use resources, you need to -- use the API since the constructor is not released. data Resource a -- | release r calls the release function provided when -- r was acquired. release :: Resource a %1 -> RIO () -- | Given a resource in the System.IO.Linear.IO monad, and given a -- function to release that resource, provides that resource in the -- RIO monad. For example, releasing a Handle from -- System.IO would be done with fromSystemIO hClose. -- Because this release function is an input, and could be wrong, this -- function is unsafe. unsafeAcquire :: IO (Ur a) -> (a -> IO ()) -> RIO (Resource a) -- | Given a System.IO computation on an unsafe resource, lift it to -- RIO computaton on the acquired resource. That is function of -- type a -> IO b turns into a function of type Resource -- a %1-> RIO (Ur b) along with threading the Resource -- a. -- -- unsafeFromSystemIOResource is only safe to use on actions which -- do not release the resource. -- -- Note that the result b can be used non-linearly. unsafeFromSystemIOResource :: (a -> IO b) -> Resource a %1 -> RIO (Ur b, Resource a) -- | Specialised variant of unsafeFromSystemIOResource for actions -- that don't return a value. unsafeFromSystemIOResource_ :: (a -> IO ()) -> Resource a %1 -> RIO (Resource a) -- | Deprecated alias for Resource -- | Deprecated: UnsafeResource has been renamed to Resource type UnsafeResource = Resource -- | Deprecated alias of the release function -- | Deprecated: unsafeRelease has been renamed to release unsafeRelease :: Resource a %1 -> RIO () -- | A thin wrapper on top of Debug.Trace, providing linear versions -- of tracing functions. -- -- It only contains minimal amount of documentation; you should consult -- the original Debug.Trace module for more detailed information. module Debug.Trace.Linear -- | The trace function outputs the trace message given as its first -- argument, before returning the second argument as its result. trace :: String %1 -> a %1 -> a -- | Like trace, but uses show on the argument to convert it -- to a String. traceShow :: Show a => a -> b %1 -> b -- | Like trace but returns the message instead of a third value. traceId :: String %1 -> String -- | Like trace, but additionally prints a call stack if one is -- available. traceStack :: String %1 -> a %1 -> a -- | The traceIO function outputs the trace message from the IO -- monad. This sequences the output with respect to other IO actions. traceIO :: String %1 -> IO () -- | Like trace but returning unit in an arbitrary -- Applicative context. Allows for convenient use in do-notation. traceM :: Applicative f => String %1 -> f () -- | Like traceM, but uses show on the argument to convert it -- to a String. traceShowM :: (Show a, Applicative f) => a -> f () -- | The traceEvent function behaves like trace with the -- difference that the message is emitted to the eventlog, if eventlog -- profiling is available and enabled at runtime. traceEvent :: String %1 -> a %1 -> a -- | The traceEventIO function emits a message to the eventlog, if -- eventlog profiling is available and enabled at runtime. traceEventIO :: String %1 -> IO () -- | The traceMarker function emits a marker to the eventlog, if -- eventlog profiling is available and enabled at runtime. The -- String is the name of the marker. The name is just used in -- the profiling tools to help you keep clear which marker is which. traceMarker :: String %1 -> a %1 -> a -- | The traceMarkerIO function emits a marker to the eventlog, if -- eventlog profiling is available and enabled at runtime. traceMarkerIO :: String %1 -> IO () -- | The names exported by this module are closely modeled on those in -- Prelude and Data.List, but also on -- Pipes.Prelude, Pipes.Group and Pipes.Parse. The -- module may be said to give independent expression to the conception of -- Producer / Source / Generator manipulation articulated in the latter -- two modules. Because we dispense with piping and conduiting, the -- distinction between all of these modules collapses. Some things are -- lost but much is gained: on the one hand, everything comes much closer -- to ordinary beginning Haskell programming and, on the other, acquires -- the plasticity of programming directly with a general free monad type. -- The leading type, Stream (Of a) m r is chosen to permit an -- api that is as close as possible to that of Data.List and the -- Prelude. -- -- Import qualified thus: -- -- 
--   import Streaming
--   import qualified Streaming.Prelude as S
--
-- -- For the examples below, one sometimes needs -- -- 
--   import Streaming.Prelude (each, yield, next, mapped, stdoutLn, stdinLn)
--   import Data.Function ((&))
--
-- -- Other libraries that come up in passing are -- -- 
--   import qualified Control.Foldl as L -- cabal install foldl
--   import qualified Pipes as P
--   import qualified Pipes.Prelude as P
--   import qualified System.IO as IO
--
-- -- Here are some correspondences between the types employed here and -- elsewhere: -- -- 
--                 streaming             |            pipes               |       conduit       |  io-streams
--   -------------------------------------------------------------------------------------------------------------------
--   Stream (Of a) m ()                  | Producer a m ()                | Source m a          | InputStream a
--                                       | ListT m a                      | ConduitM () o m ()  | Generator r ()
--   -------------------------------------------------------------------------------------------------------------------
--   Stream (Of a) m r                   | Producer a m r                 | ConduitM () o m r   | Generator a r
--   -------------------------------------------------------------------------------------------------------------------
--   Stream (Of a) m (Stream (Of a) m r) | Producer a m (Producer a m r)  |
--   --------------------------------------------------------------------------------------------------------------------
--   Stream (Stream (Of a) m) r          | FreeT (Producer a m) m r       |
--   --------------------------------------------------------------------------------------------------------------------
--   --------------------------------------------------------------------------------------------------------------------
--   ByteString m ()                     | Producer ByteString m ()       | Source m ByteString  | InputStream ByteString
--   --------------------------------------------------------------------------------------------------------------------
--
module Streaming.Prelude.Linear data Stream f m r [Step] :: !f (Stream f m r) -> Stream f m r [Effect] :: m (Stream f m r) -> Stream f m r [Return] :: r -> Stream f m r -- | A left-strict pair; the base functor for streams of individual -- elements. data Of a b [:>] :: !a -> b -> Of a b infixr 5 :> -- | Write Strings to stdout using putStrLn; -- terminates on a broken output pipe (The name and implementation are -- modelled on the Pipes.Prelude stdoutLn). -- -- >>> withLinearIO $ Control.fmap move $ S.stdoutLn $ S.each $ -- words "one two three" one two three stdoutLn :: Stream (Of Text) IO () %1 -> IO () -- | Like stdoutLn but with an arbitrary return value stdoutLn' :: forall r. Stream (Of Text) IO r %1 -> IO r -- | Print the elements of a stream as they arise. print :: Show a => Stream (Of a) IO r %1 -> IO r -- | Write a stream to a handle and return the handle. toHandle :: Handle %1 -> Stream (Of Text) RIO r %1 -> RIO (r, Handle) -- | Write a stream of text as lines as lines to a file writeFile :: FilePath -> Stream (Of Text) RIO r %1 -> RIO r -- | Reduce a stream, performing its actions but ignoring its elements. -- -- 
--   >>> rest <- S.effects $ S.splitAt 2 $ each' [1..5]
--   >>> S.print rest
--   3
--   4
--   5
--
-- -- effects should be understood together with copy and is -- subject to the rules -- -- 
--   S.effects . S.copy       = id
--   hoist S.effects . S.copy = id
--
-- -- The similar effects and copy operations in -- Data.ByteString.Streaming obey the same rules. effects :: forall a m r. Monad m => Stream (Of a) m r %1 -> m r -- | Remove the elements from a stream of values, retaining the structure -- of layers. erase :: forall a m r. Monad m => Stream (Of a) m r %1 -> Stream Identity m r -- | Where a transformer returns a stream, run the effects of the stream, -- keeping the return value. This is usually used at the type -- -- 
--   drained :: Control.Monad m => Stream (Of a) m (Stream (Of b) m r) -> Stream (Of a) m r
--   drained = Control.join . Control.fmap (Control.lift . effects)
--
-- -- Here, for example, we split a stream in two places and throw out the -- middle segment: -- -- 
--   >>> rest <- S.print $ S.drained $ S.splitAt 2 $ S.splitAt 5 $ each' [1..7]
--   1
--   2
--   >>> S.print rest
--   6
--   7
--
drained :: (Monad m, Monad (t m), Functor (t m), MonadTrans t) => t m (Stream (Of a) m r) %1 -> t m r -- | Reduce a stream to its return value with a monadic action. -- -- 
--   >>> S.mapM_ Prelude.print $ each' [1..3]
--   1
--   2
--   3
--
-- -- 
--   >>> rest <- S.mapM_ Prelude.print $ S.splitAt 3 $ each' [1..10]
--   1
--   2
--   3
--   >>> S.sum rest
--   49 :> ()
--
mapM_ :: forall a m b r. (Consumable b, Monad m) => (a -> m b) -> Stream (Of a) m r %1 -> m r -- | Strict fold of a Stream of elements that preserves the return -- value. This does not short circuit and all effects are performed. The -- third parameter will often be id where a fold is written by -- hand: -- -- 
--   >>> S.fold (+) 0 id $ each' [1..10]
--   55 :> ()
--
-- -- 
--   >>> S.fold (*) 1 id $ S.fold (+) 0 id $ S.copy $ each' [1..10]
--   3628800 :> (55 :> ())
--
-- -- It can be used to replace a standard Haskell type with one more suited -- to writing a strict accumulation function. It is also crucial to the -- Applicative instance for Control.Foldl.Fold We can apply such -- a fold purely -- -- 
--   Control.Foldl.purely S.fold :: Control.Monad m => Fold a b -> Stream (Of a) m r %1-> m (Of b r)
--
-- -- Thus, specializing a bit: -- -- 
--   L.purely S.fold L.sum :: Stream (Of Int) Int r %1-> m (Of Int r)
--   mapped (L.purely S.fold L.sum) :: Stream (Stream (Of Int)) IO r %1-> Stream (Of Int) IO r
--
-- -- Here we use the Applicative instance for Control.Foldl.Fold -- to stream three-item segments of a stream together with their sums and -- products. -- -- 
--   >>> S.print $ mapped (L.purely S.fold (liftA3 (,,) L.list L.product L.sum)) $ chunksOf 3 $ each' 1..10
--   ([4,5,6],120,15)
--   ([7,8,9],504,24)
--   ([10],10,10)
--
fold :: forall x a b m r. Monad m => (x -> a -> x) -> x -> (x -> b) -> Stream (Of a) m r %1 -> m (Of b r) -- | Strict fold of a Stream of elements, preserving only the result -- of the fold, not the return value of the stream. This does not short -- circuit and all effects are performed. The third parameter will often -- be id where a fold is written by hand: -- -- 
--   >>> S.fold_ (+) 0 id $ each [1..10]
--   55
--
-- -- It can be used to replace a standard Haskell type with one more suited -- to writing a strict accumulation function. It is also crucial to the -- Applicative instance for Control.Foldl.Fold -- -- 
--   Control.Foldl.purely fold :: Control.Monad m => Fold a b -> Stream (Of a) m () %1-> m b
--
fold_ :: forall x a b m r. (Monad m, Consumable r) => (x -> a -> x) -> x -> (x -> b) -> Stream (Of a) m r %1 -> m b -- | Strict, monadic fold of the elements of a Stream (Of a) -- -- 
--   Control.Foldl.impurely foldM :: Control.Monad m => FoldM a b -> Stream (Of a) m r %1-> m (b, r)
--
-- -- Thus to accumulate the elements of a stream as a vector, together with -- a random element we might write: -- -- 
--   >>> L.impurely S.foldM (liftA2 (,) L.vectorM L.random) $ each' [1..10::Int] :: IO (Of (Vector Int, Maybe Int) ())
--   ([1,2,3,4,5,6,7,8,9,10],Just 9) :> ()
--
foldM :: forall x a m b r. Monad m => (x %1 -> a -> m x) -> m x -> (x %1 -> m b) -> Stream (Of a) m r %1 -> m (b, r) -- | Strict, monadic fold of the elements of a Stream (Of a) -- -- 
--   Control.Foldl.impurely foldM_ :: Control.Monad m => FoldM a b -> Stream (Of a) m () %1-> m b
--
foldM_ :: forall a m x b r. (Monad m, Consumable r) => (x %1 -> a -> m x) -> m x -> (x %1 -> m b) -> Stream (Of a) m r %1 -> m b -- | Note: does not short circuit all :: Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> m (Of Bool r) -- | Note: does not short circuit all_ :: (Consumable r, Monad m) => (a -> Bool) -> Stream (Of a) m r %1 -> m Bool -- | Note: does not short circuit any :: Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> m (Of Bool r) -- | Note: does not short circuit any_ :: (Consumable r, Monad m) => (a -> Bool) -> Stream (Of a) m r %1 -> m Bool -- | Fold a Stream of numbers into their sum with the return value -- -- 
--   mapped S.sum :: Stream (Stream (Of Int)) m r %1-> Stream (Of Int) m r
--
-- -- 
--   >>> S.sum $ each' [1..10]
--   55 :> ()
--
-- -- 
--   >>> (n :> rest)  <- S.sum $ S.splitAt 3 $ each' [1..10]
--   >>> System.IO.print n
--   6
--   >>> (m :> rest') <- S.sum $ S.splitAt 3 rest
--   >>> System.IO.print m
--   15
--   >>> S.print rest'
--   7
--   8
--   9
--   10
--
sum :: (Monad m, Num a) => Stream (Of a) m r %1 -> m (Of a r) -- | Fold a Stream of numbers into their sum sum_ :: (Monad m, Num a) => Stream (Of a) m () %1 -> m a -- | Fold a Stream of numbers into their product with the return -- value -- -- 
--   mapped product :: Stream (Stream (Of Int)) m r -> Stream (Of Int) m r
--
product :: (Monad m, Num a) => Stream (Of a) m r %1 -> m (Of a r) -- | Fold a Stream of numbers into their product product_ :: (Monad m, Num a) => Stream (Of a) m () %1 -> m a -- | Note that head exhausts the rest of the stream following the -- first element, performing all monadic effects via effects head :: Monad m => Stream (Of a) m r %1 -> m (Of (Maybe a) r) -- | Note that head exhausts the rest of the stream following the -- first element, performing all monadic effects via effects head_ :: (Consumable r, Monad m) => Stream (Of a) m r %1 -> m (Maybe a) last :: Monad m => Stream (Of a) m r %1 -> m (Of (Maybe a) r) last_ :: (Consumable r, Monad m) => Stream (Of a) m r %1 -> m (Maybe a) elem :: forall a m r. (Monad m, Eq a) => a -> Stream (Of a) m r %1 -> m (Of Bool r) infix 4 `elem` elem_ :: forall a m r. (Consumable r, Monad m, Eq a) => a -> Stream (Of a) m r %1 -> m Bool -- | Exhaust a stream deciding whether a was an element. notElem :: (Monad m, Eq a) => a -> Stream (Of a) m r %1 -> m (Of Bool r) notElem_ :: (Consumable r, Monad m, Eq a) => a -> Stream (Of a) m r %1 -> m Bool -- | Run a stream, keeping its length and its return value. -- -- 
--   >>> S.print $ mapped S.length $ chunksOf 3 $ S.each' [1..10]
--   3
--   3
--   3
--   1
--
length :: Monad m => Stream (Of a) m r %1 -> m (Of Int r) -- | Run a stream, remembering only its length: -- -- 
--   >>> runIdentity $ S.length_ (S.each [1..10] :: Stream (Of Int) Identity ())
--   10
--
length_ :: (Consumable r, Monad m) => Stream (Of a) m r %1 -> m Int -- | Convert an effectful Stream into a list alongside the return -- value -- -- 
--   mapped toList :: Stream (Stream (Of a) m) m r %1-> Stream (Of [a]) m r
--
-- -- Like toList_, toList breaks streaming; unlike -- toList_ it preserves the return value and thus is -- frequently useful with e.g. mapped -- -- 
--   >>> S.print $ mapped S.toList $ chunksOf 3 $ each' [1..9]
--   [1,2,3]
--   [4,5,6]
--   [7,8,9]
--
-- -- 
--   >>> S.print $ mapped S.toList $ chunksOf 2 $ S.replicateM 4 getLine
--   sEnter
--   tEnter
--   ["s","t"]
--   uEnter
--   vEnter
--   ["u","v"]
--
toList :: Monad m => Stream (Of a) m r %1 -> m (Of [a] r) -- | Convert an effectful Stream (Of a) into a list of as -- -- Note: Needless to say, this function does not stream properly. It is -- basically the same as Prelude mapM which, like -- replicateM, sequence and similar operations on -- traversable containers is a leading cause of space leaks. toList_ :: Monad m => Stream (Of a) m () %1 -> m [a] -- | Fold streamed items into their monoidal sum mconcat :: (Monad m, Monoid w) => Stream (Of w) m r %1 -> m (Of w r) mconcat_ :: (Consumable r, Monad m, Monoid w) => Stream (Of w) m r %1 -> m w minimum :: (Monad m, Ord a) => Stream (Of a) m r %1 -> m (Of (Maybe a) r) minimum_ :: (Consumable r, Monad m, Ord a) => Stream (Of a) m r %1 -> m (Maybe a) maximum :: (Monad m, Ord a) => Stream (Of a) m r %1 -> m (Of (Maybe a) r) maximum_ :: (Consumable r, Monad m, Ord a) => Stream (Of a) m r %1 -> m (Maybe a) -- | A natural right fold for consuming a stream of elements. See also the -- more general iterT in the Streaming module and the -- still more general destroy foldrM :: forall a m r. Monad m => (a -> m r %1 -> m r) -> Stream (Of a) m r %1 -> m r -- | A natural right fold for consuming a stream of elements. See also the -- more general iterTM in the Streaming module and the -- still more general destroy -- -- 
--   foldrT (\a p -> Streaming.yield a >> p) = id
--
foldrT :: forall a t m r. (Monad m, MonadTrans t, Monad (t m)) => (a -> t m r %1 -> t m r) -> Stream (Of a) m r %1 -> t m r -- | Read an IORef (Maybe a) or a similar device until it reads -- Nothing. reread provides convenient exit from the -- io-streams library -- -- 
--   reread readIORef    :: IORef (Maybe a) -> Stream (Of a) IO ()
--   reread Streams.read :: System.IO.Streams.InputStream a -> Stream (Of a) IO ()
--
reread :: Monad m => (s -> m (Ur (Maybe a))) -> s -> Stream (Of a) m () -- | The type -- -- 
--   Data.List.unzip     :: [(a,b)] -> ([a],[b])
--
-- -- might lead us to expect -- -- 
--   Streaming.unzip :: Stream (Of (a,b)) m r -> Stream (Of a) m (Stream (Of b) m r)
--
-- -- which would not stream, since it would have to accumulate the second -- stream (of bs). Of course, Data.List unzip -- doesn't stream either. -- -- This unzip does stream, though of course you can spoil this -- by using e.g. toList: -- -- 
--   >>> let xs = Prelude.map (x -> (x, Prelude.show x)) [1..5 :: Int]
--   
--   >>> S.toList $ S.toList $ S.unzip (S.each' xs)
--   ["1","2","3","4","5"] :> ([1,2,3,4,5] :> ())
--   
--   >>> Prelude.unzip xs
--   ([1,2,3,4,5],["1","2","3","4","5"])
--
-- -- Note the difference of order in the results. It may be of some use to -- think why. The first application of toList was applied to a -- stream of integers: -- -- 
--   >>> :t S.unzip $ S.each' xs
--   S.unzip $ S.each' xs :: Control.Monad m => Stream (Of Int) (Stream (Of String) m) ()
--
-- -- Like any fold, toList takes no notice of the monad of effects. -- -- 
--   toList :: Control.Monad m => Stream (Of a) m r %1-> m (Of [a] r)
--
-- -- In the case at hand (since I am in ghci) m = Stream (Of -- String) IO. So when I apply toList, I exhaust that stream -- of integers, folding it into a list: -- -- 
--   >>> :t S.toList $ S.unzip $ S.each' xs
--   S.toList $ S.unzip $ S.each' xs
--    :: Control.Monad m => Stream (Of String) m (Of [Int] ())
--
-- -- When I apply toList to this, I reduce everything to an -- ordinary action in IO, and return a list of strings: -- -- 
--   >>> S.toList $ S.toList $ S.unzip (S.each' xs)
--   ["1","2","3","4","5"] :> ([1,2,3,4,5] :> ())
--
-- -- unzip can be considered a special case of either -- unzips or expand: -- -- 
--   unzip = unzips . maps (((a,b) :> x) -> Compose (a :> b :> x))
--   unzip = expand $ p ((a,b) :> abs) -> b :> p (a :> abs)
--
unzip :: Monad m => Stream (Of (a, b)) m r %1 -> Stream (Of a) (Stream (Of b) m) r -- | The remainder of zipping two streams type ZipResidual a b m r1 r2 = Either3 (r1, r2) (r1, Stream (Of b) m r2) (Stream (Of a) m r1, r2) -- | The (liberal) remainder of zipping three streams. This has the -- downside that the possibility of three remainders is allowed, though -- it will never occur. type ZipResidual3 a b c m r1 r2 r3 = (Either r1 (Stream (Of a) m r1), Either r2 (Stream (Of b) m r2), Either r3 (Stream (Of c) m r3)) -- | zip zips two streams exhausing the remainder of the longer -- stream and consuming its effects. zip :: Monad m => Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of (a, b)) m (r1, r2) -- | zipR zips two streams keeping the remainder if there is one. zipR :: Monad m => Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of (a, b)) m (ZipResidual a b m r1 r2) zipWith :: Monad m => (a -> b -> c) -> Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of c) m (r1, r2) -- | zipWithR zips two streams applying a function along the way, -- keeping the remainder of zipping if there is one. Note. If two streams -- have the same length, but one needs to perform some effects to obtain -- the end-of-stream result, that stream is treated as a residual. zipWithR :: Monad m => (a -> b -> c) -> Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of c) m (ZipResidual a b m r1 r2) -- | Like zipR but with three streams. zip3 :: Monad m => Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of c) m r3 %1 -> Stream (Of (a, b, c)) m (r1, r2, r3) -- | Like zipR but with three streams. zip3R :: Monad m => Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of c) m r3 %1 -> Stream (Of (a, b, c)) m (ZipResidual3 a b c m r1 r2 r3) -- | Like zipWith but with three streams zipWith3 :: Monad m => (a -> b -> c -> d) -> Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of c) m r3 %1 -> Stream (Of d) m (r1, r2, r3) -- | Like zipWithR but with three streams. zipWith3R :: Monad m => (a -> b -> c -> d) -> Stream (Of a) m r1 %1 -> Stream (Of b) m r2 %1 -> Stream (Of c) m r3 %1 -> Stream (Of d) m (ZipResidual3 a b c m r1 r2 r3) data Either3 a b c [Left3] :: a -> Either3 a b c [Middle3] :: b -> Either3 a b c [Right3] :: c -> Either3 a b c -- | Merge two streams of elements ordered with their Ord instance. -- -- The return values of both streams are returned. -- -- 
--   >>> S.print $ merge (each [1,3,5]) (each [2,4])
--   1
--   2
--   3
--   4
--   5
--   ((), ())
--
merge :: (Monad m, Ord a) => Stream (Of a) m r %1 -> Stream (Of a) m s %1 -> Stream (Of a) m (r, s) -- | Merge two streams, ordering them by applying the given function to -- each element before comparing. -- -- The return values of both streams are returned. mergeOn :: (Monad m, Ord b) => (a -> b) -> Stream (Of a) m r %1 -> Stream (Of a) m s %1 -> Stream (Of a) m (r, s) -- | Merge two streams, ordering the elements using the given comparison -- function. -- -- The return values of both streams are returned. mergeBy :: forall m a r s. Monad m => (a -> a -> Ordering) -> Stream (Of a) m r %1 -> Stream (Of a) m s %1 -> Stream (Of a) m (r, s) -- | The standard way of inspecting the first item in a stream of elements, -- if the stream is still 'running'. The Right case contains a -- Haskell pair, where the more general inspect would return a -- left-strict pair. There is no reason to prefer inspect since, -- if the Right case is exposed, the first element in the pair -- will have been evaluated to whnf. -- -- 
--   next    :: Control.Monad m => Stream (Of a) m r %1-> m (Either r    (a, Stream (Of a) m r))
--   inspect :: Control.Monad m => Stream (Of a) m r %1-> m (Either r (Of a (Stream (Of a) m r)))
--
next :: forall a m r. Monad m => Stream (Of a) m r %1 -> m (Either r (Ur a, Stream (Of a) m r)) -- | Inspect the first item in a stream of elements, without a return -- value. uncons :: forall a m r. (Consumable r, Monad m) => Stream (Of a) m r %1 -> m (Maybe (a, Stream (Of a) m r)) -- | Split a succession of layers after some number, returning a streaming -- or effectful pair. This function is the same as the splitsAt -- exported by the Streaming module, but since this module is -- imported qualified, it can usurp a Prelude name. It specializes to: -- -- 
--   splitAt :: Control.Monad m => Int -> Stream (Of a) m r %1-> Stream (Of a) m (Stream (Of a) m r)
--
splitAt :: forall f m r. (Monad m, Functor f) => Int -> Stream f m r %1 -> Stream f m (Stream f m r) -- | Split a stream of elements wherever a given element arises. The action -- is like that of words. -- -- 
--   >>> S.stdoutLn $ mapped S.toList $ S.split ' ' $ each' "hello world  "
--   hello
--   world
--
split :: forall a m r. (Eq a, Monad m) => a -> Stream (Of a) m r %1 -> Stream (Stream (Of a) m) m r -- | Break during periods where the predicate is not satisfied, grouping -- the periods when it is. -- -- 
--   >>> S.print $ mapped S.toList $ S.breaks not $ S.each' [False,True,True,False,True,True,False]
--   [True,True]
--   [True,True]
--   >>> S.print $ mapped S.toList $ S.breaks id $ S.each' [False,True,True,False,True,True,False]
--   [False]
--   [False]
--   [False]
--
breaks :: forall a m r. Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> Stream (Stream (Of a) m) m r -- | Break a sequence upon meeting an element that falls under a predicate, -- keeping it and the rest of the stream as the return value. -- -- 
--   >>> rest <- S.print $ S.break even $ each' [1,1,2,3]
--   1
--   1
--   >>> S.print rest
--   2
--   3
--
break :: forall a m r. Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> Stream (Of a) m (Stream (Of a) m r) -- | Yield elements, using a fold to maintain state, until the accumulated -- value satifies the supplied predicate. The fold will then be -- short-circuited and the element that breaks it will be put after the -- break. This function is easiest to use with purely -- -- 
--   >>> rest each' [1..10] & L.purely S.breakWhen L.sum (10) & S.print
--   1
--   2
--   3
--   4
--   >>> S.print rest
--   5
--   6
--   7
--   8
--   9
--   10
--
breakWhen :: forall m a x b r. Monad m => (x -> a -> x) -> x -> (x -> b) -> (b -> Bool) -> Stream (Of a) m r %1 -> Stream (Of a) m (Stream (Of a) m r) -- | Breaks on the first element to satisfy the predicate breakWhen' :: Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> Stream (Of a) m (Stream (Of a) m r) -- | Stream elements until one fails the condition, return the rest. span :: Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> Stream (Of a) m (Stream (Of a) m r) -- | Group successive equal items together -- -- 
--   >>> S.toList $ mapped S.toList $ S.group $ each' "baaaaad"
--   ["b","aaaaa","d"] :> ()
--
-- -- 
--   >>> S.toList $ concats $ maps (S.drained . S.splitAt 1) $ S.group $ each' "baaaaaaad"
--   "bad" :> ()
--
group :: (Monad m, Eq a) => Stream (Of a) m r %1 -> Stream (Stream (Of a) m) m r -- | Group elements of a stream in accordance with the supplied comparison. -- -- 
--   >>> S.print $ mapped S.toList $ S.groupBy (>=) $ each' [1,2,3,1,2,3,4,3,2,4,5,6,7,6,5]
--   [1]
--   [2]
--   [3,1,2,3]
--   [4,3,2,4]
--   [5]
--   [6]
--   [7,6,5]
--
groupBy :: forall a m r. Monad m => (a -> a -> Bool) -> Stream (Of a) m r %1 -> Stream (Stream (Of a) m) m r distinguish :: (a -> Bool) -> Of a r -> Sum (Of a) (Of a) r -- | Swap the order of functors in a sum of functors. -- -- 
--   >>> S.toList $ S.print $ separate $ maps S.switch $ maps (S.distinguish (==a)) $ S.each' "banana"
--   a
--   a
--   a
--   "bnn" :> ()
--   >>> S.toList $ S.print $ separate $ maps (S.distinguish (==a)) $ S.each' "banana"
--   b
--   n
--   n
--   "aaa" :> ()
--
switch :: Sum f g r -> Sum g f r -- | Given a stream on a sum of functors, make it a stream on the left -- functor, with the streaming on the other functor as the governing -- monad. This is useful for acting on one or the other functor with a -- fold, leaving the other material for another treatment. It generalizes -- partitionEithers, but actually streams properly. -- -- 
--   >>> let odd_even = S.maps (S.distinguish even) $ S.each' [1..10::Int]
--   >>> :t separate odd_even
--   separate odd_even
--    :: Monad m => Stream (Of Int) (Stream (Of Int) m) ()
--
-- -- Now, for example, it is convenient to fold on the left and right -- values separately: -- -- 
--   >>> S.toList $ S.toList $ separate odd_even
--   [2,4,6,8,10] :> ([1,3,5,7,9] :> ())
--
-- -- Or we can write them to separate files or whatever. -- -- Of course, in the special case of Stream (Of a) m r, we can -- achieve the above effects more simply by using copy -- -- 
--   >>> S.toList . S.filter even $ S.toList . S.filter odd $ S.copy $ each' [1..10::Int]
--   [2,4,6,8,10] :> ([1,3,5,7,9] :> ())
--
-- -- But separate and unseparate are functor-general. separate :: forall m f g r. (Monad m, Functor f, Functor g) => Stream (Sum f g) m r -> Stream f (Stream g m) r unseparate :: (Monad m, Functor f, Functor g) => Stream f (Stream g m) r -> Stream (Sum f g) m r eitherToSum :: Of (Either a b) r -> Sum (Of a) (Of b) r sumToEither :: Sum (Of a) (Of b) r -> Of (Either a b) r sumToCompose :: Sum f f r -> Compose (Of Bool) f r composeToSum :: Compose (Of Bool) f r -> Sum f f r -- | Separate left and right values in distinct streams. (separate -- is a more powerful, functor-general, equivalent using Sum in -- place of Either). -- -- 
--   partitionEithers = separate . maps S.eitherToSum
--   lefts  = hoist S.effects . partitionEithers
--   rights = S.effects . partitionEithers
--   rights = S.concat
--
partitionEithers :: Monad m => Stream (Of (Either a b)) m r %1 -> Stream (Of a) (Stream (Of b) m) r -- | 
--   filter p = hoist effects (partition p)
--
partition :: forall a m r. Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> Stream (Of a) (Stream (Of a) m) r -- | The catMaybes function takes a Stream of Maybes -- and returns a Stream of all of the Just values. -- concat has the same behavior, but is more general; it works -- for any foldable container type. catMaybes :: Monad m => Stream (Of (Maybe a)) m r %1 -> Stream (Of a) m r -- | The mapMaybe function is a version of map which can -- throw out elements. In particular, the functional argument returns -- something of type Maybe b. If this is Nothing, -- no element is added on to the result Stream. If it is -- Just b, then b is included in the result -- Stream. mapMaybe :: forall a b m r. Monad m => (a -> Maybe b) -> Stream (Of a) m r %1 -> Stream (Of b) m r -- | Map monadically over a stream, producing a new stream only containing -- the Just values. mapMaybeM :: forall a m b r. Monad m => (a -> m (Maybe (Ur b))) -> Stream (Of a) m r %1 -> Stream (Of b) m r -- | Change the effects of one monad to another with a transformation. This -- is one of the fundamental transformations on streams. Compare with -- maps: -- -- 
--   maps  :: (Control.Monad m, Control.Functor f) => (forall x. f x %1-> g x) -> Stream f m r %1-> Stream g m r
--   hoist :: (Control.Monad m, Control.Functor f) => (forall a. m a %1-> n a) -> Stream f m r %1-> Stream f n r
--
hoist :: forall f m n r. (Monad m, Functor f) => (forall a. m a %1 -> n a) -> Stream f m r %1 -> Stream f n r -- | Standard map on the elements of a stream. -- -- 
--   >>> S.stdoutLn $ S.map reverse $ each' (words "alpha beta")
--   ahpla
--   ateb
--
map :: Monad m => (a -> b) -> Stream (Of a) m r %1 -> Stream (Of b) m r -- | Replace each element of a stream with the result of a monadic action -- -- 
--   >>> S.print $ S.mapM readIORef $ S.chain (ior -> modifyIORef ior (*100)) $ S.mapM newIORef $ each' [1..6]
--   100
--   200
--   300
--   400
--   500
--   600
--
-- -- See also chain for a variant of this which ignores the return -- value of the function and just uses the side effects. mapM :: Monad m => (a -> m (Ur b)) -> Stream (Of a) m r %1 -> Stream (Of b) m r -- | Map layers of one functor to another with a transformation. Compare -- hoist, which has a similar effect on the monadic parameter. -- -- 
--   maps id = id
--   maps f . maps g = maps (f . g)
--
maps :: forall f g m r. (Monad m, Functor f) => (forall x. f x %1 -> g x) -> Stream f m r %1 -> Stream g m r -- | Map layers of one functor to another with a transformation involving -- the base monad. -- -- This function is completely functor-general. It is often useful with -- the more concrete type -- -- 
--   mapped :: (forall x. Stream (Of a) IO x -> IO (Of b x)) -> Stream (Stream (Of a) IO) IO r -> Stream (Of b) IO r
--
-- -- to process groups which have been demarcated in an effectful, -- IO-based stream by grouping functions like group, -- split or breaks. Summary functions like fold, -- foldM, mconcat or toList are often used to define -- the transformation argument. For example: -- -- 
--   >>> S.toList_ $ S.mapped S.toList $ S.split c (S.each' "abcde")
--   ["ab","de"]
--
-- -- maps and mapped obey these rules: -- -- 
--   maps id              = id
--   mapped return        = id
--   maps f . maps g      = maps (f . g)
--   mapped f . mapped g  = mapped (f <=< g)
--   maps f . mapped g    = mapped (fmap f . g)
--   mapped f . maps g    = mapped (f <=< fmap g)
--
-- -- where f and g are Control.Monads -- -- maps is more fundamental than mapped, which is best -- understood as a convenience for effecting this frequent composition: -- -- 
--   mapped phi = decompose . maps (Compose . phi)
--
mapped :: forall f g m r. (Monad m, Functor f) => (forall x. f x %1 -> m (g x)) -> Stream f m r %1 -> Stream g m r -- | Map layers of one functor to another with a transformation. Compare -- hoist, which has a similar effect on the monadic parameter. -- -- 
--   mapsPost id = id
--   mapsPost f . mapsPost g = mapsPost (f . g)
--   mapsPost f = maps f
--
-- -- mapsPost is essentially the same as maps, but it -- imposes a Control.Functor constraint on its target functor -- rather than its source functor. It should be preferred if -- fmap is cheaper for the target functor than for the source -- functor. mapsPost :: forall m f g r. (Monad m, Functor g) => (forall x. f x %1 -> g x) -> Stream f m r %1 -> Stream g m r -- | Map layers of one functor to another with a transformation involving -- the base monad. mapsMPost is essentially the same as -- mapsM, but it imposes a Control.Functor constraint -- on its target functor rather than its source functor. It should be -- preferred if fmap is cheaper for the target functor than for -- the source functor. -- -- mapsPost is more fundamental than mapsMPost, which -- is best understood as a convenience for effecting this frequent -- composition: -- -- 
--   mapsMPost phi = decompose . mapsPost (Compose . phi)
--
-- -- The streaming prelude exports the same function under the better name -- mappedPost, which overlaps with the lens libraries. mapsMPost :: forall m f g r. (Monad m, Functor g) => (forall x. f x %1 -> m (g x)) -> Stream f m r %1 -> Stream g m r -- | A version of mapped that imposes a Control.Functor -- constraint on the target functor rather than the source functor. This -- version should be preferred if fmap on the target functor is -- cheaper. mappedPost :: forall m f g r. (Monad m, Functor g) => (forall x. f x %1 -> m (g x)) -> Stream f m r %1 -> Stream g m r -- | for replaces each element of a stream with an associated -- stream. Note that the associated stream may layer any control functor. for :: forall f m r a x. (Monad m, Functor f, Consumable x) => Stream (Of a) m r %1 -> (a -> Stream f m x) -> Stream f m r -- | Replace each element in a stream of individual Haskell values (a -- Stream (Of a) m r) with an associated functorial -- step. -- -- 
--   for str f  = concats (with str f)
--   with str f = for str (yields . f)
--   with str f = maps (\(a:>r) -> r <$ f a) str
--   with = flip subst
--   subst = flip with
--
-- -- 
--   >>> with (each' [1..3]) (yield . Prelude.show) & intercalates (yield "--") & S.stdoutLn
--   1
--   --
--   2
--   --
--   3
--
with :: forall f m r a x. (Monad m, Functor f, Consumable x) => Stream (Of a) m r %1 -> (a -> f x) -> Stream f m r -- | Replace each element in a stream of individual values with a -- functorial layer of any sort. subst = flip with and is more -- convenient in a sequence of compositions that transform a stream. -- -- 
--   with = flip subst
--   for str f = concats $ subst f str
--   subst f = maps (\(a:>r) -> r <$ f a)
--   S.concat = concats . subst each
--
subst :: (Monad m, Functor f, Consumable x) => (a -> f x) -> Stream (Of a) m r %1 -> Stream f m r -- | Duplicate the content of a stream, so that it can be acted on twice in -- different ways, but without breaking streaming. Thus, with each' -- [1,2] I might do: -- -- 
--   >>> S.print $ each' ["one","two"]
--   "one"
--   "two"
--   >>> S.stdoutLn $ each' ["one","two"]
--   one
--   two
--
-- -- With copy, I can do these simultaneously: -- -- 
--   >>> S.print $ S.stdoutLn $ S.copy $ each' ["one","two"]
--   "one"
--   one
--   "two"
--   two
--
-- -- copy should be understood together with effects and is -- subject to the rules -- -- 
--   S.effects . S.copy       = id
--   hoist S.effects . S.copy = id
--
-- -- The similar operations in Streaming obey the same rules. -- -- Where the actions you are contemplating are each simple folds over the -- elements, or a selection of elements, then the coupling of the folds -- is often more straightforwardly effected with Foldl, e.g. -- -- 
--   >>> L.purely S.fold (liftA2 (,) L.sum L.product) $ each' 1..10 :> ()
--
-- -- rather than -- -- 
--   >>> S.sum $ S.product . S.copy $ each' [1..10]
--   55 :> (3628800 :> ())
--
-- -- A Control.Foldl fold can be altered to act on a selection of -- elements by using handles on an appropriate lens. Some such -- manipulations are simpler and more List-like, using -- copy: -- -- 
--   >>> L.purely S.fold (liftA2 (,) (L.handles (L.filtered odd) L.sum) (L.handles (L.filtered even) L.product)) $ each' 1..10 :> ()
--
-- -- becomes -- -- 
--   >>> S.sum $ S.filter odd $ S.product $ S.filter even $ S.copy' $ each' [1..10]
--   25 :> (3840 :> ())
--
-- -- or using store -- -- 
--   >>> S.sum $ S.filter odd $ S.store (S.product . S.filter even) $ each' [1..10]
--   25 :> (3840 :> ())
--
-- -- But anything that fold of a Stream (Of a) m r into e.g. an -- m (Of b r) that has a constraint on m that is -- carried over into Stream f m - e.g. Control.Monad, -- Control.Functor, etc. can be used on the stream. Thus, I can -- fold over different groupings of the original stream: -- -- 
--   >>>  (S.toList . mapped S.toList . chunksOf 5) $  (S.toList . mapped S.toList . chunksOf 3) $ S.copy $ each' [1..10]
--   [[1,2,3,4,5],[6,7,8,9,10]] :> ([[1,2,3],[4,5,6],[7,8,9],[10]] :> ())
--
-- -- The procedure can be iterated as one pleases, as one can see from this -- (otherwise unadvisable!) example: -- -- 
--   >>>  (S.toList . mapped S.toList . chunksOf 4) $ (S.toList . mapped S.toList . chunksOf 3) $ S.copy $ (S.toList . mapped S.toList . chunksOf 2) $ S.copy $ each' [1..12]
--   [[1,2,3,4],[5,6,7,8],[9,10,11,12]] :> ([[1,2,3],[4,5,6],[7,8,9],[10,11,12]] :> ([[1,2],[3,4],[5,6],[7,8],[9,10],[11,12]] :> ()))
--
-- -- copy can be considered a special case of expand: -- -- 
--   copy = expand $ p (a :> as) -> a :> p (a :> as)
--
-- -- If Of were an instance of Comonad, then one could write -- -- 
--   copy = expand extend
--
copy :: forall a m r. Monad m => Stream (Of a) m r %1 -> Stream (Of a) (Stream (Of a) m) r -- | An alias for copy. duplicate :: forall a m r. Monad m => Stream (Of a) m r %1 -> Stream (Of a) (Stream (Of a) m) r -- | Store the result of any suitable fold over a stream, keeping the -- stream for further manipulation. store f = f . copy : -- -- 
--   >>> S.print $ S.store S.product $ each' [1..4]
--   1
--   2
--   3
--   4
--   24 :> ()
--
-- -- 
--   >>> S.print $ S.store S.sum $ S.store S.product $ each' [1..4]
--   1
--   2
--   3
--   4
--   10 :> (24 :> ())
--
-- -- Here the sum (10) and the product (24) have been 'stored' for use when -- finally we have traversed the stream with print . Needless to -- say, a second pass is excluded conceptually, so the folds -- that you apply successively with store are performed -- simultaneously, and in constant memory -- as they would be if, say, -- you linked them together with Control.Fold: -- -- 
--   >>> L.impurely S.foldM (liftA3 (a b c -> (b, c)) (L.sink Prelude.print) (L.generalize L.sum) (L.generalize L.product)) $ each' [1..4]
--   1
--   2
--   3
--   4
--   (10,24) :> ()
--
-- -- Fusing folds after the fashion of Control.Foldl will -- generally be a bit faster than the corresponding succession of uses of -- store, but by constant factor that will be completely dwarfed -- when any IO is at issue. -- -- But store / copy is much more powerful, as you -- can see by reflecting on uses like this: -- -- 
--   >>> S.sum $ S.store (S.sum . mapped S.product . chunksOf 2) $ S.store (S.product . mapped S.sum . chunksOf 2) $ each' [1..6]
--   21 :> (44 :> (231 :> ()))
--
-- -- It will be clear that this cannot be reproduced with any combination -- of lenses, Control.Fold folds, or the like. (See also the -- discussion of copy.) -- -- It would conceivably be clearer to import a series of specializations -- of store. It is intended to be used at types like this: -- -- 
--   storeM ::  (forall s m . Control.Monad m => Stream (Of a) m s %1-> m (Of b s))
--           -> (Control.Monad n => Stream (Of a) n r %1-> Stream (Of a) n (Of b r))
--   storeM = store
--
-- -- It is clear from this type that we are just using the general -- instance: -- -- 
--   instance (Control.Functor f, Control.Monad m)   => Control.Monad (Stream f m)
--
-- -- We thus can't be touching the elements of the stream, or the final -- return value. It is the same with other constraints that Stream -- (Of a) inherits from the underlying monad. Thus I can -- independently filter and write to one file, but nub and write to -- another, or interact with a database and a logfile and the like: -- -- 
--   >>> (S.writeFile "hello2.txt" . S.nubOrd) $ store (S.writeFile "hello.txt" . S.filter (/= "world")) $ each' ["hello", "world", "goodbye", "world"]
--   >>> :! cat hello.txt
--   hello
--   goodbye
--   >>> :! cat hello2.txt
--   hello
--   world
--   goodbye
--
store :: Monad m => (Stream (Of a) (Stream (Of a) m) r %1 -> t) -> Stream (Of a) m r %1 -> t -- | Apply an action to all values, re-yielding each. The return value -- (y) of the function is ignored. -- -- 
--   >>> S.product $ S.chain Prelude.print $ S.each' [1..5]
--   1
--   2
--   3
--   4
--   5
--   120 :> ()
--
-- -- See also mapM for a variant of this which uses the return value -- of the function to transorm the values in the stream. chain :: forall a m r y. (Monad m, Consumable y) => (a -> m y) -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | Like the sequence but streaming. The result type is a stream of -- a's, but is not accumulated; the effects of the elements of the -- original stream are interleaved in the resulting stream. Compare: -- -- 
--   sequence :: Monad m =>         [m a]                 ->  m [a]
--   sequence :: Control.Monad m => Stream (Of (m a)) m r %1-> Stream (Of a) m r
--
sequence :: forall a m r. Monad m => Stream (Of (m (Ur a))) m r %1 -> Stream (Of a) m r -- | Remove repeated elements from a Stream. nubOrd of course -- accumulates a Set of elements that have already been seen and -- should thus be used with care. nubOrd :: (Monad m, Ord a) => Stream (Of a) m r %1 -> Stream (Of a) m r -- | Use nubOrdOn to have a custom ordering function for your -- elements. nubOrdOn :: forall m a b r. (Monad m, Ord b) => (a -> b) -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | More efficient versions of above when working with Ints that -- use IntSet. nubInt :: Monad m => Stream (Of Int) m r %1 -> Stream (Of Int) m r nubIntOn :: forall m a r. Monad m => (a -> Int) -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | Skip elements of a stream that fail a predicate filter :: forall a m r. Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | Skip elements of a stream that fail a monadic test filterM :: forall a m r. Monad m => (a -> m Bool) -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | Intersperse given value between each element of the stream. -- -- 
--   >>> S.print $ S.intersperse 0 $ each [1,2,3]
--   1
--   0
--   2
--   0
--   3
--
intersperse :: forall a m r. Monad m => a -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | Ignore the first n elements of a stream, but carry out the actions -- -- 
--   >>> S.toList $ S.drop 2 $ S.replicateM 5 getLine
--   aEnter
--   bEnter
--   cEnter
--   dEnter
--   eEnter
--   ["c","d","e"] :> ()
--
-- -- Because it retains the final return value, drop n is a -- suitable argument for maps: -- -- 
--   >>> S.toList $ concats $ maps (S.drop 4) $ chunksOf 5 $ each [1..20]
--   [5,10,15,20] :> ()
--
drop :: forall a m r. (HasCallStack, Monad m) => Int -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | Ignore elements of a stream until a test succeeds, retaining the rest. -- -- 
--   >>> S.print $ S.dropWhile ((< 5) . length) S.stdinLn
--   oneEnter
--   twoEnter
--   threeEnter
--   "three"
--   fourEnter
--   "four"
--   ^CInterrupted.
--
dropWhile :: forall a m r. Monad m => (a -> Bool) -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | Strict left scan, streaming, e.g. successive partial results. The seed -- is yielded first, before any action of finding the next element is -- performed. -- -- 
--   >>> S.print $ S.scan (++) "" id $ each' (words "a b c d")
--   ""
--   "a"
--   "ab"
--   "abc"
--   "abcd"
--
-- -- scan is fitted for use with Control.Foldl, thus: -- -- 
--   >>> S.print $ L.purely S.scan L.list $ each' [3..5]
--   []
--   [3]
--   [3,4]
--   [3,4,5]
--
scan :: forall a x b m r. Monad m => (x -> a -> x) -> x -> (x -> b) -> Stream (Of a) m r %1 -> Stream (Of b) m r -- | Strict left scan, accepting a monadic function. It can be used with -- FoldMs from Control.Foldl using impurely. -- Here we yield a succession of vectors each recording -- -- 
--   >>> let v = L.impurely scanM L.vectorM $ each' [1..4::Int] :: Stream (Of (Vector Int)) IO ()
--   >>> S.print v
--   []
--   [1]
--   [1,2]
--   [1,2,3]
--   [1,2,3,4]
--
scanM :: forall a x b m r. Monad m => (x %1 -> a -> m (Ur x)) -> m (Ur x) -> (x %1 -> m (Ur b)) -> Stream (Of a) m r %1 -> Stream (Of b) m r -- | Label each element in a stream with a value accumulated according to a -- fold. -- -- 
--   >>> S.print $ S.scanned (*) 1 id $ S.each' 100,200,300
--   (200,20000)
--   (300,6000000)
--
-- -- 
--   >>> S.print $ L.purely S.scanned' L.product $ S.each 100,200,300
--   (200,20000)
--   (300,6000000)
--
scanned :: forall a x b m r. Monad m => (x -> a -> x) -> x -> (x -> b) -> Stream (Of a) m r %1 -> Stream (Of (a, b)) m r -- | Interpolate a delay of n seconds between yields. delay :: forall a r. Double -> Stream (Of a) IO r %1 -> Stream (Of a) IO r -- | Make a stream of strings into a stream of parsed values, skipping bad -- cases -- -- 
--   >>> S.sum_ $ S.read $ S.takeWhile (/= "total") S.stdinLn :: IO Int
--   1000Enter
--   2000Enter
--   totalEnter
--   3000
--
read :: (Monad m, Read a) => Stream (Of String) m r %1 -> Stream (Of a) m r show :: (Monad m, Show a) => Stream (Of a) m r %1 -> Stream (Of String) m r -- | The natural cons for a Stream (Of a). -- -- 
--   cons a stream = yield a Control.>> stream
--
-- -- Useful for interoperation: -- -- 
--   Data.Text.foldr S.cons (return ()) :: Text -> Stream (Of Char) m ()
--   Lazy.foldrChunks S.cons (return ()) :: Lazy.ByteString -> Stream (Of Strict.ByteString) m ()
--
-- -- and so on. cons :: Monad m => a -> Stream (Of a) m r %1 -> Stream (Of a) m r -- | slidingWindow accumulates the first n elements of a -- stream, update thereafter to form a sliding window of length -- n. It follows the behavior of the slidingWindow function in -- conduit-combinators. -- -- 
--   >>> S.print $ S.slidingWindow 4 $ S.each "123456"
--   fromList "1234"
--   fromList "2345"
--   fromList "3456"
--
slidingWindow :: forall a b m. Monad m => Int -> Stream (Of a) m b %1 -> Stream (Of (Seq a)) m b -- | Before evaluating the monadic action returning the next step in the -- Stream, wrapEffect extracts the value in a monadic -- computation m a and passes it to a computation a -> m -- y. wrapEffect :: (Monad m, Functor f, Consumable y) => m a -> (a %1 -> m y) -> Stream f m r %1 -> Stream f m r destroyExposed :: forall f m r b. (Functor f, Monad m) => Stream f m r %1 -> (f b %1 -> b) -> (m b %1 -> b) -> (r %1 -> b) -> b -- | A singleton stream -- -- 
--   >>> stdoutLn $ yield "hello"
--   hello
--
-- -- 
--   >>> S.sum $ do {yield 1; yield 2; yield 3}
--   6 :> ()
--
yield :: Monad m => a -> Stream (Of a) m () -- | Stream the elements of a pure, foldable container. -- -- 
--   >>> S.print $ each' [1..3]
--   1
--   2
--   3
--
each' :: Monad m => [a] -> Stream (Of a) m () -- | Build a Stream by unfolding steps starting from a seed. In -- particular note that S.unfoldr S.next = id. unfoldr :: Monad m => (s %1 -> m (Either r (Ur a, s))) -> s %1 -> Stream (Of a) m r fromHandle :: Handle %1 -> Stream (Of Text) RIO () -- | Read the lines of a file given the filename. readFile :: FilePath -> Stream (Of Text) RIO () -- | Repeat an element several times. replicate :: (HasCallStack, Monad m) => Int -> a -> Stream (Of a) m () -- | Repeat an action several times, streaming its results. -- -- 
--   >>> import qualified Unsafe.Linear as Unsafe
--   >>> import qualified Data.Time as Time
--   >>> let getCurrentTime = fromSystemIO (Unsafe.coerce Time.getCurrentTime)
--   >>> S.print $ S.replicateM 2 getCurrentTime
--   2015-08-18 00:57:36.124508 UTC
--   2015-08-18 00:57:36.124785 UTC
--
replicateM :: Monad m => Int -> m (Ur a) -> Stream (Of a) m () -- | Replicate a constant element and zip it with the finite stream which -- is the first argument. replicateZip :: Monad m => Stream (Of x) m r -> a -> Stream (Of (a, x)) m r untilRight :: forall m a r. Monad m => m (Either (Ur a) r) -> Stream (Of a) m r -- | stdinLnN n is a stream of n lines from standard -- input stdinLnN :: Int -> Stream (Of Text) IO () -- | Provides a stream of standard input and omits the first line that -- satisfies the predicate stdinLnUntil :: (Text -> Bool) -> Stream (Of Text) IO () -- | Provides a stream of standard input and omits the first line that -- satisfies the predicate, possibly requiring IO stdinLnUntilM :: (Text -> IO Bool) -> Stream (Of Text) IO () -- | Given a finite stream, provide a stream of lines of standard input -- zipped with that finite stream stdinLnZip :: Stream (Of x) IO r %1 -> Stream (Of (x, Text)) IO r readLnN :: Read a => Int -> Stream (Of a) IO () readLnUntil :: Read a => (a -> Bool) -> Stream (Of a) IO () readLnUntilM :: Read a => (a -> IO Bool) -> Stream (Of a) IO () readLnZip :: Read a => Stream (Of x) IO r %1 -> Stream (Of (x, a)) IO r -- | Iterate a pure function from a seed value, streaming the results -- forever. iterateN :: Monad m => Int -> (a -> a) -> a -> Stream (Of a) m () iterateZip :: Monad m => Stream (Of x) m r -> (a -> a) -> a -> Stream (Of (x, a)) m r -- | Iterate a monadic function from a seed value, streaming the results -- forever. iterateMN :: Monad m => Int -> (a -> m (Ur a)) -> m (Ur a) -> Stream (Of a) m () iterateMZip :: Monad m => Stream (Of x) m r %1 -> (a -> m (Ur a)) -> m (Ur a) -> Stream (Of (x, a)) m r -- | Cycle a stream a finite number of times cycleN :: (Monad m, Consumable r) => Int -> Stream (Of a) m r -> Stream (Of a) m r -- | cycleZip s1 s2 will cycle s2 just enough to zip with -- the given finite stream s1. Note that we consume all the -- effects of the remainder of the cycled stream s2. That is, we -- consume s2 the smallest natural number of times we need to -- zip. cycleZip :: (Monad m, Consumable s) => Stream (Of a) m r %1 -> Stream (Of b) m s -> Stream (Of (a, b)) m (r, s) -- | Like enumFromThenN but where the next element in the -- enumeration is just the successor succ n for a given enum -- n. enumFromN :: (Monad m, Enum e) => Int -> e -> Stream (Of e) m () -- | Like enumFromThenZip but where the next element in the -- enumeration is just the successor succ n for a given enum -- n. enumFromZip :: (Monad m, Enum e) => Stream (Of a) m r %1 -> e -> Stream (Of (a, e)) m r -- | An finite sequence of enumerable values at a fixed distance, -- determined by the first and second values. -- -- 
--   >>> S.print $ S.enumFromThenN 3 100 200
--   100
--   200
--   300
--
enumFromThenN :: (Monad m, Enum e) => Int -> e -> e -> Stream (Of e) m () -- | A finite sequence of enumerable values at a fixed distance determined -- by the first and second values. The length is limited by zipping with -- a given finite stream, i.e., the first argument. enumFromThenZip :: (Monad m, Enum e) => Stream (Of a) m r %1 -> e -> e -> Stream (Of (a, e)) m r module Streaming.Linear data Stream f m r [Step] :: !f (Stream f m r) -> Stream f m r [Effect] :: m (Stream f m r) -> Stream f m r [Return] :: r -> Stream f m r -- | A left-strict pair; the base functor for streams of individual -- elements. data Of a b [:>] :: !a -> b -> Of a b infixr 5 :> -- | yields is like lift for items in the streamed -- functor. It makes a singleton or one-layer succession. -- -- 
--   lift :: (Control.Monad m, Control.Functor f)    => m r %1-> Stream f m r
--   yields ::  (Control.Monad m, Control.Functor f) => f r %1-> Stream f m r
--
-- -- Viewed in another light, it is like a functor-general version of -- yield: -- -- 
--   S.yield a = yields (a :> ())
--
yields :: (Monad m, Functor f) => f r %1 -> Stream f m r -- | Wrap an effect that returns a stream -- -- 
--   effect = join . lift
--
effect :: (Monad m, Functor f) => m (Stream f m r) %1 -> Stream f m r -- | Wrap a new layer of a stream. So, e.g. -- -- 
--   S.cons :: Control.Monad m => a -> Stream (Of a) m r %1-> Stream (Of a) m r
--   S.cons a str = wrap (a :> str)
--
-- -- and, recursively: -- -- 
--   S.each' :: Control.Monad m =>  [a] -> Stream (Of a) m ()
--   S.each' = foldr (\a b -> wrap (a :> b)) (return ())
--
-- -- The two operations -- -- 
--   wrap :: (Control.Monad m, Control.Functor f) =>
--     f (Stream f m r) %1-> Stream f m r
--   effect :: (Control.Monad m, Control.Functor f) =>
--     m (Stream f m r) %1-> Stream f m r
--
-- -- are fundamental. We can define the parallel operations yields -- and lift in terms of them -- -- 
--   yields :: (Control.Monad m, Control.Functor f) => f r %1-> Stream f m r
--   yields = wrap . Control.fmap Control.return
--   lift ::  (Control.Monad m, Control.Functor f)  => m r %1-> Stream f m r
--   lift = effect . Control.fmap Control.return
--
wrap :: (Monad m, Functor f) => f (Stream f m r) %1 -> Stream f m r -- | Repeat a functorial layer, command or instruction a fixed number of -- times. replicates :: (HasCallStack, Monad m, Functor f) => Int -> f () -> Stream f m () -- | replicatesM n repeats an effect containing a functorial -- layer, command or instruction n times. replicatesM :: forall f m. (Monad m, Functor f) => Int -> m (f ()) -> Stream f m () unfold :: (Monad m, Functor f) => (s %1 -> m (Either r (f s))) -> s %1 -> Stream f m r untilJust :: forall f m r. (Monad m, Applicative f) => m (Maybe r) -> Stream f m r -- | Reflect a church-encoded stream; cp. GHC.Exts.build -- -- 
--   streamFold return_ effect_ step_ (streamBuild psi) = psi return_ effect_ step_
--
streamBuild :: (forall b. (r %1 -> b) -> (m b %1 -> b) -> (f b %1 -> b) -> b) -> Stream f m r delays :: forall f r. Applicative f => Double -> Stream f IO r -- | Map layers of one functor to another with a transformation. -- -- 
--   maps id = id
--   maps f . maps g = maps (f . g)
--
maps :: forall f g m r. (Monad m, Functor f) => (forall x. f x %1 -> g x) -> Stream f m r %1 -> Stream g m r -- | Map layers of one functor to another with a transformation. -- -- 
--   mapsPost id = id
--   mapsPost f . mapsPost g = mapsPost (f . g)
--   mapsPost f = maps f
--
-- -- mapsPost is essentially the same as maps, but it -- imposes a Control.Functor constraint on its target functor -- rather than its source functor. It should be preferred if -- Control.fmap is cheaper for the target functor than for the -- source functor. mapsPost :: forall m f g r. (Monad m, Functor g) => (forall x. f x %1 -> g x) -> Stream f m r %1 -> Stream g m r -- | Map layers of one functor to another with a transformation involving -- the base monad. maps is more fundamental than mapsM, -- which is best understood as a convenience for effecting this frequent -- composition: -- -- 
--   mapsM phi = decompose . maps (Compose . phi)
--
-- -- The streaming prelude exports the same function under the better name -- mapped, which overlaps with the lens libraries. mapsM :: forall f g m r. (Monad m, Functor f) => (forall x. f x %1 -> m (g x)) -> Stream f m r %1 -> Stream g m r -- | Map layers of one functor to another with a transformation involving -- the base monad. mapsMPost is essentially the same as -- mapsM, but it imposes a Control.Functor constraint on -- its target functor rather than its source functor. It should be -- preferred if Control.fmap is cheaper for the target functor -- than for the source functor. -- -- mapsPost is more fundamental than mapsMPost, which -- is best understood as a convenience for effecting this frequent -- composition: -- -- 
--   mapsMPost phi = decompose . mapsPost (Compose . phi)
--
-- -- The streaming prelude exports the same function under the better name -- mappedPost, which overlaps with the lens libraries. mapsMPost :: forall m f g r. (Monad m, Functor g) => (forall x. f x %1 -> m (g x)) -> Stream f m r %1 -> Stream g m r -- | Map layers of one functor to another with a transformation involving -- the base monad. This could be trivial, e.g. -- -- 
--   let noteBeginning text x = (fromSystemIO (System.putStrLn text)) Control.>> (Control.return x)
--
-- -- this is completely functor-general -- -- maps and mapped obey these rules: -- -- 
--   maps id              = id
--   mapped return        = id
--   maps f . maps g      = maps (f . g)
--   mapped f . mapped g  = mapped (f <=< g)
--   maps f . mapped g    = mapped (fmap f . g)
--   mapped f . maps g    = mapped (f <=< fmap g)
--
-- -- maps is more fundamental than mapped, which is best -- understood as a convenience for effecting this frequent composition: -- -- 
--   mapped phi = decompose . maps (Compose . phi)
--
mapped :: forall f g m r. (Monad m, Functor f) => (forall x. f x %1 -> m (g x)) -> Stream f m r %1 -> Stream g m r -- | A version of mapped that imposes a Control.Functor -- constraint on the target functor rather than the source functor. This -- version should be preferred if Control.fmap on the target -- functor is cheaper. mappedPost :: forall m f g r. (Monad m, Functor g) => (forall x. f x %1 -> m (g x)) -> Stream f m r %1 -> Stream g m r -- | A less-efficient version of hoist that works properly even -- when its argument is not a monad morphism. hoistUnexposed :: forall f m n r. (Monad m, Functor f) => (forall a. m a %1 -> n a) -> Stream f m r %1 -> Stream f n r -- | Group layers in an alternating stream into adjoining sub-streams of -- one type or another. groups :: forall f g m r. (Monad m, Functor f, Functor g) => Stream (Sum f g) m r %1 -> Stream (Sum (Stream f m) (Stream g m)) m r -- | Inspect the first stage of a freely layered sequence. Compare -- Pipes.next and the replica Streaming.Prelude.next. -- This is the uncons for the general unfold. -- -- 
--   unfold inspect = id
--   Streaming.Prelude.unfoldr StreamingPrelude.next = id
--
inspect :: forall f m r. Monad m => Stream f m r %1 -> m (Either r (f (Stream f m r))) -- | Split a succession of layers after some number, returning a streaming -- or effectful pair. -- -- >>> rest <- S.print $ S.splitAt 1 $ each' [1..3] 1 -- >>> S.print rest 2 3 -- -- 
--   splitAt 0 = return
--   (\stream -> splitAt n stream >>= splitAt m) = splitAt (m+n)
--
-- -- Thus, e.g. -- -- >>> rest S.print $ (s - splitsAt 2 s >>= -- splitsAt 2) each' [1..5] 1 2 3 4 >>> S.print rest 5 splitsAt :: forall f m r. (HasCallStack, Monad m, Functor f) => Int -> Stream f m r %1 -> Stream f m (Stream f m r) -- | Break a stream into substreams each with n functorial layers. -- -- >>> S.print $ mapped S.sum $ chunksOf 2 $ each' [1,1,1,1,1] 2 -- 2 1 chunksOf :: forall f m r. (HasCallStack, Monad m, Functor f) => Int -> Stream f m r %1 -> Stream (Stream f m) m r -- | Dissolves the segmentation into layers of Stream f m layers. concats :: forall f m r. (Monad m, Functor f) => Stream (Stream f m) m r %1 -> Stream f m r -- | Interpolate a layer at each segment. This specializes to e.g. -- -- 
--   intercalates :: Stream f m () -> Stream (Stream f m) m r %1-> Stream f m r
--
intercalates :: forall t m r x. (Monad m, Monad (t m), MonadTrans t, Consumable x) => t m x -> Stream (t m) m r %1 -> t m r unzips :: forall f g m r. (Monad m, Functor f, Functor g) => Stream (Compose f g) m r %1 -> Stream f (Stream g m) r -- | Given a stream on a sum of functors, make it a stream on the left -- functor, with the streaming on the other functor as the governing -- monad. This is useful for acting on one or the other functor with a -- fold, leaving the other material for another treatment. It generalizes -- partitionEithers, but actually streams properly. -- -- >>> let odd_even = S.maps (S.distinguish even) $ S.each' -- [1..10::Int] >>> :t separate odd_even separate odd_even :: -- Monad m => Stream (Of Int) (Stream (Of Int) m) () -- -- Now, for example, it is convenient to fold on the left and right -- values separately: -- -- >>> S.toList $ S.toList $ separate odd_even [2,4,6,8,10] -- :> ([1,3,5,7,9] :> ()) -- -- Or we can write them to separate files or whatever: -- -- >>> S.writeFile "even.txt" . S.show $ S.writeFile "odd.txt" . -- S.show $ S.separate odd_even >>> :! cat even.txt 2 4 6 8 10 -- >>> :! cat odd.txt 1 3 5 7 9 -- -- Of course, in the special case of Stream (Of a) m r, we can -- achieve the above effects more simply by using copy -- -- >>> S.toList . S.filter even $ S.toList . S.filter odd $ -- S.copy $ each [1..10::Int] [2,4,6,8,10] :> ([1,3,5,7,9] :> ()) -- -- But separate and unseparate are functor-general. separate :: forall f g m r. (Monad m, Functor f, Functor g) => Stream (Sum f g) m r -> Stream f (Stream g m) r unseparate :: (Monad m, Functor f, Functor g) => Stream f (Stream g m) r -> Stream (Sum f g) m r -- | Rearrange a succession of layers of the form Compose m (f x). -- -- we could as well define decompose by mapsM: -- -- 
--   decompose = mapped getCompose
--
-- -- but mapped is best understood as: -- -- 
--   mapped phi = decompose . maps (Compose . phi)
--
-- -- since maps and hoist are the really fundamental -- operations that preserve the shape of the stream: -- -- 
--   maps  :: (Control.Monad m, Control.Functor f) => (forall x. f x %1-> g x) -> Stream f m r %1-> Stream g m r
--   hoist :: (Control.Monad m, Control.Functor f) => (forall a. m a %1-> n a) -> Stream f m r %1-> Stream f n r
--
decompose :: forall f m r. (Monad m, Functor f) => Stream (Compose m f) m r %1 -> Stream f m r -- | If Of had a Comonad instance, then we'd have -- -- 
--   copy = expand extend
--
-- -- See expandPost for a version that requires a -- Control.Functor g instance instead. expand :: forall f m r g h. (Monad m, Functor f) => (forall a b. (g a %1 -> b) -> f a %1 -> h b) -> Stream f m r %1 -> Stream g (Stream h m) r -- | If Of had a Comonad instance, then we'd have -- -- 
--   copy = expandPost extend
--
-- -- See expand for a version that requires a Control.Functor -- f instance instead. expandPost :: forall f m r g h. (Monad m, Functor g) => (forall a b. (g a %1 -> b) -> f a %1 -> h b) -> Stream f m r %1 -> Stream g (Stream h m) r -- | Map each layer to an effect, and run them all. mapsM_ :: (Functor f, Monad m) => (forall x. f x %1 -> m x) -> Stream f m r %1 -> m r -- | Run the effects in a stream that merely layers effects. run :: Monad m => Stream m m r %1 -> m r -- | streamFold reorders the arguments of destroy to be more -- akin to foldr It is more convenient to query in ghci to -- figure out what kind of 'algebra' you need to write. -- -- >>> :t streamFold Control.return Control.join (Control.Monad -- m, Control.Functor f) => (f (m a) %1-> m a) -> Stream f m a -- %1-> m a -- iterT -- -- >>> :t streamFold Control.return (Control.join . -- Control.lift) (Control.Monad m, Control.Monad (t m), Control.Functor -- f, Control.MonadTrans t) => (f (t m a) %1-> t m a) -> Stream -- f m a %1-> t m a -- iterTM -- -- >>> :t streamFold Control.return effect (Control.Monad m, -- Control.Functor f, Control.Functor g) => (f (Stream g m r) %1-> -- Stream g m r) -> Stream f m r %1-> Stream g m r -- -- >>> :t f -> streamFold Control.return effect (wrap . f) -- (Control.Monad m, Control.Functor f, Control.Functor g) => (f -- (Stream g m a) %1-> g (Stream g m a)) -> Stream f m a %1-> -- Stream g m a -- maps -- -- >>> :t f -> streamFold Control.return effect (effect . -- Control.fmap wrap . f) (Control.Monad m, Control.Functor f, -- Control.Functor g) => (f (Stream g m a) %1-> m (g (Stream g m -- a))) -> Stream f m a %1-> Stream g m a -- mapped -- -- 
--   streamFold done eff construct
--      = eff . iterT (Control.return . construct . Control.fmap eff) . Control.fmap done
--
streamFold :: (Functor f, Monad m) => (r %1 -> b) -> (m b %1 -> b) -> (f b %1 -> b) -> Stream f m r %1 -> b -- | Specialized fold following the usage of -- Control.Monad.Trans.Free -- -- 
--   iterTM alg = streamFold Control.return (Control.join . Control.lift)
--   iterTM alg = iterT alg . hoist Control.lift
--
iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) %1 -> t m a) -> Stream f m a %1 -> t m a -- | Specialized fold following the usage of -- Control.Monad.Trans.Free -- -- 
--   iterT alg = streamFold Control.return Control.join alg
--   iterT alg = runIdentityT . iterTM (IdentityT . alg . Control.fmap runIdentityT)
--
iterT :: (Functor f, Monad m) => (f (m a) %1 -> m a) -> Stream f m a %1 -> m a -- | Map a stream to its church encoding; compare Data.List.foldr. -- destroyExposed may be more efficient in some cases when -- applicable, but it is less safe. -- -- 
--   destroy s construct eff done
--     = eff .
--       iterT (Control.return . construct . Control.fmap eff) .
--       Control.fmap done $ s
--   
--
destroy :: forall f m r b. (Functor f, Monad m) => Stream f m r %1 -> (f b %1 -> b) -> (m b %1 -> b) -> (r %1 -> b) -> b -- | This module introduces primitives to safely allocate and -- discard system heap memory (not GC heap memory) for storing -- values explicitly. (Basically, a haskell program has a GC that -- at runtime, manages its own heap by freeing and allocating space from -- the system heap.) Values discarded explicitly don't need to be managed -- by the garbage collector (GC), which therefore has less work to do. -- Less work for the GC can sometimes mean more predictable request -- latencies in multi-threaded and distributed applications. -- -- This module is meant to be imported qualified. -- --

The Interface

-- -- Run a computation that uses heap memory by passing a continuation to -- withPool of type Pool %1-> Ur b. Allocate and free -- with alloc and deconstruct. Make as many or as few pools -- you need, by using the Dupable and Consumable -- instances of Pool. -- -- A toy example: -- -- 
--   >>> :set -XLinearTypes
--   
--   >>> import Prelude
--   
--   >>> import Data.Unrestricted.Linear
--   
--   >>> import qualified Foreign.Marshal.Pure as Manual
--   
--   >>> :{
--     nothingWith3 :: Pool %1-> Ur Int
--     nothingWith3 pool = move (Manual.deconstruct (Manual.alloc 3 pool))
--   :}
--
-- -- 
--   >>> unur (Manual.withPool nothingWith3)
--   3
--
-- --

What are Pools?

-- -- Pools are memory pools from which a user can safely allocate -- and use heap memory manually by passing withPool a -- continuation. An alternative design would have allowed passing -- continuations to allocation functions but this could break -- tail-recursion in certain cases. -- -- Pools play another role: resilience to exceptions. If an exception is -- raised, all the data in the pool is deallocated. -- -- Note that data from one pool can refer to data in another pool and -- vice versa. -- --

Large Examples

-- -- You can find example data structure implementations in -- Foreign.List and Foreign.Heap here. module Foreign.Marshal.Pure -- | Pools represent collections of values. A Pool can be -- consume-ed. This is a no-op: it does not deallocate the data in -- that pool. It cannot do so, because accessible values might still -- exist. Consuming a pool simply makes it impossible to add new data to -- the pool. data Pool -- | Given a linear computation that manages memory, run that computation. withPool :: (Pool %1 -> Ur b) %1 -> Ur b -- | 'Box a' is the abstract type of manually managed data. It can be used -- as part of data type definitions in order to store linked data -- structure off heap. See Foreign.List and -- Foreign.Pair in the examples directory of the source -- repository. data Box a -- | Store a value a on the system heap that is not managed by the -- GC. alloc :: forall a. Representable a => a %1 -> Pool %1 -> Box a -- | Retrieve the value stored on system heap memory. deconstruct :: Representable a => Box a %1 -> a -- | This abstract type class represents values natively known to have a -- GC-less implementation. Basically, these are sequences (represented as -- tuples) of base types. class KnownRepresentable a -- | Laws of Representable: -- -- class (KnownRepresentable (AsKnown a)) => Representable a where { type AsKnown a :: Type; } toKnown :: Representable a => a %1 -> AsKnown a ofKnown :: Representable a => AsKnown a %1 -> a toKnown :: (Representable a, MkRepresentable a b, AsKnown a ~ AsKnown b) => a %1 -> AsKnown a ofKnown :: (Representable a, MkRepresentable a b, AsKnown a ~ AsKnown b) => AsKnown a %1 -> a -- | This is an easier way to create an instance of Representable. -- It is a bit abusive to use a type class for this (after all, it almost -- never makes sense to use this as a constraint). But it works in -- practice. -- -- To use, define an instance of MkRepresentable myType -- intermediateType then declare the following instance: -- -- 
--   instance Representable myType where {type AsKnown = AsKnown intermediateType}
--
-- -- And the default instance mechanism will create the appropriate -- Representable instance. -- -- Laws of MkRepresentable: -- -- class Representable b => MkRepresentable a b | a -> b toRepr :: MkRepresentable a b => a %1 -> b ofRepr :: MkRepresentable a b => b %1 -> a -- | This module provides Bifunctor and related classes. -- --

Bifunctor

-- -- Use a bifunctor instance to map functions over data structures that -- have two type paramaters a and b and could be have a -- functor instance for either the as or bs. For -- instance, you might want to map a function on either the left or right -- element of a (Int, Bool): -- -- 
--   import Prelude.Linear
--   import Data.Bifunctor.Linear
--   
--   -- Map over the second element
--   negateRight :: (Int, Bool) %1-> (Int, Bool)
--   negateRight x = second not x
--
module Data.Bifunctor.Linear -- | The Bifunctor class -- --

Laws

-- -- If bimap is supplied, then bimap id id -- = id -- -- class Bifunctor p bimap :: Bifunctor p => (a %1 -> b) -> (c %1 -> d) -> (a `p` c) %1 -> b `p` d first :: Bifunctor p => (a %1 -> b) -> (a `p` c) %1 -> b `p` c second :: Bifunctor p => (b %1 -> c) -> (a `p` b) %1 -> a `p` c -- | A SymmetricMonoidal class -- -- This allows you to shuffle around a bifunctor nested in itself and -- swap the places of the two types held in the bifunctor. For instance, -- for tuples: -- -- -- --

Laws

-- -- class Bifunctor m => SymmetricMonoidal (m :: Type -> Type -> Type) (u :: Type) | m -> u, u -> m rassoc :: SymmetricMonoidal m u => ((a `m` b) `m` c) %1 -> a `m` (b `m` c) lassoc :: SymmetricMonoidal m u => (a `m` (b `m` c)) %1 -> (a `m` b) `m` c swap :: SymmetricMonoidal m u => (a `m` b) %1 -> b `m` a -- | This module provides profunctor classes and instances. -- -- Please import this module qualified. -- -- Some of the definitions in this module are heavily connected to and -- motivated by linear optics. Please see Control.Optics.Linear -- and other optics modules for motivations for the definitions provided -- here. -- --

Connections to Linear Optics

-- -- module Data.Profunctor.Linear -- | A Profunctor can be thought of as a computation that involves taking -- a(s) as input and returning b(s). These computations -- compose with (linear) functions. Profunctors generalize the function -- arrow ->. -- -- Hence, think of a value of type x arr y for -- profunctor arr to be something like a function from -- x to y. -- -- Laws: -- -- 
--   lmap id = id
--   lmap (f . g) = lmap f . lmap g
--   rmap id = id
--   rmap (f . g) = rmap f . rmap g
--
class Profunctor (arr :: Type -> Type -> Type) dimap :: Profunctor arr => (s %1 -> a) -> (b %1 -> t) -> (a `arr` b) -> s `arr` t lmap :: Profunctor arr => (s %1 -> a) -> (a `arr` t) -> s `arr` t rmap :: Profunctor arr => (b %1 -> t) -> (s `arr` b) -> s `arr` t -- | A (Monoidal m u arr) is a profunctor arr that can be -- sequenced with the bifunctor m. In rough terms, you can -- combine two function-like things to one function-like thing that holds -- both input and output types with the bifunctor m. class (SymmetricMonoidal m u, Profunctor arr) => Monoidal m u arr (***) :: Monoidal m u arr => (a `arr` b) -> (x `arr` y) -> (a `m` x) `arr` (b `m` y) unit :: Monoidal m u arr => u `arr` u infixr 3 *** -- | A (Strong m u arr) instance means that the function-like -- thing of type a arr b can be extended to pass along -- a value of type c as a constant via the bifunctor of type -- m. -- -- This typeclass is used primarily to generalize common patterns and -- instances that are defined when defining optics. The two uses below -- are used in defining lenses and prisms respectively in -- Control.Optics.Linear.Internal: -- -- If m is the tuple type constructor (,) then we can -- create a function-like thing of type (a,c) arr (b,c) -- passing along c as a constant. -- -- If m is Either then we can create a function-like -- thing of type Either a c arr Either b c that either -- does the original function or behaves like the constant function. class (SymmetricMonoidal m u, Profunctor arr) => Strong m u arr first :: Strong m u arr => (a `arr` b) -> (a `m` c) `arr` (b `m` c) second :: Strong m u arr => (b `arr` c) -> (a `m` b) `arr` (a `m` c) -- | A Wandering arr instance means that there is a -- wander function which is the traversable generalization of -- the classic lens function: -- -- 
--   forall f. Functor f => (a -> f b) -> (s -> f t)
--
-- -- in our notation: -- -- 
--   forall arr. (HasKleisliFunctor arr) => (a `arr` b) -> (s `arr` t)
--
-- -- wander specializes the Functor constraint to a -- control applicative: -- -- 
--   forall f. Applicative f => (a -> f b) -> (s -> f t)
--   forall arr. (HasKleisliApplicative arr) => (a `arr` b) -> (s `arr` t)
--
-- -- where HasKleisliFunctor or HasKleisliApplicative are -- some constraints which allow for the arr to be Kleisli -- f for control functors or applicatives f. class (Strong (,) () arr, Strong Either Void arr) => Wandering arr -- | Equivalently but less efficient in general: -- -- 
--   wander :: Data.Traversable f => a `arr` b -> f a `arr` f b
--
wander :: forall s t a b. Wandering arr => (forall f. Applicative f => (a %1 -> f b) -> s %1 -> f t) -> (a `arr` b) -> s `arr` t -- | An exchange is a pair of translation functions that encode an -- isomorphism; an Exchange a b s t is equivalent to a Iso a -- b s t. data Exchange a b s t Exchange :: (s %1 -> a) -> (b %1 -> t) -> Exchange a b s t -- | A market is a pair of constructor and deconstructor functions that -- encode a prism; a Market a b s t is equivalent to a Prism -- a b s t. data Market a b s t Market :: (b %1 -> t) -> (s %1 -> Either t a) -> Market a b s t runMarket :: Market a b s t %1 -> (b %1 -> t, s %1 -> Either t a) instance Data.Profunctor.Linear.Profunctor (Data.Profunctor.Linear.Market a b) instance Data.Profunctor.Linear.Strong Data.Either.Either Data.Void.Void (Data.Profunctor.Linear.Market a b) instance Data.Profunctor.Linear.Profunctor (Data.Profunctor.Linear.Exchange a b) instance Data.Profunctor.Linear.Wandering (FUN 'One) instance Data.Profunctor.Linear.Strong (,) () (FUN 'One) instance Data.Profunctor.Linear.Strong Data.Either.Either Data.Void.Void (FUN 'One) instance Data.Profunctor.Linear.Strong (,) () (->) instance Data.Profunctor.Linear.Strong Data.Either.Either Data.Void.Void (->) instance GHC.Base.Functor f => Data.Profunctor.Linear.Strong (,) () (Control.Arrow.Kleisli f) instance GHC.Base.Applicative f => Data.Profunctor.Linear.Strong Data.Either.Either Data.Void.Void (Control.Arrow.Kleisli f) instance Data.Profunctor.Linear.Monoidal (,) () (FUN 'One) instance Data.Profunctor.Linear.Monoidal Data.Either.Either Data.Void.Void (FUN 'One) instance Data.Profunctor.Linear.Monoidal (,) () (->) instance Data.Profunctor.Linear.Monoidal Data.Either.Either Data.Void.Void (->) instance GHC.Base.Applicative f => Data.Profunctor.Linear.Monoidal (,) () (Control.Arrow.Kleisli f) instance GHC.Base.Functor f => Data.Profunctor.Linear.Monoidal Data.Either.Either Data.Void.Void (Control.Arrow.Kleisli f) instance Data.Profunctor.Linear.Profunctor (FUN 'One) instance Data.Profunctor.Linear.Profunctor (->) instance GHC.Base.Functor f => Data.Profunctor.Linear.Profunctor (Control.Arrow.Kleisli f) -- | This module provides (linear) Kleisli and CoKleisli arrows -- -- This module is meant to be imported qualified, perhaps as below. -- -- 
--   import qualified Data.Profunctor.Kleisli as Linear
--
-- --

What are Kleisli arrows?

-- -- The basic idea is that a Kleisli arrow is like a function arrow and -- Kleisli m a b is similar to a function from a to -- b. Basically: -- -- 
--   type Kleisli m a b = a %1-> m b
--
-- --

Why make this definition?

-- -- It let's us view Kleisli m for a certain m as a -- certain kind of function arrow, give it instances, abstract over it an -- so on. -- -- For instance, if m is any functor, Kleisli m is a -- Profunctor. -- --

CoKleisli

-- -- A CoKleisli arrow is just one that represents a computation from a -- m a to an a via a linear arrow. (It's a Co-something -- because it reverses the order of the function arrows in the -- something.) module Data.Profunctor.Kleisli.Linear -- | Linear Kleisli arrows for the monad m. These arrows are still -- useful in the case where m is not a monad however, and some -- profunctorial properties still hold in this weaker setting. newtype Kleisli m a b Kleisli :: (a %1 -> m b) -> Kleisli m a b [runKleisli] :: Kleisli m a b -> a %1 -> m b -- | Linear co-Kleisli arrows for the comonad w. These arrows are -- still useful in the case where w is not a comonad however, -- and some profunctorial properties still hold in this weaker setting. -- However stronger requirements on f are needed for -- profunctorial strength, so we have fewer instances. newtype CoKleisli w a b CoKleisli :: (w a %1 -> b) -> CoKleisli w a b [runCoKleisli] :: CoKleisli w a b -> w a %1 -> b instance Data.Functor.Linear.Internal.Functor.Functor f => Data.Profunctor.Linear.Profunctor (Data.Profunctor.Kleisli.Linear.CoKleisli f) instance Data.Profunctor.Linear.Strong Data.Either.Either Data.Void.Void (Data.Profunctor.Kleisli.Linear.CoKleisli (Data.Functor.Const.Const x)) instance Data.Functor.Linear.Internal.Functor.Functor f => Data.Profunctor.Linear.Profunctor (Data.Profunctor.Kleisli.Linear.Kleisli f) instance Control.Functor.Linear.Internal.Class.Functor f => Data.Profunctor.Linear.Strong (,) () (Data.Profunctor.Kleisli.Linear.Kleisli f) instance Control.Functor.Linear.Internal.Class.Applicative f => Data.Profunctor.Linear.Strong Data.Either.Either Data.Void.Void (Data.Profunctor.Kleisli.Linear.Kleisli f) instance Data.Functor.Linear.Internal.Applicative.Applicative f => Data.Profunctor.Linear.Monoidal (,) () (Data.Profunctor.Kleisli.Linear.Kleisli f) instance Data.Functor.Linear.Internal.Functor.Functor f => Data.Profunctor.Linear.Monoidal Data.Either.Either Data.Void.Void (Data.Profunctor.Kleisli.Linear.Kleisli f) instance Control.Functor.Linear.Internal.Class.Applicative f => Data.Profunctor.Linear.Wandering (Data.Profunctor.Kleisli.Linear.Kleisli f) -- | This module provides linear traversals. -- -- Traversals provides a means of accessing several as organized -- in some structural way in an s, and a means of changing them -- to bs to create a t. In very ordinary language, it's -- like walking or traversing the data structure, going across cases and -- inside definitions. In more imaginative language, it's like selecting -- some specific as by looking at each constructor of a data -- definition and recursing on each non-basic type (where basic types are -- things like Int, Bool or Char). -- --

Example

-- -- 
--   {-# LANGUAGE LinearTypes #-}
--   {-# LANGUAGE NoImplicitPrelude #-}
--   {-# LANGUAGE RankNTypes #-}
--   {-# LANGUAGE GADTs #-}
--   
--   import Control.Optics.Linear.Internal
--   import qualified Control.Functor.Linear as Control
--   import Control.Functor.Linear (($), (*), pure)
--   import Prelude.Linear
--   
--   -- We can use a traversal to append a string only to the
--   -- human names in a classroom struct
--   appendToNames :: String -> Classroom %1-> Classroom
--   appendToNames s = over classroomNamesTrav (name -> name ++ s)
--   
--   data Classroom where
--     Classroom ::
--       { className :: String
--       , teacherName :: String
--       , classNum :: Int
--       , students :: [Student]
--       , textbooks :: [String]
--       } %1-> Classroom
--   
--   -- A Student is a name and a student id number
--   data Student = Student String Int
--   
--   classroomNamesTrav :: Traversal' Classroom String
--   classroomNamesTrav = traversal traverseClassStr where
--     traverseClassStr :: forall f. Control.Applicative f =>
--       (String %1-> f String) -> Classroom %1-> f Classroom
--     traverseClassStr onName (Classroom cname teachname x students texts) =
--       Classroom $
--       pure cname *
--       onName teachname *
--       pure x *
--       traverse' ((Student s i) -> Student $ onName s * pure i) students *
--       pure texts
--
module Control.Optics.Linear.Traversal type Traversal s t a b = Optic Wandering s t a b type Traversal' s a = Traversal s s a a (.>) :: Optic_ arr s t a b -> Optic_ arr a b x y -> Optic_ arr s t x y infixr 9 .> traversed :: Traversable t => Traversal (t a) (t b) a b over :: Optic_ (FUN 'One) s t a b -> (a %1 -> b) -> s %1 -> t overU :: Optic_ (->) s t a b -> (a -> b) -> s -> t traverseOf :: Optic_ (Kleisli f) s t a b -> (a %1 -> f b) -> s %1 -> f t traverseOfU :: Optic_ (Kleisli f) s t a b -> (a -> f b) -> s -> f t traversal :: (forall f. Applicative f => (a %1 -> f b) -> s %1 -> f t) -> Traversal s t a b -- | This module provides linear prisms. -- -- A Prism s t a b is equivalent to (s %1-> Either a t, b -- %1-> t) for some sum type s. In the -- non-polymorphic version, this is a (s %1-> Either a s, a -- %1-> s) which represents taking one case of a sum type and a -- way to build the sum-type given that one case. A prism is a traversal -- focusing on one branch or case that a sum type could be. -- --

Example

-- -- 
--   {-# LANGUAGE LinearTypes #-}
--   {-# LANGUAGE LambdaCase #-}
--   {-# LANGUAGE FlexibleContexts #-}
--   {-# LANGUAGE NoImplicitPrelude #-}
--   {-# LANGUAGE GADTs #-}
--   
--   import Control.Optics.Linear.Internal
--   import Prelude.Linear
--   import qualified Data.Functor.Linear as Data
--   
--   -- We can use a prism to do operations on one branch of a sum-type
--   -- (This is a bit of a toy example since we could use over for this.)
--   formatLicenceName :: PersonId %1-> PersonId
--   formatLicenceName personId =
--     Data.fmap modLisc (match pIdLiscPrism personId) & case
--       Left personId' -> personId'
--       Right lisc -> build pIdLiscPrism lisc
--     where
--       modLisc :: Licence %1-> Licence
--       modLisc (Licence nm x) = Licence (nm ++ "n") x
--   
--   data PersonId where
--     IdLicence :: Licence %1-> PersonId
--     SSN :: Int %1-> PersonId
--     BirthCertif :: String %1-> PersonId
--     -- And there could be many more constructors ...
--   
--   -- A Licence is a name and number
--   data Licence = Licence String Int
--   
--   pIdLiscPrism :: Prism' PersonId Licence
--   pIdLiscPrism = prism IdLicence decompose where
--     decompose :: PersonId %1-> Either PersonId Licence
--     decompose (IdLicence l) = Right l
--     decompose x = Left x
--
module Control.Optics.Linear.Prism type Prism s t a b = Optic (Strong Either Void) s t a b type Prism' s a = Prism s s a a (.>) :: Optic_ arr s t a b -> Optic_ arr a b x y -> Optic_ arr s t x y infixr 9 .> _Left :: Prism (Either a c) (Either b c) a b _Right :: Prism (Either c a) (Either c b) a b _Just :: Prism (Maybe a) (Maybe b) a b _Nothing :: Prism' (Maybe a) () match :: Optic_ (Market a b) s t a b -> s %1 -> Either t a build :: Optic_ (CoKleisli (Const b)) s t a b -> b %1 -> t withPrism :: Optic_ (Market a b) s t a b -> ((b %1 -> t) -> (s %1 -> Either t a) -> r) -> r prism :: (b %1 -> t) -> (s %1 -> Either t a) -> Prism s t a b -- | This module provides linear lenses. -- -- A Lens s t a b is equivalent to a (s %1-> (a,b %1-> -- t). It is a way to cut up an instance of a product type -- s into an a and a way to take a b to fill -- the place of the a in s which yields a t. -- When a=b and s=t, this type is much more intuitive: -- (s %1-> (a,a %1-> s)). This is a traversal on exactly -- one a in a s. -- --

Example

-- -- 
--   {-# LANGUAGE LinearTypes #-}
--   {-# LANGUAGE FlexibleContexts #-}
--   {-# LANGUAGE NoImplicitPrelude #-}
--   
--   import Control.Optics.Linear.Internal
--   import Prelude.Linear
--   
--   import Control.Optics.Linear.Internal
--   import Prelude.Linear
--   -- We can use a lens to, for instance, linearly modify a sub-piece in
--   -- a nested record
--   modPersonZip :: Person %1-> Person
--   modPersonZip = over (personLocL .> locZipL)  (x -> x + 1)
--   
--   -- A person has a name and location
--   data Person = Person String Location
--   
--   -- A location is a zip code and address
--   data Location = Location Int String
--   
--   personLocL :: Lens' Person Location
--   personLocL = lens ((Person s l) -> (l, l' -> Person s l'))
--   
--   locZipL :: Lens' Location Int
--   locZipL = lens ((Location i s) -> (i, i' -> Location i' s))
--
module Control.Optics.Linear.Lens type Lens s t a b = Optic (Strong (,) ()) s t a b type Lens' s a = Lens s s a a (.>) :: Optic_ arr s t a b -> Optic_ arr a b x y -> Optic_ arr s t x y infixr 9 .> _1 :: Lens (a, c) (b, c) a b _2 :: Lens (c, a) (c, b) a b get :: Optic_ (Kleisli (Const a)) s t a b -> s -> a set :: Optic_ (->) s t a b -> b -> s -> t gets :: Optic_ (Kleisli (Const r)) s t a b -> (a -> r) -> s -> r setSwap :: Optic_ (Kleisli (Compose (FUN 'One b) ((,) a))) s t a b -> s %1 -> b %1 -> (a, t) over :: Optic_ (FUN 'One) s t a b -> (a %1 -> b) -> s %1 -> t overU :: Optic_ (->) s t a b -> (a -> b) -> s -> t reifyLens :: Optic_ (Kleisli (Compose ((,) a) (FUN 'One b))) s t a b -> s %1 -> (a, b %1 -> t) withLens :: Optic_ (Kleisli (Compose ((,) a) (FUN 'One b))) s t a b -> (forall c. (s %1 -> (c, a)) -> ((c, b) %1 -> t) -> r) -> r lens :: (s %1 -> (a, b %1 -> t)) -> Lens s t a b -- | This module provides linear isomorphisms. -- -- An Iso a b s t is equivalent to a (s %1-> a, b %1-> -- t). In the simple case of an Iso' a s, this is -- equivalent to inverse functions (s %1-> a, a %1-> s). -- In the general case an Iso a b s t means if you have the -- isomorphisms (a %1-> b, b %1-> a) and (s %1-> t, -- t %1-> s), then you can form isomorphisms between s, -- t, a and b. -- --

Example

-- -- 
--   {-# LANGUAGE LinearTypes #-}
--   {-# LANGUAGE NoImplicitPrelude #-}
--   {-# LANGUAGE GADTs #-}
--   
--   import Control.Optics.Linear.Internal
--   import Prelude.Linear
--   import qualified Data.Functor.Linear as Data
--   
--   -- A toy example of operating over two isomorphic linear types
--   closureFmap :: (a %1-> b) -> ClosureEither x a %1-> ClosureEither x b
--   closureFmap f = over isoEithers (Data.fmap f)
--   
--   data ClosureEither a b where
--     CLeft :: x %1-> (x %1-> a) %1-> ClosureEither a b
--     CRight :: x %1-> (x %1-> b) %1-> ClosureEither a b
--   
--   isoEithers ::
--     Iso (ClosureEither a b) (ClosureEither a b') (Either a b) (Either a b')
--   isoEithers = iso fromClosure fromEither
--     where
--       fromEither :: Either a b %1-> ClosureEither a b
--       fromEither (Left a) = CLeft () (() -> a)
--       fromEither (Right b) = CRight () (() -> b)
--   
--       fromClosure :: ClosureEither a b %1-> Either a b
--       fromClosure (CLeft x f) = Left (f x)
--       fromClosure (CRight x f) = Right (f x)
--
module Control.Optics.Linear.Iso type Iso s t a b = Optic Profunctor s t a b type Iso' s a = Iso s s a a (.>) :: Optic_ arr s t a b -> Optic_ arr a b x y -> Optic_ arr s t x y infixr 9 .> swap :: SymmetricMonoidal m u => Iso (a `m` b) (c `m` d) (b `m` a) (d `m` c) assoc :: SymmetricMonoidal m u => Iso (a `m` (b `m` c)) (d `m` (e `m` f)) ((a `m` b) `m` c) ((d `m` e) `m` f) withIso :: Optic_ (Exchange a b) s t a b -> ((s %1 -> a) -> (b %1 -> t) -> r) -> r iso :: (s %1 -> a) -> (b %1 -> t) -> Iso s t a b -- | This module provides linear optics. -- -- Documentation for specific optics (lenses, prisms, traversals and -- isomorphisms) are provided in their respective modules. -- -- Here we just provide an overview. -- -- Some familiarity with optics is needed to understand linear optics. -- Please go through the (hopefully friendly!) background material -- section if you are unfamiliar with lenses, prisms, traversals or -- isomorphisms. -- --

Background Material

-- -- If you don't know anything about optics, we suggest looking at the -- resources below and playing with the lens package. -- -- -- --

Conceptualizing and using optics

-- --

What are linear optics?

-- -- Optics can be conceptualized as a first class object with which you -- can view and map functions over sub-structure(s) within a larger -- structure. -- -- Linear optics are optics where the "viewing" and "mapping" -- are done with linear functions (and any corresponding -- structures hold values linearly, i.e., with constructors that -- use linear arrows). -- -- In types: a (linear) optic of type Optic s t a b is a way of -- viewing the sub-structure(s) of type a in the structure of -- type s and mapping a function from an a to a -- b on those sub-structures in s which change an -- s to a t. The non-polymorphic version of the optic -- is specialized to the types Optic s s a a and is usually -- defined with a tick mark, e.g., the non-polymorphic Lens is -- Lens'. -- -- There are four basic optics: traversals, lenses, prisms and -- isomorphisms. -- --

Sub-typing diagram of optics

-- -- <math> <math> <math> <math> <math> -- -- In the diagram above, the arrows X --> Y mean any of the -- following equivalent things: -- -- -- --

A bird's eye view of the types

-- -- The types of linear optics are generalizations of the standard optic -- types from the lens package. -- -- These are the standard optic types: -- -- 
--   type Traversal s t a b =
--     forall f. Applicative f => (a -> f b) -> s -> f t
--   type Lens s t a b =
--     forall f. Functor f => (a -> f b) -> (s -> f t)
--   type Prism s t a b =
--     forall p f. (Choice p, Applicative f) => p a (f b) -> p s (f t)
--   type Iso s t a b =
--     forall p f. (Profunctor p, Functor f) => a `p` (f b) -> s `p` (f t)
--
-- -- These are (basically) the linear optic types: -- -- 
--   type Traversal a b s t =
--     forall arr.  Wandering arr => (a `arr` b) -> (s `arr` t)
--   type Lens a b s t =
--     forall arr. Strong (,) () arr => (a `arr` b) -> (s `arr` t)
--   type Prism a b s t =
--     forall arr. Strong Either Void arr => (a `arr` b) -> (s `arr` t)
--   type Iso a b s t =
--     forall arr. Profunctor arr => (a `arr` b) -> (s `arr` t)
--
-- -- Below is a table that lists the instances of the typeclasses which -- generalize the standard optics. -- -- Note that Kleisli arrows basically defined like so: -- -- 
--   type Kleisli f a b = a %1-> f b
--
-- -- Note: We abbreviate Control for Control.Functor.Linear. -- -- TODO: table -- -- Essentially: -- -- module Control.Optics.Linear newtype Optic_ arr s t a b Optical :: ((a `arr` b) -> s `arr` t) -> Optic_ arr s t a b type Optic c s t a b = forall arr. c arr => Optic_ arr s t a b module Control.Monad.IO.Class.Linear -- | Like MonadIO but allows to lift both linear and non-linear -- IO actions into a linear monad. class Monad m => MonadIO m liftIO :: MonadIO m => IO a %1 -> m a liftSystemIO :: MonadIO m => IO a -> m a liftSystemIOU :: MonadIO m => IO a -> m (Ur a) instance Control.Monad.IO.Class.Linear.MonadIO System.IO.Linear.IO -- | This module provides pull arrays. -- -- These are part of a larger framework for controlling when memory is -- allocated for an array. See Data.Array.Polarized. module Data.Array.Polarized.Pull -- | A pull array is an array from which it is easy to extract elements, -- and this can be done in any order. The linear consumption of a pull -- array means each element is consumed exactly once, but the length can -- be accessed freely. data Array a -- | fromFunction arrIndexer len constructs a pull array -- given a function arrIndexer that goes from an array index to -- array values and a specified length len. fromFunction :: (Int -> a) -> Int -> Array a -- | Convert a Vector to a pull array. fromVector :: Vector a %1 -> Array a -- | Creates a pull array of given size, filled with the given element. make :: a -> Int -> Array a -- | Produce a pull array of lenght 1 consisting of solely the given -- element. singleton :: a %1 -> Array a -- | This is a convenience function for alloc . transfer toVector :: Array a %1 -> Vector a -- | Convert a pull array into a list. asList :: Array a %1 -> [a] -- | zip [x1, ..., xn] [y1, ..., yn] = [(x1,y1), ..., (xn,yn)] -- Partial: `zip [x1,x2,...,xn] [y1,y2,...,yp]` is an error if -- n ≠ p. zip :: Array a %1 -> Array b %1 -> Array (a, b) -- | zipWith f [x1,x2,...,xn] [y1,y2,...,yn] = [f x1 y1, ..., f xn -- yn] Partial: `zipWith f [x1,x2,...,xn] [y1,y2,...,yp]` is -- an error if n ≠ p. zipWith :: (a %1 -> b %1 -> c) -> Array a %1 -> Array b %1 -> Array c -- | Concatenate two pull arrays. append :: Array a %1 -> Array a %1 -> Array a -- | A right-fold of a pull array. foldr :: (a %1 -> b %1 -> b) -> b %1 -> Array a %1 -> b -- | Fold a pull array using a monoid. foldMap :: Monoid m => (a %1 -> m) -> Array a %1 -> m -- | Extract the length of an array, and give back the original array. findLength :: Array a %1 -> (Int, Array a) -- | split n v = (vl, vr) such that vl has length -- n. -- -- split is total: if n is larger than the length of -- v, then vr is empty. split :: Int -> Array a %1 -> (Array a, Array a) -- | Reverse a pull array. reverse :: Array a %1 -> Array a -- | Index a pull array (without checking bounds) index :: Array a %1 -> Int -> (a, Array a) -- | This module provides an unlifted mutable array with a pure interface. -- Though the array itself is unlifted, it's elements are lifted types. -- This is made possible by using linear types to make sure array -- references are single threaded through reads and writes. -- -- Accessing out-of-bounds indices causes undefined behaviour. -- -- This module is meant to be imported qualified. module Data.Array.Mutable.Unlifted.Linear -- | A mutable array holding as data Array# a -- | Extract the underlying MutableArray#, consuming the -- Array# in process. unArray# :: (MutableArray# RealWorld a -> b) -> Array# a %1 -> Ur b -- | Allocate a mutable array of given size using a default value. -- -- The size should be non-negative. alloc :: Int -> a -> (Array# a %1 -> Ur b) %1 -> Ur b -- | Allocate a mutable array of given size using a default value, using -- another Array# as a uniqueness proof. -- -- The size should be non-negative. allocBeside :: Int -> a -> Array# b %1 -> (# Array# a, Array# b #) -- | Consume an Array#. -- -- Note that we can not implement a Consumable instance because -- Array# is unlifted. lseq :: Array# a %1 -> b %1 -> b infixr 0 `lseq` size :: Array# a %1 -> (# Ur Int, Array# a #) get :: Int -> Array# a %1 -> (# Ur a, Array# a #) set :: Int -> a -> Array# a %1 -> Array# a -- | Copy the first mutable array into the second mutable array, starting -- from the given index of the source array. -- -- It copies fewer elements if the second array is smaller than the -- first. n should be within [0..size src). -- -- 
--   copyInto n src dest:
--    dest[i] = src[n+i] for i < size dest, i < size src + n
--
copyInto :: Int -> Array# a %1 -> Array# a %1 -> (# Array# a, Array# a #) map :: (a -> b) -> Array# a %1 -> Array# b -- | Return the array elements as a lazy list. toList :: Array# a %1 -> Ur [a] -- | O(1) Convert an Array# to an immutable Array#. freeze :: (Array# a -> b) -> Array# a %1 -> Ur b -- | Clone an array. dup2 :: Array# a %1 -> (# Array# a, Array# a #) -- | This module provides a pure linear interface for arrays with in-place -- mutation. -- -- To use these mutable arrays, create a linear computation of type -- Array a %1-> Ur b and feed it to alloc or -- fromList. -- --

A Tiny Example

-- -- 
--   >>> :set -XLinearTypes
--   
--   >>> :set -XNoImplicitPrelude
--   
--   >>> import Prelude.Linear
--   
--   >>> import qualified Data.Array.Mutable.Linear as Array
--   
--   >>> :{
--    isFirstZero :: Array.Array Int %1-> Ur Bool
--    isFirstZero arr =
--      Array.get 0 arr
--        & \(Ur val, arr') -> arr' `lseq` Ur (val == 0)
--   :}
--
-- -- 
--   >>> unur $ Array.fromList [0..10] isFirstZero
--   True
--   
--   >>> unur $ Array.fromList [1,2,3] isFirstZero
--   False
--
module Data.Array.Mutable.Linear data Array a -- | Allocate a constant array given a size and an initial value The size -- must be non-negative, otherwise this errors. alloc :: HasCallStack => Int -> a -> (Array a %1 -> Ur b) %1 -> Ur b -- | Allocate a constant array given a size and an initial value, using -- another array as a uniqueness proof. allocBeside :: Int -> a -> Array b %1 -> (Array a, Array b) -- | Allocate an array from a list fromList :: HasCallStack => [a] -> (Array a %1 -> Ur b) %1 -> Ur b -- | Sets the value of an index. The index should be less than the arrays -- size, otherwise this errors. set :: HasCallStack => Int -> a -> Array a %1 -> Array a -- | Same as set, but does not do bounds-checking. The behaviour is -- undefined if an out-of-bounds index is provided. unsafeSet :: Int -> a -> Array a %1 -> Array a -- | Resize an array. That is, given an array, a target size, and a seed -- value; resize the array to the given size using the seed value to fill -- in the new cells when necessary and copying over all the unchanged -- cells. -- -- Target size should be non-negative. -- -- 
--   let b = resize n x a,
--     then size b = n,
--     and b[i] = a[i] for i < size a,
--     and b[i] = x for size a <= i < n.
--
resize :: HasCallStack => Int -> a -> Array a %1 -> Array a map :: (a -> b) -> Array a %1 -> Array b -- | Get the value of an index. The index should be less than the arrays -- size, otherwise this errors. get :: HasCallStack => Int -> Array a %1 -> (Ur a, Array a) -- | Same as get, but does not do bounds-checking. The behaviour is -- undefined if an out-of-bounds index is provided. unsafeGet :: Int -> Array a %1 -> (Ur a, Array a) size :: Array a %1 -> (Ur Int, Array a) -- | Copy a slice of the array, starting from given offset and copying -- given number of elements. Returns the pair (oldArray, slice). -- -- Start offset + target size should be within the input array, and both -- should be non-negative. -- -- 
--   let b = slice i n a,
--     then size b = n,
--     and b[j] = a[i+j] for 0 <= j < n
--
slice :: HasCallStack => Int -> Int -> Array a %1 -> (Array a, Array a) -- | Return the array elements as a lazy list. toList :: Array a %1 -> Ur [a] -- | O(1) Convert an Array to an immutable Vector -- (from vector package). freeze :: Array a %1 -> Ur (Vector a) -- | Same as get, but takes the Array as the first parameter. read :: HasCallStack => Array a %1 -> Int -> (Ur a, Array a) -- | Same as unsafeGet, but takes the Array as the first -- parameter. unsafeRead :: Array a %1 -> Int -> (Ur a, Array a) -- | Same as set, but takes the Array as the first parameter. write :: HasCallStack => Array a %1 -> Int -> a -> Array a -- | Same as unsafeSet, but takes the Array as the first -- parameter. unsafeWrite :: Array a %1 -> Int -> a -> Array a -- | Mutable vectors with a linear API. -- -- Vectors are arrays that grow automatically, that you can append to -- with push. They never shrink automatically to reduce -- unnecessary copying, use shrinkToFit to get rid of the wasted -- space. -- -- To use mutable vectors, create a linear computation of type Vector -- a %1-> Ur b and feed it to constant or fromList. -- --

Example

-- -- 
--   >>> :set -XLinearTypes
--   
--   >>> import Prelude.Linear
--   
--   >>> import qualified Data.Vector.Mutable.Linear as Vector
--   
--   >>> :{
--    isFirstZero :: Vector.Vector Int %1-> Ur Bool
--    isFirstZero vec =
--      Vector.get 0 vec
--        & \(Ur ret, vec) -> vec `lseq` Ur (ret == 0)
--   :}
--
-- -- 
--   >>> unur $ Vector.fromList [0..10] isFirstZero
--   True
--   
--   >>> unur $ Vector.fromList [1,2,3] isFirstZero
--   False
--
module Data.Vector.Mutable.Linear -- | A dynamic mutable vector. data Vector a empty :: (Vector a %1 -> Ur b) %1 -> Ur b -- | Allocate a constant vector of a given non-negative size (and error on -- a bad size) constant :: HasCallStack => Int -> a -> (Vector a %1 -> Ur b) %1 -> Ur b -- | Allocator from a list fromList :: HasCallStack => [a] -> (Vector a %1 -> Ur b) %1 -> Ur b -- | Write to an element . Note: this will not write to elements beyond the -- current size of the vector and will error instead. set :: HasCallStack => Int -> a -> Vector a %1 -> Vector a -- | Same as write, but does not do bounds-checking. The behaviour -- is undefined when passed an invalid index. unsafeSet :: HasCallStack => Int -> a -> Vector a %1 -> Vector a -- | Modify a value inside a vector, with an ability to return an extra -- information. Errors if the index is out of bounds. modify :: HasCallStack => (a -> (a, b)) -> Int -> Vector a %1 -> (Ur b, Vector a) -- | Same as modify, but without the ability to return extra -- information. modify_ :: HasCallStack => (a -> a) -> Int -> Vector a %1 -> Vector a -- | Insert at the end of the vector. This will grow the vector if there is -- no empty space. push :: a -> Vector a %1 -> Vector a -- | Pop from the end of the vector. This will never shrink the vector, use -- shrinkToFit to remove the wasted space. pop :: Vector a %1 -> (Ur (Maybe a), Vector a) -- | Filters the vector in-place. It does not deallocate unused capacity, -- use shrinkToFit for that if necessary. filter :: Vector a %1 -> (a -> Bool) -> Vector a -- | A version of fmap which can throw out elements. mapMaybe :: Vector a %1 -> (a -> Maybe b) -> Vector b -- | Return a slice of the vector with given size, starting from an offset. -- -- Start offset + target size should be within the input vector, and both -- should be non-negative. -- -- This is a constant time operation if the start offset is 0. Use -- shrinkToFit to remove the possible wasted space if necessary. slice :: Int -> Int -> Vector a %1 -> Vector a -- | Resize the vector to not have any wasted memory (size == capacity). -- This returns a semantically identical vector. shrinkToFit :: Vector a %1 -> Vector a -- | Read from a vector, with an in-range index and error for an index that -- is out of range (with the usual range 0..size-1). get :: HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a) -- | Same as read, but does not do bounds-checking. The behaviour is -- undefined when passed an invalid index. unsafeGet :: HasCallStack => Int -> Vector a %1 -> (Ur a, Vector a) -- | Number of elements inside the vector. -- -- This might be different than how much actual memory the vector is -- using. For that, see: capacity. size :: Vector a %1 -> (Ur Int, Vector a) -- | Capacity of a vector. In other words, the number of elements the -- vector can contain before it is copied to a bigger array. capacity :: Vector a %1 -> (Ur Int, Vector a) -- | Return the vector elements as a lazy list. toList :: Vector a %1 -> Ur [a] -- | O(1) Convert a Vector to an immutable Vector -- (from vector package). freeze :: Vector a %1 -> Ur (Vector a) -- | Same as get, but takes the Vector as the first -- parameter. read :: HasCallStack => Vector a %1 -> Int -> (Ur a, Vector a) -- | Same as unsafeGet, but takes the Vector as the first -- parameter. unsafeRead :: Vector a %1 -> Int -> (Ur a, Vector a) -- | Same as set, but takes the Vector as the first -- parameter. write :: HasCallStack => Vector a %1 -> Int -> a -> Vector a -- | Same as unsafeSafe, but takes the Vector as the first -- parameter. unsafeWrite :: Vector a %1 -> Int -> a -> Vector a -- | This module provides mutable hashmaps with a linear interface. -- -- It is implemented with Robin Hood hashing which has amortized constant -- time lookups and updates. module Data.HashMap.Mutable.Linear -- | A mutable hashmap with a linear interface. data HashMap k v -- | At minimum, we need to store hashable and identifiable keys type Keyed k = (Eq k, Hashable k) -- | Run a computation with an empty HashMap with given capacity. empty :: forall k v b. Keyed k => Int -> (HashMap k v %1 -> Ur b) %1 -> Ur b -- | Run a computation with an HashMap containing given key-value -- pairs. fromList :: forall k v b. Keyed k => [(k, v)] -> (HashMap k v %1 -> Ur b) %1 -> Ur b -- | Insert a key value pair to a HashMap. It overwrites the -- previous value if it exists. insert :: Keyed k => k -> v -> HashMap k v %1 -> HashMap k v -- | insert (in the provided order) the given key-value pairs to the -- hashmap. insertAll :: Keyed k => [(k, v)] -> HashMap k v %1 -> HashMap k v -- | Delete a key from a HashMap. Does nothing if the key does not -- exist. delete :: Keyed k => k -> HashMap k v %1 -> HashMap k v -- | Complexity: O(capacity hm) filter :: Keyed k => (v -> Bool) -> HashMap k v %1 -> HashMap k v -- | Complexity: O(capacity hm) filterWithKey :: Keyed k => (k -> v -> Bool) -> HashMap k v %1 -> HashMap k v -- | A version of fmap which can throw out the elements. -- -- Complexity: O(capacity hm) mapMaybe :: Keyed k => (v -> Maybe v') -> HashMap k v %1 -> HashMap k v' -- | Same as mapMaybe, but also has access to the keys. mapMaybeWithKey :: forall k v v'. Keyed k => (k -> v -> Maybe v') -> HashMap k v %1 -> HashMap k v' -- | Reduce the HashMap capacity to decrease wasted memory. -- Returns a semantically identical HashMap. -- -- This is only useful after a lot of deletes. -- -- Complexity: O(capacity hm) shrinkToFit :: Keyed k => HashMap k a %1 -> HashMap k a -- | A general modification function; which can insert, update or delete a -- value of the key. See alterF, for an even more general -- function. alter :: Keyed k => (Maybe v -> Maybe v) -> k -> HashMap k v %1 -> HashMap k v -- | The most general modification function; which can insert, update or -- delete a value of the key, while collecting an effect in the form of -- an arbitrary Functor. alterF :: (Keyed k, Functor f) => (Maybe v -> f (Ur (Maybe v))) -> k -> HashMap k v %1 -> f (HashMap k v) -- | Number of key-value pairs inside the HashMap size :: HashMap k v %1 -> (Ur Int, HashMap k v) -- | Maximum number of elements the HashMap can store without resizing. -- However, for performance reasons, the HashMap might be before -- full. -- -- Use shrinkToFit to reduce the wasted space. capacity :: HashMap k v %1 -> (Ur Int, HashMap k v) -- | Look up a value from a HashMap. lookup :: Keyed k => k -> HashMap k v %1 -> (Ur (Maybe v), HashMap k v) -- | Check if the given key exists. member :: Keyed k => k -> HashMap k v %1 -> (Ur Bool, HashMap k v) -- | Converts a HashMap to a lazy list. toList :: HashMap k v %1 -> Ur [(k, v)] -- | A right-biased union. -- -- Complexity: O(min(capacity hm1, capacity hm2) union :: Keyed k => HashMap k v %1 -> HashMap k v %1 -> HashMap k v -- | Union of two maps using the provided function on conflicts. -- -- Complexity: O(min(capacity hm1, capacity hm2) unionWith :: Keyed k => (v -> v -> v) -> HashMap k v %1 -> HashMap k v %1 -> HashMap k v -- | Intersection of two maps with the provided combine function. -- -- Complexity: O(min(capacity hm1, capacity hm2) intersectionWith :: Keyed k => (a -> b -> c) -> HashMap k a %1 -> HashMap k b %1 -> HashMap k c -- | This module defines linear mutable sets. -- -- The underlying implementation uses Linear, so it inherits the -- time and memory characteristics of it. -- -- Please import this module qualified to avoid name clashes. module Data.Set.Mutable.Linear data Set a empty :: Keyed a => Int -> (Set a %1 -> Ur b) %1 -> Ur b insert :: Keyed a => a -> Set a %1 -> Set a delete :: Keyed a => a -> Set a %1 -> Set a union :: Keyed a => Set a %1 -> Set a %1 -> Set a intersection :: Keyed a => Set a %1 -> Set a %1 -> Set a size :: Keyed a => Set a %1 -> (Ur Int, Set a) member :: Keyed a => a -> Set a %1 -> (Ur Bool, Set a) fromList :: Keyed a => [a] -> (Set a %1 -> Ur b) %1 -> Ur b toList :: Keyed a => Set a %1 -> Ur [a] type Keyed a = Keyed a -- | This module provides destination arrays -- --

What are destination arrays? What are they good for?

-- -- Destination arrays are write-only arrays that are only allocated once, -- thereby avoiding your reliance on GHC's fusion mechanisms to remove -- unneccessary allocations. -- -- The current status-quo for computations that have a write-only array -- threaded along is to rely on fusion. While the optimizations in say, -- Vector are quite good at ensuring GHC fuses, they aren't -- foolproof and can sometimes break by simple refactorings. -- -- Avoiding extra allocations of a write-only array is easy in C, with -- something the functional programming world calls destination passing -- style, or DPS for short. -- -- Here is a C function that manipulates an array written in DPS style; -- it takes in the destiniation array res and writes to it: -- -- 
--   // ((a + b) * c) for vectors a,b and scalar c
--   void apbxc(int size, int *a, int *b, int c, int *res){
--     for (int i=0; i<size;++i){res[i]=a[i]+b[i];}
--     mult(size, c, res);
--   }
--   
--   void mult(int size, int scalar, int* vec){
--     for (int i=0; i<size; ++i){vec[i] *= scalar;}
--   }
--
-- --

Example: Stencil computation

-- -- One possible use of destination arrays could be the stencil -- computation typically called jacobi. Here we show one time step -- of this computation in a single dimension: -- -- 
--   jacobi1d :: Int -> Vector Double -> Vector Double
--   jacobi1d n oldA = case stepArr n oldA of
--     newB -> stepArr n newB
--   
--   -- jacobi1d N A[N] B[N] = (new_A[N], new_B[N]).
--   stepArr :: Int -> Vector Double -> Vector Double
--   stepArr n oldArr = alloc n $ newArr -> fillArr newArr oldArr 1
--     where
--       fillArr :: DArray Double %1-> Vector Double -> Int -> ()
--       fillArr newA oldA ix
--         | ix == (n-1) = newA &
--             fill (0.33 * ((oldA ! (ix-1)) + (oldA ! ix) + (oldA ! (ix+1))))
--         | True = split 1 newA & (fst, rest) ->
--             fill (0.33 * ((oldA ! (ix-1)) + (oldA ! ix) + (oldA ! (ix+1)))) fst &
--               () -> fillArr rest oldA (ix+1)
--
-- -- We can be sure that stepArr only allocates one array. In -- certain variations and implementations of the jacobi kernel or similar -- dense array computations, ensuring one allocation with -- Data.Vector's fusion oriented implementation may not be -- trivial. -- -- For reference, the C equivalent of this code is the following: -- -- 
--   static void jacobi_1d_time_step(int n, int *A, int *B){
--     int t, i;
--     for (i = 1; i < _PB_N - 1; i++)
--       B[i] = 0.33333 * (A[i-1] + A[i] + A[i + 1]);
--     for (i = 1; i < _PB_N - 1; i++)
--       A[i] = 0.33333 * (B[i-1] + B[i] + B[i + 1]);
--   }
--
-- -- This example is taken from the polybench test-suite of dense -- array codes. -- --

Aside: Why do we need linear types?

-- -- Linear types avoids ambiguous writes to the destination array. For -- example, this function could never be linear and hence we avoid -- ambiguity: -- -- 
--   nonLinearUse :: DArray Int -> ()
--   nonLinearUse arr = case (replicate 3 arr, replicate 4 arr) of
--     ((),()) -> ()
--
-- -- Furthermore, this API is safely implemented by mutating an underlying -- array which is good for performance. The API is safe because linear -- types enforce the fact that each reference to an underlying mutable -- array (and there can be more than one by using split) is -- linearly threaded through functions and at the end consumed by one of -- our write functions. -- -- Lastly, linear types are used to ensure that each cell in the -- destination array is written to exactly once. This is because the only -- way to create and use a destination array is via -- -- 
--   alloc :: Int -> (DArray a %1-> ()) %1-> Vector a
--
-- -- and the only way to really consume a DArray is via our API -- which requires you to completely fill the array. module Data.Array.Destination -- | A destination array, or DArray, is a write-only array that is -- filled by some computation which ultimately returns an array. data DArray a alloc :: Int -> (DArray a %1 -> ()) %1 -> Vector a -- | Get the size of a destination array. size :: DArray a %1 -> (Ur Int, DArray a) -- | Fill a destination array with a constant replicate :: a -> DArray a %1 -> () -- | split n dest = (destl, destr) such as destl -- has length n. -- -- split is total: if n is larger than the length of -- dest, then destr is empty. split :: Int -> DArray a %1 -> (DArray a, DArray a) -- | Fills the destination array with the contents of given vector. -- -- Errors if the given vector is smaller than the destination array. mirror :: HasCallStack => Vector a -> (a %1 -> b) -> DArray b %1 -> () -- | Fill a destination array using the given index-to-value function. fromFunction :: (Int -> b) -> DArray b %1 -> () -- | fill a dest fills a singleton destination array. Caution, -- fill a dest will fail is dest isn't of length -- exactly one. fill :: HasCallStack => a %1 -> DArray a %1 -> () -- | dropEmpty dest consumes and empty array and fails otherwise. dropEmpty :: HasCallStack => DArray a %1 -> () -- | This module provides push arrays. -- -- These are part of a larger framework for controlling when memory is -- allocated for an array. See Data.Array.Polarized. -- -- This module is designed to be imported qualified as Push. module Data.Array.Polarized.Push -- | Push arrays are un-allocated finished arrays. These are finished -- computations passed along or enlarged until we are ready to allocate. data Array a [Array] :: (forall m. Monoid m => (a -> m) -> m) -> Array a -- | make x n creates a constant push array of length -- n in which every element is x. make :: HasCallStack => a -> Int -> Array a singleton :: a -> Array a cons :: a -> Array a %1 -> Array a snoc :: a -> Array a %1 -> Array a -- | Convert a push array into a vector by allocating. This would be a -- common end to a computation using push and pull arrays. alloc :: Array a %1 -> Vector a foldMap :: Monoid b => (a -> b) -> Array a %1 -> b unzip :: Array (a, b) %1 -> (Array a, Array b) instance GHC.Base.Semigroup (Data.Array.Polarized.Push.ArrayWriter a) instance GHC.Base.Monoid (Data.Array.Polarized.Push.ArrayWriter a) instance Data.Monoid.Linear.Internal.Semigroup.Semigroup (Data.Array.Polarized.Push.ArrayWriter a) instance Data.Monoid.Linear.Internal.Monoid.Monoid (Data.Array.Polarized.Push.ArrayWriter a) instance Data.Functor.Linear.Internal.Functor.Functor Data.Array.Polarized.Push.Array instance GHC.Base.Semigroup (Data.Array.Polarized.Push.Array a) instance Data.Monoid.Linear.Internal.Semigroup.Semigroup (Data.Array.Polarized.Push.Array a) instance GHC.Base.Monoid (Data.Array.Polarized.Push.Array a) instance Data.Monoid.Linear.Internal.Monoid.Monoid (Data.Array.Polarized.Push.Array a) -- | This module documents polarized arrays and top-level conversions -- --

What are polarized arrays and what are they good for?

-- -- Polarized arrays aim to offer an API to replace that of -- Data.Vector with mechanisms to explicitly control when memory -- is allocated for an array. The current status quo is to use some array -- or vector type and rely on a good implementation and GHC's fusion -- capabilities to avoid unnecessary allocations (and thus save memory -- and improve the performance). -- -- Polarized arrays are arrays with one of two polarities or directions: -- push or pull. Push and pull arrays are two array types that do not -- allocate memory with conversions to and from Data.Vector. The -- only API function that allocates space for an array is -- Push.alloc. Nothing else allocates memory and hence we are -- not relying on GHC to fuse according to a particular implementation of -- our vector API and program. -- --

What is a pull array?

-- -- A pull array is one that it's easy to "pull" from and read. These -- arrays work nicely as arguments to functions and we can fold, map, -- zip, and split these easily. -- -- A typical use of polarized arrays would construct a pull array to -- begin a computation using arrays. -- --

What is a push array?

-- -- A push array is a finished result that we do not want to allocate just -- yet. We can concatenate two push arrays, convert a pull array into a -- push array (without any memory allocation), create constant push -- arrays and when we desire allocate a push array to a -- Data.Vector: -- -- 
--   Push.alloc :: Push.Array a %1-> Vector a
--
-- -- A push array is typically created towards the end of a computation -- that uses arrays and passed along until we are ready to allocate. -- --

What does using polarized arrays look like?

-- -- A typical computation would start by constructing a pull array, -- computing over it, converting it to a push array while other -- computations occur and then finally finishing the computation by -- allocating the push array (or arrays). -- -- A simple example is a one-time allocating filter on vectors: -- -- 
--   vecfilter :: Vector a -> (a -> Bool) -> Vector a
--   vecfilter vec f = Push.alloc (transfer (loop (Pull.fromVector vec) f))
--     where
--       loop :: Pull.Array a -> (a -> Bool) -> Pull.Array a
--       loop arr f = case Pull.findLength arr of
--         (0,_) -> Pull.fromFunction (error "empty") 0
--         (n,_) -> case Pull.split 1 arr of
--           (head, tail) -> case Pull.index head 0 of
--             (a,_) ->
--               if f a
--               then Pull.append (Pull.singleton a) (loop tail f)
--               else loop tail f
--
-- --

Aside: why do we need linear types?

-- -- To correctly represent a push array, we need a way of specifying a -- computation that writes to and fills an array. -- -- 
--   data Array a where
--     Array :: (forall b. (a %1-> b) -> DArray b %1-> ()) %1-> Int -> Array a
--
-- -- As documented with destination arrays in -- Data.Array.Destination, any computation of type DArray b -- %1-> () must fill the array. Now, since the b is -- completely abstract due to the rank2 type (read about -XRankNTypes for -- more) this computation must fill the array by wrapping writes of -- values of type a with the given linear conversion function of -- type a %1-> b. This prevents the computation from being -- evaluated until we are sure we want to allocate. -- --

Background for the interested

-- -- To understand how polarized arrays work in greater depth, these links -- may be of some help: -- -- module Data.Array.Polarized -- | Convert a pull array into a push array. NOTE: this does NOT require -- allocation and can be in-lined. transfer :: Array a %1 -> Array a -- | This is a shortcut convenience function for transfer . -- Pull.fromVector. walk :: Vector a %1 -> Array a