module Data.Queue.Indexed.List
(List(..)
,DiffList(..)
,reverseTraversable
,reverseTraversal)
where
import Data.Queue.Indexed.Class
import TypeLevel.Singletons hiding (The(..))
import Data.Traversable.Parts
infixr 5 :-
data List n a where
Nil :: List 0 a
(:-) :: a -> List n a -> List (1 + n) a
instance IndexedQueue List a where
empty = Nil
insert = (:-)
minView (x :- xs) = (x,xs)
minViewMay Nil b _ = b
minViewMay (x :- xs) _ f = f x xs
instance MeldableIndexedQueue List a where
merge Nil ys = ys
merge (x :- xs) ys = x :- merge xs ys
newtype DiffList n a = DiffList
{ runDiffList :: forall m. List m a -> List (n + m) a
}
instance IndexedQueue DiffList a where
empty = DiffList id
insert x xs =
DiffList
(\ys ->
runDiffList xs (x :- ys))
minView (DiffList xs) =
case minView (xs Nil) of
(y,ys) -> (y, DiffList (merge ys))
minViewMay (DiffList xs) b f =
minViewMay
(xs Nil)
b
(\y ys ->
f y (DiffList (merge ys)))
instance MeldableIndexedQueue DiffList a where
merge (DiffList xs) (DiffList ys) = DiffList (ys . xs)
reverseTraversable :: Traversable t => t a -> t a
reverseTraversable = transformTraversable (`runDiffList` Nil)
reverseTraversal
:: ((a -> Parts DiffList List a a a) -> t -> Parts DiffList List a a t)
-> t
-> t
reverseTraversal = transformTraversal (`runDiffList` Nil)