-- {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# OPTIONS -Wall -fno-warn-orphans #-} -- For ghc-6.6 compatibility {-# OPTIONS_GHC -fglasgow-exts #-} ---------------------------------------------------------------------- -- | -- Module : Data.SFuture -- Copyright : (c) Conal Elliott 2007 -- License : LGPL -- -- Maintainer : conal@conal.net -- Stability : experimental -- -- A sort of semantic prototype for functional /futures/, roughly as -- described at <http://en.wikipedia.org/wiki/Futures_and_promises>. -- -- A /future/ is a value that will become knowable only later. This -- module gives a way to manipulate them functionally. For instance, -- @a+b@ becomes knowable when the later of @a@ and @b@ becomes knowable. -- -- Primitive futures can be things like /the value of the next key you -- press/, or /the value of LambdaPix stock at noon next Monday/. -- -- Composition is via standard type classes: 'Ord', 'Functor', -- 'Applicative', 'Monad', and 'Monoid'. Some comments on the 'Future' -- instances of these classes: -- -- * 'Ord': @a `min` b@ is whichever of @a@ and @b@ is knowable first. @a -- `max` b@ is whichever of @a@ and @b@ is knowable last. -- -- * Monoid: 'mempty' is a future that never becomes knowable. 'mappend' -- is the same as 'min'. -- -- * 'Functor': apply a function to a future. The result is knowable when -- the given future is knowable. -- -- * 'Applicative': 'pure' gives value knowable since the beginning of -- time. '(\<*\>)' applies a future function to a future argument. -- Result available when /both/ are available, i.e., it becomes knowable -- when the later of the two futures becomes knowable. -- -- * 'Monad': 'return' is the same as 'pure' (as always). @(>>=)@ -- cascades futures. 'join' resolves a future future value into a -- future value. -- -- Futures are parametric over /time/ as well as /value/ types. The time -- parameter can be any ordered type. -- -- Please keep in mind that this module specifies the interface and -- semantics, rather than a useful implementation. See "Data.Future" for -- an implementation that nearly implements the semantics described here. -- -- On second thought, I'm experimenting with using this module in an -- usable implementation of events. See Data.MEvent. ---------------------------------------------------------------------- module Data.SFuture ( -- * Time & futures Time, Future(..), futTime, futVal, sequenceF -- * To go elsewhere , Max(..), Min(..), AddBounds(..) ) where import Data.Monoid (Monoid(..)) import Control.Applicative (Applicative(..)) import Data.Function (on) {---------------------------------------------------------- Time and futures ----------------------------------------------------------} -- | Time of some event occurrence, which can be any @Ord@ type. In an -- actual implementation, we would not usually have access to the time -- value until (slightly after) that time. Extracting the actual time -- would block until the time is known. The added bounds represent -- -Infinity and +Infinity. Pure values have time minBound (-Infinity), -- while eternally unknowable values (non-occurring events) have time -- maxBound (+Infinity). type Time t = Max (AddBounds t) -- | A future value of type @a@ with time type @t@. Semantically, just a -- time\/value pair, but those values would not be available until -- 'force'd, which could block. newtype Future t a = Future { unFuture :: (Time t, a) } deriving (Functor, Applicative, Monad, Show) -- The 'Applicative' instance relies on the 'Monoid' instance of 'Max'. -- | A future's time futTime :: Future t a -> Time t futTime = fst . unFuture -- | A future's value futVal :: Future t a -> a futVal = snd . unFuture -- -- The Monoid instance picks the earlier future -- instance Ord t => Monoid (Future t a) where -- mempty = Future (maxBound, error "it'll never happen, buddy") -- fut@(Future (t,_)) `mappend` fut'@(Future (t',_)) = -- if t <= t' then fut else fut' -- or: instance Eq (Future t a) where (==) = error "sorry, no (==) for futures" instance Ord t => Ord (Future t a) where (<=) = (<=) `on` futTime -- We could leave 'min' to the default in terms of '(<=)', but the -- following can yield partial time info, as much as allowed by the time -- parameter type @t@ and its 'min'. Future (s,a) `min` Future (t,b) = Future (s `min` t, if s <= t then a else b) -- For some choices of @t@, there may be an efficient combination of 'min' -- and '(<=)'. In particular, 'Improving' has 'minI'. instance Ord t => Monoid (Future t a) where mempty = Future (maxBound, error "it'll never happen, buddy") mappend = min -- 'sequenceF' is like 'sequenceA' from "Data.Traversable". However, -- the @Traversable@ class assumes @Foldable@, which I'm not confident -- how to implement usefully. (I could of course just strip off the -- 'Future' constructor and the time. Why is Foldable required? -- | Make a future container into a container of futures. sequenceF :: Functor f => Future t (f a) -> f (Future t a) sequenceF (Future (tt, f)) = fmap (Future . ((,) tt)) f {---------------------------------------------------------- To go elsewhere ----------------------------------------------------------} -- For Data.Monoid: -- | Ordered monoid under 'max'. newtype Max a = Max { getMax :: a } deriving (Eq, Ord, Read, Show, Bounded) instance (Ord a, Bounded a) => Monoid (Max a) where mempty = Max minBound Max a `mappend` Max b = Max (a `max` b) -- | Ordered monoid under 'min'. newtype Min a = Min { getMin :: a } deriving (Eq, Ord, Read, Show, Bounded) instance (Ord a, Bounded a) => Monoid (Min a) where mempty = Min maxBound Min a `mappend` Min b = Min (a `min` b) -- I have a niggling uncertainty about the 'Ord' & 'Bounded' instances for -- @Min a@? Is there a reason flip the @a@ ordering instead of preserving -- it? -- For Control.Monad.Instances -- Equivalent to the Monad Writer instance. -- import Data.Monoid instance Monoid o => Monad ((,) o) where return = pure (o,a) >>= f = (o `mappend` o', a') where (o',a') = f a -- Alternatively, -- m >>= f = join (fmap f m) -- where -- join ((o, (o',a))) = (o `mappend` o', a) -- Or even, -- (o,a) >>= f = (o,id) <*> f a -- -- I prefer the join version, because it's the standard (>>=)-via-join, -- plus a very simple definition for join. Too bad join isn't a method of -- Monad, with (>>=) and join defined in terms of each other. Why isn't -- it? Probably because Monad isn't derived from Functor. Was that an -- oversight? -- Where to put this definition? Prelude? -- | Wrap a type into one having new least and greatest elements, -- preserving the existing ordering. data AddBounds a = MinBound | NoBound a | MaxBound deriving (Eq, Ord, Read, Show) instance Bounded (AddBounds a) where minBound = MinBound maxBound = MaxBound