Movatterモバイル変換

{-# LANGUAGE Trustworthy #-}{-# LANGUAGE NoImplicitPrelude #-}{-# LANGUAGE TypeOperators #-}------------------------------------------------------------------------------- |-- Module      :  Control.Monad.Fix-- Copyright   :  (c) Andy Gill 2001,--                (c) Oregon Graduate Institute of Science and Technology, 2002-- License     :  BSD-style (see the file libraries/base/LICENSE)-- Maintainer  :  libraries@haskell.org-- Stability   :  experimental-- Portability :  portable---- Monadic fixpoints.---- For a detailed discussion, see Levent Erkok's thesis,-- /Value Recursion in Monadic Computations/, Oregon Graduate Institute, 2002.-------------------------------------------------------------------------------moduleControl.Monad.Fix(MonadFix(mfix),fix)whereimportData.EitherimportData.Function(fix)importData.MaybeimportData.Monoid(Dual(..),Sum(..),Product(..),First(..),Last(..),Alt(..),Ap(..))importData.Ord(Down(..))importGHC.Base(Monad,NonEmpty(..),errorWithoutStackTrace,(.))importGHC.GenericsimportGHC.List(head,tail)importControl.Monad.ST.ImpimportSystem.IO-- | Monads having fixed points with a \'knot-tying\' semantics.-- Instances of 'MonadFix' should satisfy the following laws:---- [Purity]--      @'mfix' ('Control.Monad.return' . h)  =  'Control.Monad.return' ('fix' h)@---- [Left shrinking (or Tightening)]--      @'mfix' (\\x -> a >>= \\y -> f x y)  =  a >>= \\y -> 'mfix' (\\x -> f x y)@---- [Sliding]--      @'mfix' ('Control.Monad.liftM' h . f)  =  'Control.Monad.liftM' h ('mfix' (f . h))@,--      for strict @h@.---- [Nesting]--      @'mfix' (\\x -> 'mfix' (\\y -> f x y))  =  'mfix' (\\x -> f x x)@---- This class is used in the translation of the recursive @do@ notation-- supported by GHC and Hugs.class(Monadm)=>MonadFixmwhere-- | The fixed point of a monadic computation.-- @'mfix' f@ executes the action @f@ only once, with the eventual-- output fed back as the input.  Hence @f@ should not be strict,-- for then @'mfix' f@ would diverge.mfix::(a->ma)->ma-- Instances of MonadFix for Prelude monads-- | @since 2.01instanceMonadFixMaybewheremfix :: (a -> Maybe a) -> Maybe amfixa -> Maybe af=leta :: Maybe aa=a -> Maybe af(Maybe a -> aforall p. Maybe p -> punJustMaybe aa)inMaybe aawhereunJust :: Maybe p -> punJust(Justpx)=pxunJustMaybe pNothing=[Char] -> pforall a. [Char] -> aerrorWithoutStackTrace[Char]"mfix Maybe: Nothing"-- | @since 2.01instanceMonadFix[]wheremfix :: (a -> [a]) -> [a]mfixa -> [a]f=case([a] -> [a]) -> [a]forall a. (a -> a) -> afix(a -> [a]f(a -> [a]) -> ([a] -> a) -> [a] -> [a]forall b c a. (b -> c) -> (a -> b) -> a -> c.[a] -> aforall a. [a] -> ahead)of[]->[](ax:[a]_)->axa -> [a] -> [a]forall a. a -> [a] -> [a]:(a -> [a]) -> [a]forall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix([a] -> [a]forall a. [a] -> [a]tail([a] -> [a]) -> (a -> [a]) -> a -> [a]forall b c a. (b -> c) -> (a -> b) -> a -> c.a -> [a]f)-- | @since 4.9.0.0instanceMonadFixNonEmptywheremfix :: (a -> NonEmpty a) -> NonEmpty amfixa -> NonEmpty af=case(NonEmpty a -> NonEmpty a) -> NonEmpty aforall a. (a -> a) -> afix(a -> NonEmpty af(a -> NonEmpty a) -> (NonEmpty a -> a) -> NonEmpty a -> NonEmpty aforall b c a. (b -> c) -> (a -> b) -> a -> c.NonEmpty a -> aforall a. NonEmpty a -> aneHead)of~(ax:|[a]_)->axa -> [a] -> NonEmpty aforall a. a -> [a] -> NonEmpty a:|(a -> [a]) -> [a]forall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix(NonEmpty a -> [a]forall a. NonEmpty a -> [a]neTail(NonEmpty a -> [a]) -> (a -> NonEmpty a) -> a -> [a]forall b c a. (b -> c) -> (a -> b) -> a -> c.a -> NonEmpty af)whereneHead :: NonEmpty a -> aneHead~(aa:|[a]_)=aaneTail :: NonEmpty a -> [a]neTail~(a_:|[a]as)=[a]as-- | @since 2.01instanceMonadFixIOwheremfix :: (a -> IO a) -> IO amfix=(a -> IO a) -> IO aforall a. (a -> IO a) -> IO afixIO-- | @since 2.01instanceMonadFix((->)r)wheremfix :: (a -> r -> a) -> r -> amfixa -> r -> af=\rr->leta :: aa=a -> r -> afaarrinaa-- | @since 4.3.0.0instanceMonadFix(Eithere)wheremfix :: (a -> Either e a) -> Either e amfixa -> Either e af=leta :: Either e aa=a -> Either e af(Either e a -> aforall a p. Either a p -> punRightEither e aa)inEither e aawhereunRight :: Either a p -> punRight(Rightpx)=pxunRight(Lefta_)=[Char] -> pforall a. [Char] -> aerrorWithoutStackTrace[Char]"mfix Either: Left"-- | @since 2.01instanceMonadFix(STs)wheremfix :: (a -> ST s a) -> ST s amfix=(a -> ST s a) -> ST s aforall a s. (a -> ST s a) -> ST s afixST-- Instances of Data.Monoid wrappers-- | @since 4.8.0.0instanceMonadFixDualwheremfix :: (a -> Dual a) -> Dual amfixa -> Dual af=a -> Dual aforall a. a -> Dual aDual((a -> a) -> aforall a. (a -> a) -> afix(Dual a -> aforall a. Dual a -> agetDual(Dual a -> a) -> (a -> Dual a) -> a -> aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Dual af))-- | @since 4.8.0.0instanceMonadFixSumwheremfix :: (a -> Sum a) -> Sum amfixa -> Sum af=a -> Sum aforall a. a -> Sum aSum((a -> a) -> aforall a. (a -> a) -> afix(Sum a -> aforall a. Sum a -> agetSum(Sum a -> a) -> (a -> Sum a) -> a -> aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Sum af))-- | @since 4.8.0.0instanceMonadFixProductwheremfix :: (a -> Product a) -> Product amfixa -> Product af=a -> Product aforall a. a -> Product aProduct((a -> a) -> aforall a. (a -> a) -> afix(Product a -> aforall a. Product a -> agetProduct(Product a -> a) -> (a -> Product a) -> a -> aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Product af))-- | @since 4.8.0.0instanceMonadFixFirstwheremfix :: (a -> First a) -> First amfixa -> First af=Maybe a -> First aforall a. Maybe a -> First aFirst((a -> Maybe a) -> Maybe aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix(First a -> Maybe aforall a. First a -> Maybe agetFirst(First a -> Maybe a) -> (a -> First a) -> a -> Maybe aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> First af))-- | @since 4.8.0.0instanceMonadFixLastwheremfix :: (a -> Last a) -> Last amfixa -> Last af=Maybe a -> Last aforall a. Maybe a -> Last aLast((a -> Maybe a) -> Maybe aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix(Last a -> Maybe aforall a. Last a -> Maybe agetLast(Last a -> Maybe a) -> (a -> Last a) -> a -> Maybe aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Last af))-- | @since 4.8.0.0instanceMonadFixf=>MonadFix(Altf)wheremfix :: (a -> Alt f a) -> Alt f amfixa -> Alt f af=f a -> Alt f aforall k (f :: k -> *) (a :: k). f a -> Alt f aAlt((a -> f a) -> f aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix(Alt f a -> f aforall k (f :: k -> *) (a :: k). Alt f a -> f agetAlt(Alt f a -> f a) -> (a -> Alt f a) -> a -> f aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Alt f af))-- | @since 4.12.0.0instanceMonadFixf=>MonadFix(Apf)wheremfix :: (a -> Ap f a) -> Ap f amfixa -> Ap f af=f a -> Ap f aforall k (f :: k -> *) (a :: k). f a -> Ap f aAp((a -> f a) -> f aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix(Ap f a -> f aforall k (f :: k -> *) (a :: k). Ap f a -> f agetAp(Ap f a -> f a) -> (a -> Ap f a) -> a -> f aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Ap f af))-- Instances for GHC.Generics-- | @since 4.9.0.0instanceMonadFixPar1wheremfix :: (a -> Par1 a) -> Par1 amfixa -> Par1 af=a -> Par1 aforall p. p -> Par1 pPar1((a -> a) -> aforall a. (a -> a) -> afix(Par1 a -> aforall p. Par1 p -> punPar1(Par1 a -> a) -> (a -> Par1 a) -> a -> aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Par1 af))-- | @since 4.9.0.0instanceMonadFixf=>MonadFix(Rec1f)wheremfix :: (a -> Rec1 f a) -> Rec1 f amfixa -> Rec1 f af=f a -> Rec1 f aforall k (f :: k -> *) (p :: k). f p -> Rec1 f pRec1((a -> f a) -> f aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix(Rec1 f a -> f aforall k (f :: k -> *) (p :: k). Rec1 f p -> f punRec1(Rec1 f a -> f a) -> (a -> Rec1 f a) -> a -> f aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Rec1 f af))-- | @since 4.9.0.0instanceMonadFixf=>MonadFix(M1icf)wheremfix :: (a -> M1 i c f a) -> M1 i c f amfixa -> M1 i c f af=f a -> M1 i c f aforall k i (c :: Meta) (f :: k -> *) (p :: k). f p -> M1 i c f pM1((a -> f a) -> f aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix(M1 i c f a -> f aforall i (c :: Meta) k (f :: k -> *) (p :: k). M1 i c f p -> f punM1(M1 i c f a -> f a) -> (a -> M1 i c f a) -> a -> f aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> M1 i c f af))-- | @since 4.9.0.0instance(MonadFixf,MonadFixg)=>MonadFix(f:*:g)wheremfix :: (a -> (:*:) f g a) -> (:*:) f g amfixa -> (:*:) f g af=((a -> f a) -> f aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix((:*:) f g a -> f aforall (f :: * -> *) (g :: * -> *) p. (:*:) f g p -> f pfstP((:*:) f g a -> f a) -> (a -> (:*:) f g a) -> a -> f aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> (:*:) f g af))f a -> g a -> (:*:) f g aforall k (f :: k -> *) (g :: k -> *) (p :: k).f p -> g p -> (:*:) f g p:*:((a -> g a) -> g aforall (m :: * -> *) a. MonadFix m => (a -> m a) -> m amfix((:*:) f g a -> g aforall (f :: * -> *) (g :: * -> *) p. (:*:) f g p -> g psndP((:*:) f g a -> g a) -> (a -> (:*:) f g a) -> a -> g aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> (:*:) f g af))wherefstP :: (:*:) f g p -> f pfstP(f pa:*:g p_)=f pasndP :: (:*:) f g p -> g psndP(f p_:*:g pb)=g pb-- Instances for Data.Ord-- | @since 4.12.0.0instanceMonadFixDownwheremfix :: (a -> Down a) -> Down amfixa -> Down af=a -> Down aforall a. a -> Down aDown((a -> a) -> aforall a. (a -> a) -> afix(Down a -> aforall a. Down a -> agetDown(Down a -> a) -> (a -> Down a) -> a -> aforall b c a. (b -> c) -> (a -> b) -> a -> c.a -> Down af))