Seq.hs

--------------------------------------------------------------------------------
{-| Module      :  Seq
    Copyright   :  (c) Daan Leijen 2002
    License     :  BSD-style

    Maintainer  :  daan@cs.uu.nl
    Stability   :  provisional
    Portability :  portable

  An implementation of John Hughes's efficient catenable sequence type. A lazy sequence
  @Seq a@ can be concatenated in /O(1)/ time. After
  construction, the sequence in converted in /O(n)/ time into a list.

  Modified by John Meacham for use in jhc
-}
---------------------------------------------------------------------------------}
module Util.Seq( -- * Type
            Seq
            -- * Operators
          , (<>)

            -- * Construction
          , empty
          , single
          , singleton
          , cons
          , append

            -- * Conversion
          , toList
          , fromList
          ) where

import Data.Monoid(Monoid(..))
import Control.Monad

{--------------------------------------------------------------------
  Operators
--------------------------------------------------------------------}
infixr 5 <>

-- | /O(1)/. Append two sequences, see 'append'.
(<>) :: Seq a -> Seq a -> Seq a
s <> t
  = append s t

{--------------------------------------------------------------------
  Type
--------------------------------------------------------------------}
-- | Sequences of values @a@.
newtype Seq a = Seq ([a] -> [a])


{--------------------------------------------------------------------
  Construction
--------------------------------------------------------------------}
-- | /O(1)/. Create an empty sequence.
empty :: Seq a
empty
  = Seq (\ts -> ts)

-- | /O(1)/. Create a sequence of one element.
single :: a -> Seq a
single x
  = Seq (\ts -> x:ts)

-- | /O(1)/. Create a sequence of one element.
singleton :: a -> Seq a
singleton x = single x

-- | /O(1)/. Put a value in front of a sequence.
cons :: a -> Seq a -> Seq a
cons x (Seq f)
  = Seq (\ts -> x:f ts)

-- | /O(1)/. Append two sequences.
append :: Seq a -> Seq a -> Seq a
append (Seq f) (Seq g)
  = Seq (\ts -> f (g ts))


{--------------------------------------------------------------------
  Conversion
--------------------------------------------------------------------}
-- | /O(n)/. Convert a sequence to a list.
toList :: Seq a -> [a]
toList (Seq f)
  = f []

-- | /O(n)/. Create a sequence from a list.
fromList :: [a] -> Seq a
fromList xs
  = Seq (\ts -> xs++ts)


--tell x = W.tell (Util.Seq.singleton x)
--tells xs = W.tell (Util.Seq.fromList xs)


concat :: Seq (Seq a) -> Seq a
concat (Seq f) = (foldr Util.Seq.append Util.Seq.empty (f []))

instance Functor Util.Seq.Seq where
    --fmap f xs = Seq.fromList (map f (Seq.toList xs))
    fmap f (Seq xs) = Seq (\ts -> map f (xs []) ++ ts )

instance Monad Util.Seq.Seq where
    --a >>= b  = mconcat ( fmap b (Seq.toList a))
    a >>= b  = Util.Seq.concat (fmap b a)
    return x = Util.Seq.single x
    fail _ = Util.Seq.empty

instance MonadPlus Util.Seq.Seq where
    mplus = mappend
    mzero = Util.Seq.empty


instance Monoid (Seq a) where
    mempty = empty
    mappend = append