sequence 0.9.6 → 0.9.7

raw patch · 3 files changed

+67/−2 lines, 3 files

Files

• ChangeLog +1/−0
• Data/Sequence/BSeq.hs +64/−0
• sequence.cabal +2/−2

@@ -1,3 +1,4 @@+0.9.7: Added binary tree sequence datastructure 0.9.6: Fixed bug in Functor for FastQueue which causes it be not O(1) 0.9.5: Added traversable instances (thanks dolio!) 0.9.4: More fixing docs

@@ -0,0 +1,64 @@+{-# LANGUAGE Rank2Types,GADTs, DataKinds, TypeOperators #-}++++-----------------------------------------------------------------------------+-- |+-- Module      :  Data.Sequence.BSeq+-- Copyright   :  (c) Atze van der Ploeg 2014+-- License     :  BSD-style+-- Maintainer  :  atzeus@gmail.org+-- Stability   :  provisional+-- Portability :  portable+--+-- A sequence, implemented as a binary tree, good performance when used ephemerally+--+--+-----------------------------------------------------------------------------+module Data.Sequence.BSeq(module Data.SequenceClass,BSeq)  where+import Control.Applicative (pure, (<*>), (<$>))+import Data.Foldable+import Data.Monoid ((<>))+import Data.Traversable+import Prelude hiding (foldr,foldl)+import Data.SequenceClass++data BSeq a = Empty | Leaf a | Node (BSeq a) (BSeq a)++++instance Functor BSeq where+  fmap f = loop where+    loop Empty = Empty+    loop (Leaf x) = Leaf (f x)+    loop (Node l r) = Node (loop l) (loop r)++instance Foldable BSeq where+  foldl f = loop where+    loop i s = case viewl s of+          EmptyL -> i+          h :< t -> loop (f i h) t+  foldr f i s = foldr f i (reverse $ toRevList s)+    where toRevList s = case viewl s of+           EmptyL -> []+           h :< t -> h : toRevList t++instance Traversable BSeq where+  traverse f = loop where+    loop Empty = pure Empty+    loop (Leaf x) = Leaf <$> f x+    loop (Node l r) = Node <$> loop l <*> loop r++instance Sequence BSeq where+  empty     = Empty+  singleton = Leaf+  Empty      >< r = r+  l          >< Empty = l+  (Node l r) >< z = Node l (Node r z)+  (Leaf x)   >< z = Node (Leaf x) z+  viewl Empty               = EmptyL+  viewl (Leaf x)            = x :< Empty+  viewl (Node (Leaf x) r)   = x :< r+++

@@ -1,5 +1,5 @@ Name:                sequence-Version:             0.9.6+Version:             0.9.7 Synopsis:	         A type class for sequences and various sequence data structures. Description:         A type class for sequences and various sequence data structures. License:             BSD3@@ -14,7 +14,7 @@ Tested-With:         GHC==7.6.3 Library   Build-Depends: base >= 2 && <= 6, containers, transformers-  Exposed-modules: Data.SequenceClass, Data.Sequence.Queue, Data.Sequence.FastQueue, Data.Sequence.FastCatQueue,  Data.Sequence.ToCatQueue+  Exposed-modules: Data.SequenceClass,Data.Sequence.BSeq, Data.Sequence.Queue, Data.Sequence.FastQueue, Data.Sequence.FastCatQueue,  Data.Sequence.ToCatQueue   Extensions:	  source-repository head