ralist 0.1.0.0 → 0.2.0.0

raw patch · 4 files changed

+1013/−80 lines, 4 filesdep +criteriondep +deepseqdep +faildep ~basenew-uploaderPVP ok

version bump matches the API change (PVP)

Dependencies added: criterion, deepseq, fail, hspec, ralist, semigroups

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Data/RAList.hs +188/−76
• benchmark/benchmarking.hs +63/−0
• ralist.cabal +54/−4
• tests/hspec.hs +708/−0

@@ -1,4 +1,10 @@--- | +{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE ExplicitForAll #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE DeriveFoldable , DeriveTraversable#-}+-- | -- A random-access list implementation based on Chris Okasaki's approach -- on his book \"Purely Functional Data Structures\", Cambridge University -- Press, 1998, chapter 9.3.@@ -13,9 +19,9 @@      RAList     -- * Basic functions-    , empty    , cons+   , uncons --   , singleton    , (++)    , head@@ -25,6 +31,20 @@    , null    , length +   -- * Indexing lists+   -- | These functions treat a list @xs@ as a indexed collection,+   -- with indices ranging from 0 to @'length' xs - 1@.++   , (!!)+   ,lookupWithDefault+   ,lookupM+   ,lookup++   --- * KV indexing+   --- | This function treats a RAList as an association list+   ,lookupL++    -- * List transformations    , map    , reverse@@ -32,7 +52,7 @@    , intersperse    , intercalate    , transpose-   +    , subsequences    , permutations @@ -83,6 +103,7 @@    -- ** Extracting sublists    , take    , drop+   , simpleDrop    , splitAt {-RA @@ -109,18 +130,14 @@    -- ** Searching by equality    , elem    , notElem-   , lookup+ {-RA    -- ** Searching with a predicate    , find -}    , filter    , partition-   -- * Indexing lists-   -- | These functions treat a list @xs@ as a indexed collection,-   -- with indices ranging from 0 to @'length' xs - 1@. -   , (!!) {-RA    , elemIndex    , elemIndices@@ -214,8 +231,13 @@     zip, zipWith, unzip     ) import qualified Data.List as List-import Data.Monoid-+#if !MIN_VERSION_base(4,9,0) == 1+import Data.Monoid(Monoid,mappend,mempty)+#endif+import Data.Semigroup(Semigroup,(<>))+import Data.Data(Data,Typeable)+import Data.Functor.Identity(runIdentity)+import Data.Word  infixl 9  !! infixr 5  `cons`, ++@@ -227,8 +249,8 @@ -- [ [], [1], [1,1], [3], [1,3], [1,1,3], [3,3], [7], [1,7], [1,1,7], --   [3,7], [1,3,7], [1,1,3,7], [3,3,7], [7,7], [15], ... -- (I.e., skew binary numbers.)-data RAList a = RAList {-# UNPACK #-} !Int !(Top a)-    deriving (Eq)+data RAList a = RAList {-# UNPACK #-} !Word64 !(Top a)+    deriving (Eq,Data,Typeable,Foldable)  instance (Show a) => Show (RAList a) where     showsPrec p xs = showParen (p >= 10) $ showString "fromList " . showsPrec 10 (toList xs)@@ -245,33 +267,40 @@  instance Monoid (RAList a) where     mempty  = empty-    mappend = (++)+    mappend = (<>) +instance Semigroup (RAList a) where+    (<>) = (++)+ instance Functor RAList where     fmap f (RAList s wts) = RAList s (fmap f wts) +instance Applicative RAList where+    pure = \x -> RAList 1 (Cons 1 (Leaf x) Nil)+    (<*>) = zipWith ($)+ instance Monad RAList where-    return x = RAList 1 (Cons 1 (Leaf x) Nil)+    return = pure     (>>=) = flip concatMap --- Special list type for (Int, Tree a), i.e., Top a ~= [(Int, Tree a)]-data Top a = Nil | Cons {-# UNPACK #-} !Int !(Tree a) (Top a)-    deriving (Eq)+-- Special list type for (Word64, Tree a), i.e., Top a ~= [(Word64, Tree a)]+data Top a = Nil | Cons {-# UNPACK #-} !Word64 !(Tree a) (Top a)+    deriving (Eq,Data,Typeable,Functor,Foldable,Traversable) -instance Functor Top where-    fmap _ Nil = Nil-    fmap f (Cons w t xs) = Cons w (fmap f t) (fmap f xs)+--instance Functor Top where+--    fmap _ Nil = Nil+--    fmap f (Cons w t xs) = Cons w (fmap f t) (fmap f xs)  -- Complete binary tree.  The completeness of the trees is an invariant that must -- be preserved for the implementation to work. data Tree a      = Leaf a      | Node a !(Tree a) !(Tree a)-     deriving (Eq)+     deriving (Eq,Data,Typeable,Functor,Foldable,Traversable) -instance Functor Tree where-     fmap f (Leaf x)     = Leaf (f x)-     fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)+--instance Functor Tree where+--     fmap f (Leaf x)     = Leaf (f x)+--     fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)  ----- @@ -289,23 +318,78 @@ xs ++ ys | null ys   = xs                   -- small optimization to avoid consing to empty          | otherwise = foldr cons ys xs ++uncons :: RAList a -> Maybe (a, RAList a)+uncons (RAList _ Nil) =  Nothing+uncons (RAList s (Cons _ (Leaf h)     wts)) =  Just (h,RAList (s-1) wts)+uncons (RAList s (Cons w (Node x l r) wts)) = Just (x, RAList (s-1) (Cons w2 l (Cons w2 r wts)))+  where w2 = w `quot` 2+ -- | Complexity /O(1)/.-head :: RAList a -> a-head (RAList _ Nil) = errorEmptyList "head"-head (RAList _ (Cons _ (Leaf x)     _)) = x-head (RAList _ (Cons _ (Node x _ _) _)) = x+head :: RAList a -> Maybe a+head = fmap fst  . uncons  -- | Complexity /O(log n)/. last :: RAList a -> a last xs@(RAList s _) = xs !! (s-1) --- | Complexity /O(1)/.-tail :: RAList a -> RAList a-tail (RAList _ Nil) = errorEmptyList "tail"-tail (RAList s (Cons _ (Leaf _)     wts)) = RAList (s-1) wts-tail (RAList s (Cons w (Node x l r) wts)) = RAList (s-1) (Cons w2 l (Cons w2 r wts))-  where w2 = w `quot` 2+half :: Word64 -> Word64+half n = n `quot` 2 +-- | Complexity /O(log n)/.+(!!) :: RAList a -> Word64 -> a+RAList s wts !! n | n <  0 = error "Data.RAList.!!: negative index"+                  | n >= s = error "Data.RAList.!!: index too large"+                  | otherwise = ix n wts+  where ix j (Cons w t wts') | j < w     = ixt j (w `quot` 2) t+                             | otherwise = ix (j-w) wts'+        ix _ _ = error "Data.RAList.!!: impossible"+        ixt 0 0 (Leaf x) = x+        ixt 0 _ (Node x _l _r) = x+        ixt j w (Node _x l r) | j <= w    = ixt (j-1)   (w `quot` 2) l+                             | otherwise = ixt (j-1-w) (w `quot` 2) r+        ixt _j _w _ = error "Data.RAList.!!: impossible"++lookup :: forall a. Word64 -> Top a -> a+lookup i xs = runIdentity (lookupM i xs)++lookupM :: forall (m :: * -> *) a. Monad m => Word64 -> Top a -> m a+lookupM jx zs = look zs jx+  where look Nil _ = fail "RandList.lookup bad subscript"+        look (Cons j t xs) i+            | i < j     = lookTree j t i+            | otherwise = look xs (i - j)++        lookTree _ (Leaf x) i+            | i == 0    = return x+            | otherwise = nothing+        lookTree j (Node x s t) i+            | i > k  = lookTree k t (i - 1 - k)+            | i /= 0 = lookTree k s (i - 1)+            | otherwise = return x+          where k = half j+        nothing = fail "RandList.lookup: not found"+        --- this wont fly long term++lookupWithDefault :: forall t. t -> Word64 -> Top t -> t+lookupWithDefault d jx zs = look zs jx+  where look Nil _ = d+        look (Cons j t xs) i+            | i < j     = lookTree j t i+            | otherwise = look xs (i - j)++        lookTree _ (Leaf x) i+            | i == 0    = x+            | otherwise = d+        lookTree j (Node x s t) i+            | i > k   = lookTree k t (i - 1 - k)+            | i /= 0  = lookTree k s (i - 1)+            | otherwise = x+          where k = half j++-- | Complexity /O(1)/.+tail :: RAList a -> Maybe (RAList a)+tail = fmap snd . uncons -- XXX Is there some clever way to do this? init :: RAList a -> RAList a init = fromList . Prelude.init . toList@@ -314,12 +398,14 @@ null (RAList s _) = s == 0  -- | Complexity /O(1)/.-length :: RAList a -> Int+length :: RAList a -> Word64 length (RAList s _) = s  map :: (a->b) -> RAList a -> RAList b map = fmap ++ reverse :: RAList a -> RAList a reverse = fromList . Prelude.reverse . toList @@ -378,63 +464,89 @@ minimum xs | null xs   = errorEmptyList "minimum"            | otherwise = foldl1 min xs -replicate :: Int -> a -> RAList a-replicate n = fromList . Prelude.replicate n+replicate :: Word64 -> a -> RAList a+replicate n v = fromList $ Prelude.replicate (fromIntegral n)  v -take :: Int -> RAList a -> RAList a-take n = fromList . Prelude.take n . toList+take :: Word64 -> RAList a -> RAList a+take n ls | n < fromIntegral (maxBound :: Int) = fromList $  Prelude.take (fromIntegral n) $ toList ls+          | otherwise = ls --- | Complexity /O(log n)/.-drop :: Int -> RAList a -> RAList a+-- | drop i l+-- @`drop` i l@ where l has length n has worst case complexity  Complexity /O(log n)/, Average case+-- complexity should be /O(min(log i, log n))/.+drop :: Word64 -> RAList a -> RAList a drop n xs | n <= 0 = xs-drop n xs@(RAList s _) | n >= s = empty+drop n _xs@(RAList s _) | n >= s = empty drop n (RAList s wts) = RAList (s-n) (loop n wts)   where loop 0 xs = xs-        loop n (Cons w _ xs) | w <= n = loop (n-w) xs-        loop n (Cons w (Node _ l r) xs) = loop (n-1) (Cons w2 l (Cons w2 r xs)) where w2 = w `quot` 2+        loop m (Cons w _ xs) | w <= m = loop (m-w) xs -- drops full trees+        loop m (Cons w tre xs) = splitTree m w tre xs -- splits tree         loop _ _ = error "Data.RAList.drop: impossible" -splitAt :: Int -> RAList a -> (RAList a, RAList a)+-- helper function for drop+-- drops the first n elements of the tree and adds them to the front+splitTree :: Word64 -> Word64 -> Tree a -> Top a -> Top a+splitTree n treeSize tree@(Node _ l r) xs =+    case (compare n  1, n <= halfTreeSize) of+      (GT {- n==0 -}, _ )  -> Cons treeSize tree xs+      (EQ {- n==1 -}, _ ) -> Cons halfTreeSize l (Cons halfTreeSize r xs)+      (_, True ) -> splitTree (n-1) halfTreeSize l (Cons halfTreeSize r xs)+      (_, False) -> splitTree (n-halfTreeSize-1) halfTreeSize r xs+  where halfTreeSize = treeSize `quot` 2+splitTree n treeSize nd@(Leaf _) xs =+  case compare n 1 of+    EQ {-1-} -> xs+    LT {-0-}-> Cons treeSize nd xs+    GT {- > 1-} -> error "drop invariant violated, must be smaller than current tree"+++++-- Old version of drop+-- worst case complexity /O(n)/+simpleDrop :: Word64 -> RAList a -> RAList a+simpleDrop n xs | n <= 0 = xs+simpleDrop n _xs@(RAList s _) | n >= s = empty+simpleDrop n (RAList s wts) = RAList (s-n) (loop n wts)+    where loop 0 xs = xs+          loop n1 (Cons w _ xs) | w <= n1 = loop (n1-w) xs+          loop n2 (Cons w (Node _ l r) xs) = loop (n2-1) (Cons w2 l (Cons w2 r xs))+            where w2 = w `quot` 2+          loop _ _ = error "Data.RAList.drop: impossible"+++splitAt :: Word64 -> RAList a -> (RAList a, RAList a) splitAt n xs = (take n xs, drop n xs)  elem :: (Eq a) => a -> RAList a -> Bool elem x = any (== x)  notElem :: (Eq a) => a -> RAList a -> Bool-notElem x = any (/= x)+notElem x = not . elem x -- aka all (/=) -lookup :: (Eq a) => a -> RAList (a, b) -> Maybe b-lookup x xys = Prelude.lookup x (toList xys)+-- naive list based lookup+lookupL :: (Eq a) => a -> RAList (a, b) -> Maybe b+lookupL x xys = Prelude.lookup x (toList xys)  filter :: (a->Bool) -> RAList a -> RAList a filter p xs =-    if null xs then-        empty-    else-        let x = head xs-            ys = filter p (tail xs)-        in  if p x then x `cons` ys else ys+    case uncons xs of+      Nothing -> empty+      Just(h,tl) ->+        let+           ys = filter p tl+        in+           if p h then h `cons` ys else  ys + partition :: (a->Bool) -> RAList a -> (RAList a, RAList a) partition p xs = (filter p xs, filter (not . p) xs) --- | Complexity /O(log n)/.-(!!) :: RAList a -> Int -> a-RAList s wts !! n | n <  0 = error "Data.RAList.!!: negative index"-                  | n >= s = error "Data.RAList.!!: index too large"-                  | otherwise = ix n wts-  where ix n (Cons w t wts') | n < w     = ixt n (w `quot` 2) t-                             | otherwise = ix (n-w) wts'-        ix _ _ = error "Data.RAList.!!: impossible"-        ixt 0 0 (Leaf x) = x-        ixt 0 _ (Node x l r) = x-        ixt n w (Node x l r) | n <= w    = ixt (n-1)   (w `quot` 2) l-                             | otherwise = ixt (n-1-w) (w `quot` 2) r-        ixt n w _ = error "Data.RAList.!!: impossible"  + zip :: RAList a -> RAList b -> RAList (a, b)-zip = zipWith (,)        +zip = zipWith (,)  zipWith :: (a->b->c) -> RAList a -> RAList b -> RAList c zipWith f xs1@(RAList s1 wts1) xs2@(RAList s2 wts2)@@ -444,7 +556,7 @@         zipTree (Node x1 l1 r1) (Node x2 l2 r2) = Node (f x1 x2) (zipTree l1 l2) (zipTree r1 r2)         zipTree _ _ = error "Data.RAList.zipWith: impossible"         zipTop Nil Nil = Nil-        zipTop (Cons w t1 xs1) (Cons _ t2 xs2) = Cons w (zipTree t1 t2) (zipTop xs1 xs2)+        zipTop (Cons w t1 xss1) (Cons _ t2 xss2) = Cons w (zipTree t1 t2) (zipTop xss1 xss2)         zipTop _ _ = error "Data.RAList.zipWith: impossible"  unzip :: RAList (a, b) -> (RAList a, RAList b)@@ -452,22 +564,22 @@  -- | Change element at the given index. -- Complexity /O(log n)/.-update :: Int -> a -> RAList a -> RAList a+update :: Word64 -> a -> RAList a -> RAList a update i x = adjust (const x) i  -- | Apply a function to the value at the given index. -- Complexity /O(log n)/.-adjust :: (a->a) -> Int -> RAList a -> RAList a+adjust :: (a->a) -> Word64 -> RAList a -> RAList a adjust f n (RAList s wts) | n <  0 = error "Data.RAList.adjust: negative index"                           | n >= s = error "Data.RAList.adjust: index too large"                           | otherwise = RAList s (adj n wts)-  where adj n (Cons w t wts') | n < w     = Cons w (adjt n (w `quot` 2) t) wts'-                              | otherwise = Cons w t (adj (n-w) wts')-        adj _ _ = error "Data.RAList.adjust: impossible"+  where adj j (Cons w t wts') | j < w     = Cons w (adjt j (w `quot` 2) t) wts'+                              | otherwise = Cons w t (adj (j-w) wts')+        adj j _ = error ("Data.RAList.adjust: impossible Nil element: " <> show j)         adjt 0 0 (Leaf x) = Leaf (f x)         adjt 0 _ (Node x l r) = Node (f x) l r-        adjt n w (Node x l r) | n <= w    = Node x (adjt (n-1) (w `quot` 2) l) r-                              | otherwise = Node x l (adjt (n-1-w) (w `quot` 2) r)+        adjt j w (Node x l r) | j <= w    = Node x (adjt (j-1) (w `quot` 2) l) r+                              | otherwise = Node x l (adjt (j-1-w) (w `quot` 2) r)         adjt _ _ _ = error "Data.RAList.adjust: impossible"  -- XXX Make this a good producer

@@ -0,0 +1,63 @@++module Main where+import Criterion.Main+import Data.RAList++hundred :: RAList Int+hundred = fromList [0..100]++thousand :: RAList Int+thousand = fromList [0..1000]++tenThousand :: RAList Int+tenThousand = fromList [0..10000]++hundredThousand :: RAList Int+hundredThousand = fromList [0..100000]++million :: RAList Int+million = fromList [0..1000000]++tenMillion :: RAList Int+tenMillion = fromList [0..10000000]++main = defaultMain [+    bgroup "drop"+        [ bench "TenThousand" $ whnf (Data.RAList.drop 100) tenThousand,+          bench "HundredThousand" $ whnf (Data.RAList.drop 100) hundredThousand,+          bench "Million" $ whnf (Data.RAList.drop 100) million,+          bench "TenMillion" $ whnf (Data.RAList.drop 100) tenMillion,++          bench "TenThousand-Drop1" $ whnf (Data.RAList.drop 1) tenThousand,+          bench "HundredThousand-Drop1" $ whnf (Data.RAList.drop 1) hundredThousand,+          bench "Million-Drop1" $ whnf (Data.RAList.drop 1) million,+          bench "TenMillion-Drop1" $ whnf (Data.RAList.drop 1) tenMillion+        ],++    bgroup "simpleDrop"+        [ bench "TenThousand" $ whnf (Data.RAList.simpleDrop 100) tenThousand,+          bench "HundredThousand" $ whnf (Data.RAList.simpleDrop 100) hundredThousand,+          bench "Million" $ whnf (Data.RAList.simpleDrop 100) million,+          bench "TenMillion" $ whnf (Data.RAList.simpleDrop 100) tenMillion,++          bench "TenThousand-Drop1" $ whnf (Data.RAList.simpleDrop 1) tenThousand,+          bench "HundredThousand-Drop1" $ whnf (Data.RAList.simpleDrop 1) hundredThousand,+          bench "Million-Drop1" $ whnf (Data.RAList.simpleDrop 1) million,+          bench "TenMillion-Drop1" $ whnf (Data.RAList.simpleDrop 1) tenMillion+        ],++    bgroup "cons"+        [ bench "hundred" $ whnf (Data.RAList.cons 0) hundred,+          bench "thousand" $ whnf (Data.RAList.cons 0) thousand+        ],++    bgroup "uncons"+        [ bench "hundred" $ whnf Data.RAList.uncons hundred,+          bench "thousand" $ whnf Data.RAList.uncons thousand+        ],+    bgroup "lookup last element"+        [ bench "TenThousand" $ whnf  (tenThousand Data.RAList.!!) 10000,+          bench "HundredThousand" $ whnf (hundredThousand Data.RAList.!!) 100000,+          bench "Million" $ whnf (million Data.RAList.!!) 1000000,+          bench "TenMillion" $ whnf (tenMillion Data.RAList.!!) 10000000+        ] ]

@@ -1,9 +1,9 @@ Name:           ralist-Cabal-Version:  >= 1.2-Version:        0.1.0.0+Cabal-Version:  >= 1.20+Version:        0.2.0.0 License:        BSD3-Author:         Lennart Augustsson-Maintainer:     Lennart Augustsson+Author:         Lennart Augustsson, Carter Schonwald+Maintainer:     Carter Schonwald Category:       Data Structures Synopsis:       Random access list with a list compatible interface. Stability:      experimental@@ -12,7 +12,57 @@                 Random access list have same complexity as lists with some exceptions,                 the notable one being that (!!) is O(log n) instead of O(n).                 RALists have to be finite.+-- URL for the project homepage or repository.+homepage:            http://github.com/cartazio/ralist +source-repository head+  type: git+  location: https://github.com/cartazio/ralist.git+++-- You can disable the hunit test suite with -f-test-hunit+flag test-hspec+  default: True+  manual: True+ Library   Build-Depends: base >= 3 && < 6   Exposed-modules:      Data.RAList+  ghc-options: -Wall -O2+  default-language: Haskell2010+  -- Build-depends: semigroups == 0.18.*+  if impl(ghc >= 8.0)+    ghc-options: -Wcompat -Wnoncanonical-monad-instances -Wnoncanonical-monadfail-instances+  else+    -- provide/emulate `Control.Monad.Fail` and `Data.Semigroups` API for pre-GHC8+    build-depends: fail == 4.9.*, semigroups == 0.18.*++test-suite hspec+  type: exitcode-stdio-1.0++  main-is: hspec.hs+  default-language: Haskell2010+  ghc-options: -w -threaded -rtsopts -with-rtsopts=-N+  hs-source-dirs: tests++  if !flag(test-hspec)+    buildable: False+  else+    build-depends:+      base,+      ralist,+      hspec >= 2.2 && < 2.3+++benchmark benchmarking+  type: exitcode-stdio-1.0+  main-is: benchmarking.hs+  default-language: Haskell2010+  hs-source-dirs: benchmark+  ghc-options: -O2++  build-depends:+      base,+      ralist,+      criterion,+      deepseq

@@ -0,0 +1,708 @@+module Main where++import Data.RAList+import Test.Hspec+import Control.Exception (evaluate)+++main = hspec $ do+  describe "RAList.cons" $ do+    it "adds to an empty list" $ do+      cons 1 empty `shouldBe` (fromList [1] :: RAList Int)+    it "adds to a list of length 1" $ do+      cons 1 (fromList [2]) `shouldBe` (fromList [1,2] :: RAList Int)+    it "add to a list of length 10" $ do+      cons 1 (fromList [2..11]) `shouldBe`+        (fromList [1..11] :: RAList Int)+++  describe "RAList.uncons" $ do+    it "deletes the first element of a list of length 1" $ do+      uncons (fromList ['a']) `shouldBe`+        (Just ('a',(fromList [])) :: Maybe (Char, RAList Char))+    it "deletes the first element of a list of length 3" $ do+      uncons (fromList ['a'..'c']) `shouldBe`+        (Just ('a',(fromList ['b','c'])) :: Maybe (Char, RAList Char))+    it "returns Nothing when it uncons from an empty list" $ do+      (uncons empty :: Maybe (Char, RAList Char)) `shouldBe`+        (Nothing :: Maybe (Char, RAList Char))++  describe "RAList.head" $ do -- This is a Maybe+    it "gets the first element of a list of length 1" $ do+      (Data.RAList.head (fromList [1 :: Int ]) ) `shouldBe` Just 1+    it "gets the first element of a list of length 3" $ do+      (Data.RAList.head (fromList [1 .. 3 :: Int ])) `shouldBe` Just 1+    it "gets the first element of a list of length 9" $ do+      (Data.RAList.head (fromList [1 .. 9 :: Int])) `shouldBe` Just 1+    it "gets nothing if the list is empty" $ do+      Data.RAList.head (fromList ([] :: [Int])) `shouldBe` Nothing++  describe "RAList.last" $ do -- This is not a Maybe+    it "gets the last element of a list of length 1" $ do+       (Data.RAList.last (fromList [1]) ) `shouldBe`+        (1 :: Integer)+    it "gets the last element of a list of length 3" $ do+      Data.RAList.last (fromList [1..3]) `shouldBe`+        (3 :: Integer)+    it "gets the last element of a list of length 9" $ do+      Data.RAList.last (fromList [1..9]) `shouldBe`+        (9 :: Integer)+    it "gets nothing if the list is empty" $ do+      evaluate (Data.RAList.last empty) `shouldThrow` anyException++  describe "RAList.tail" $ do -- This is a Maybe+    it "gets everything after the first element of a list of length 1" $ do+      (Data.RAList.tail (fromList [1]) ) `shouldBe`+        (Just (fromList []) :: Maybe (RAList Integer))+    it "gets everything after the first element of a list of length 3" $ do+      (Data.RAList.tail (fromList [1..3])) `shouldBe`+        (Just (fromList [2,3]) :: Maybe (RAList Integer))+    it "gets everything after the first element of a list of length 9" $ do+      (Data.RAList.tail (fromList [1..9])) `shouldBe`+        (Just (fromList [2..9]) :: Maybe (RAList Integer))+    it "gets nothing if the list is empty" $ do+      Data.RAList.tail empty `shouldBe` (Nothing :: Maybe (RAList Integer))++  describe "RAList.init" $ do -- This is not a Maybe+    it "gets everything before the last element of a list of length 1" $ do+       (Data.RAList.init (fromList [1]) ) `shouldBe` (fromList [] :: RAList Integer)+    it "gets everything but the last element of a list of length 3" $ do+      Data.RAList.init (fromList [1..3]) `shouldBe` (fromList [1,2] :: RAList Integer)+    it "gets everything but the last element of a list of length 9" $ do+      Data.RAList.init (fromList [1..9]) `shouldBe` (fromList [1..8] :: RAList Integer)++    it "gets nothing if the list is empty" $ do+      evaluate (Data.RAList.init empty) `shouldThrow` anyException++  describe "RAList.null" $ do+    it "returns True if it is given an empty list" $ do+      Data.RAList.null empty `shouldBe` (True :: Bool)+    it "return False if it is given a non-empty list" $ do+      Data.RAList.null (fromList [1]) `shouldBe` (False :: Bool)++  describe "RAList.length" $ do+    it "returns 0 if the list is empty" $ do+      Data.RAList.length empty `shouldBe` 0+    it "returns 1 if the list has length 1" $ do+      Data.RAList.length (fromList [1]) `shouldBe` 1+    it "returns 3 if the list has lenght 3"$ do+      Data.RAList.length (fromList [1..3]) `shouldBe` 3+    it "returns 9 if the list has length 9" $ do+      Data.RAList.length (fromList [1..9]) `shouldBe`  9++  describe "RAList.lookupL" $ do+    describe "for a list of length 1" $ do+      let ra = fromList [('a','b')]+      it "returns the first value correctly" $ do+        lookupL 'a' ra `shouldBe` (Just 'b' :: Maybe Char)+      it "returns Nothing for a nonexistent key value" $ do+        lookupL 'z' ra `shouldBe` (Nothing :: Maybe Char)+    describe "for a list of length 3" $ do+      let ra = fromList [('a','b'),('c','d'),('e','f')]+      it "returns the first value correctly" $ do+        lookupL 'a' ra `shouldBe` (Just 'b':: Maybe Char)+      it "returns the last value correctly" $ do+        lookupL 'e' ra `shouldBe` (Just 'f':: Maybe Char)+      it "returns the middle value correctly" $ do+        lookupL 'c' ra `shouldBe` (Just 'd':: Maybe Char)+      it "returns Nothing for a nonexistent key value" $ do+        lookupL 'z' ra `shouldBe` (Nothing :: Maybe Char)+    describe "for a list of length 9" $ do+      let ra = fromList [('a','b'),('c','d'),('e','f'),('g','h'),('i','j'),('k','l'),('m','n'),('o','p'),('q','r')]+      it "returns the first value correctly" $ do+        lookupL 'a' ra `shouldBe` (Just 'b':: Maybe Char)+      it "returns the second value correctly" $ do+        lookupL 'c' ra `shouldBe` (Just 'd':: Maybe Char)+      it "returns the third value correctly" $ do+        lookupL 'e' ra `shouldBe` (Just 'f':: Maybe Char)+      it "returns the fourth value correctly" $ do+        lookupL 'g' ra `shouldBe` (Just 'h':: Maybe Char)+      it "returns the last value correctly" $ do+        lookupL 'q' ra `shouldBe` (Just 'r':: Maybe Char)+      it "returns Nothing for a nonexistent key value" $ do+        lookupL 'z' ra `shouldBe` (Nothing :: Maybe Char)+    describe "for an empty list" $ do+      it "return Nothing when called with an empty list" $ do+        lookupL 'a' empty `shouldBe` (Nothing :: Maybe Char)++  describe "RAList.map" $ do+    describe "for a list of length 1" $ do+      it "maps from Int to Int"$ do+        Data.RAList.map (\x -> 2*x) (fromList [1])  `shouldBe`+          (fromList [2] :: RAList Int)+      it "maps from Int to String" $ do+        Data.RAList.map (\x -> 'a') (fromList [1]) `shouldBe`+          (fromList ['a'] :: RAList Char)+      it "maps from Char to Int" $ do+        Data.RAList.map (\x -> 1) (fromList ['a']) `shouldBe`+          (fromList [1] :: RAList Int)+      it "maps from Int to [Int]" $ do+        Data.RAList.map (\x -> [x]) (fromList [1]) `shouldBe`+          (fromList [[1]] :: RAList [Int])+      it "maps from [Int] to Int" $ do+        Data.RAList.map (\x -> x Prelude.!! 0)+          ((fromList [[1]]) :: RAList [Int])+          `shouldBe` (fromList [1] :: RAList Int)+    describe "for a list of length 3" $ do+      it "maps from Int to Int" $ do+        Data.RAList.map (\x -> 2*x) (fromList [1..3]) `shouldBe`+          (fromList [2,4,6] :: RAList Int)+    describe "for a list of length 9" $ do+      it "maps from Int to Int" $ do+        Data.RAList.map (\x -> 2*x) (fromList [1..9])+          `shouldBe`+          ((fromList [2,4..18]) :: RAList Int)+    describe "for an empty list" $ do+      it "returns an empty list of correct type" $ do+        Data.RAList.map (\x -> 'a') empty `shouldBe`+          (empty :: RAList Char)++  describe "RAList.reverse" $ do+    it "does nothing to a list of length 1" $ do+      Data.RAList.reverse (fromList [1]) `shouldBe`+        (fromList [1] :: RAList Int)+    it "reverses a list of length 3" $ do+      Data.RAList.reverse (fromList [1..3]) `shouldBe`+        (fromList [3,2,1] :: RAList Int)+    it "reverse a list of length 9" $ do+      Data.RAList.reverse (fromList [1..9]) `shouldBe`+        (fromList [9,8..1] :: RAList Int)+    it "does nothing to an empty list" $ do+      Data.RAList.reverse (empty :: RAList Int) `shouldBe`+        (empty :: RAList Int)++  -- Only tests for one list length because it immediately turns the RALists+  -- into standard lists with 'toList', which is tested elsewhere+  describe "folds" $ do+    let rai = fromList [1..3]+    let ras = fromList ["a","b","c"]+    describe "RAList.foldl" $ do+      it "adds Ints in a list" $ do+        Data.RAList.foldl (+) 0 rai `shouldBe` (6 :: Int)+      it "subtracts Ints in a list" $ do+        Data.RAList.foldl (-) 0 rai `shouldBe` ((-6) :: Int)+      it "concatenates Strings in a list" $ do+        Data.RAList.foldl (Prelude.++) "" ras `shouldBe`+          ("abc" :: [Char])+    describe "RAList.foldl1" $  do+      it "adds Ints in a list" $ do+        Data.RAList.foldl1 (+) rai `shouldBe` (6 :: Int)+      it "subtracts Ints in a list" $ do+        Data.RAList.foldl1 (-) rai `shouldBe` ((-4) :: Int)+      it "concatenates Strings in a list" $ do+        Data.RAList.foldl1 (Prelude.++) ras `shouldBe`+          ("abc" :: [Char])+    describe "RAList.foldr" $ do+      it "adds Ints in a list" $ do+        Data.RAList.foldr (+) 0 rai `shouldBe` (6 :: Int)+      it "subtracts Ints in a list" $ do+        Data.RAList.foldr (-) 0 rai `shouldBe` (2 :: Int)+      it "concatenates Strings in a list" $ do+        Data.RAList.foldr (Prelude.++) "" ras `shouldBe`+          ("abc" :: [Char])+    describe "RAList.foldr1" $ do+      it "adds Ints in a list" $ do+        Data.RAList.foldr1 (+) rai `shouldBe` (6 :: Int)+      it "subtracts Ints in a list" $ do+        Data.RAList.foldr1 (-) rai `shouldBe` (2 :: Int)+      it "concatenates characters in a list" $ do+        Data.RAList.foldr1 (Prelude.++) ras `shouldBe`+          ("abc" :: [Char])++  describe "RAList.concat" $ do+    it "concatenates list of empty lists" $ do+      Data.RAList.concat (fromList [empty, empty]) `shouldBe`+        (empty :: RAList Integer)+    it "concatenates an empty list" $ do+      Data.RAList.concat empty `shouldBe` (empty :: RAList Integer)+    it "concatenates lists of the same length" $ do+      Data.RAList.concat+        (fromList [fromList [1,2], fromList [1,2], fromList [1,2]])+        `shouldBe` (fromList [1,2,1,2,1,2] :: RAList Int)+    it "concatenates lists of different lengths" $ do+      Data.RAList.concat+        (fromList [fromList [], fromList [1], fromList [1,2],+          fromList [1..3], fromList [1..9]])+        `shouldBe`+        (fromList [1,1,2,1,2,3,1,2,3,4,5,6,7,8,9] :: RAList Int)++  describe "RAList.concatMap" $ do+    describe "for lists of length 1" $ do+       it "maps (x -> [x]) on a list of integers" $ do+         Data.RAList.concatMap (\x -> fromList [x])+           (fromList [1]) `shouldBe`+           (fromList [1] :: RAList Int)+       it "maps (x -> [1, length x]) on a list of Strings" $ do+         Data.RAList.concatMap+           (\x -> fromList [1, (Prelude.length x)])+           (fromList ["abc"]) `shouldBe`+           (fromList [1,3] :: RAList Int)+       it "returns an empty list when it maps to an empty list" $ do+         Data.RAList.concatMap+           (\x -> empty) (fromList [1]) `shouldBe`+           (fromList [] :: RAList Int)+    describe "for lists of length 3" $ do+      it "maps (x -> [x]) on a list of integers" $ do+        Data.RAList.concatMap (\x -> fromList [x])+          (fromList [1..3]) `shouldBe`+          (fromList [1..3] :: RAList Int)+      it "maps (x -> [1, length x]) on a list of Strings" $ do+        Data.RAList.concatMap+          (\x -> fromList [1, (Prelude.length x)])+          (fromList ["a","ab", "abc"]) `shouldBe`+          (fromList [1,1,1,2,1,3] :: RAList Int)+      it "returns an empty list when it maps to an empty list" $ do+        Data.RAList.concatMap+          (\x -> empty) (fromList [1..3]) `shouldBe`+          (fromList [] :: RAList Int)+    describe "for lists of length " $ do+        it "maps (x -> [x]) on a list of integers" $ do+          Data.RAList.concatMap (\x -> fromList [x])+            (fromList [1..9]) `shouldBe`+            (fromList [1..9] :: RAList Int)+        it "maps (x -> [1, length x]) on a list of Strings" $ do+          Data.RAList.concatMap+            (\x -> fromList [1, (Prelude.length x)])+            (fromList ["a","ab", "abc","a","a","a","a","a","abcd"])+            `shouldBe`+            (fromList [1,1,1,2,1,3,1,1,1,1,1,1,1,1,1,1,1,4]+            :: RAList Int)+        it "returns an empty list when it maps to an empty list" $ do+          Data.RAList.concatMap+            (\x -> empty) (fromList [1..9]) `shouldBe`+            (fromList [] :: RAList Int)++  describe "logic functions" $ do+    describe "Data.RAList.and" $ do+      it "returns False when first value is False" $ do+        Data.RAList.and+          (fromList [False, True, True, True, True, True, True, True,+          True])+          `shouldBe` (False :: Bool)+      it "returns False when last value is True" $ do+        Data.RAList.and+           (fromList [True, True, True, True, True, True, True,+          True, False])+          `shouldBe` (False :: Bool)+      it "returns False when the only value is False" $ do+        Data.RAList.and+          (fromList [False, False, False, False, False, False, False,+          False, False])+          `shouldBe` (False :: Bool)+      it "returns False with a list of length one containing False" $ do+        Data.RAList.and (fromList [False]) `shouldBe` (False :: Bool)+      it " returns True with a list of length one containing True" $ do+        Data.RAList.and (fromList [True]) `shouldBe` (True :: Bool)+      it "returns True when the only value is True" $ do+        Data.RAList.and+          (fromList [True, True, True, True, True, True, True, True,+          True])+          `shouldBe` (True :: Bool)+      it "returns True for an empty list" $ do+        Data.RAList.and empty `shouldBe` (True :: Bool)+    describe "Ralist.or" $ do+      it "returns True when first value is True" $ do+        Data.RAList.or+          (fromList [True, False, False, False, False, False, False,+          False, False])+          `shouldBe` (True :: Bool)+      it "returns True when last value is True" $ do+        Data.RAList.or+          (fromList [False, False, False, False, False, False, False,+          False, True])+        `shouldBe` (True :: Bool)+      it "returns False when the only value is False" $ do+        Data.RAList.or+          (fromList [False, False, False, False, False, False, False,+          False, False])+          `shouldBe` (False :: Bool)+      it "returns False with a list of length one containing False" $ do+        Data.RAList.or (fromList [False]) `shouldBe` (False :: Bool)+      it " returns True with a list of length one containing True" $ do+        Data.RAList.or (fromList [True]) `shouldBe` (True :: Bool)+      it "returns True when the only value is True" $ do+        Data.RAList.or+          (Data.RAList.replicate 9 True)+          `shouldBe` (True :: Bool)+      it "returns False for an empty list" $ do+        Data.RAList.or empty `shouldBe` (False :: Bool)+    describe "RAList.any" $ do+      it "returns True when first value evaluates to True" $ do+        Data.RAList.any (\x -> x)+          (fromList [True, False, False, False, False, False, False,+          False, False])+          `shouldBe` (True :: Bool)+      it "returns True when last value is True" $ do+        Data.RAList.any  (\x -> x)+          (fromList [False, False, False, False, False, False, False,+          False, True])+        `shouldBe` (True :: Bool)+      it "returns False when the only value is False" $ do+        Data.RAList.any  (\x -> x)+          (Data.RAList.replicate 9 False)+          `shouldBe` (False :: Bool)+      it "returns False with a list of length one containing False" $ do+        Data.RAList.any (\x -> x) (fromList [False]) `shouldBe`+          (False :: Bool)+      it " returns True with a list of length one containing True" $ do+        Data.RAList.any  (\x -> x) (fromList [True]) `shouldBe` (True :: Bool)+      it "returns True when the only value is True" $ do+        Data.RAList.any  (\x -> x)+          (Data.RAList.replicate 9 True)+          `shouldBe` (True :: Bool)+      it "returns False for an empty list" $ do+        Data.RAList.any (\x -> x) empty `shouldBe` (False :: Bool)+    describe "RAList.all" $ do+       it "returns False when first value evaluates to False" $ do+         Data.RAList.all (\x -> x)+           (fromList [False, True, True, True, True, True, True, True,+           True])+           `shouldBe` (False :: Bool)+       it "returns False when last value evaluates to False" $ do+         Data.RAList.all (\x -> x)+            (fromList [True, True, True, True, True, True, True,+           True, False])+           `shouldBe` (False :: Bool)+       it "returns False when the only value evaluates to False" $ do+         Data.RAList.all (\x -> x)+          (Data.RAList.replicate 9 False)+           `shouldBe` (False :: Bool)+       it "returns False with a list of one value which evaluates to False"+        $ do+         Data.RAList.all (\x -> x) (fromList [False]) `shouldBe` (False :: Bool)+       it " returns True with a list of one value which evaluates to True"+        $ do+         Data.RAList.all (\x -> x) (fromList [True]) `shouldBe` (True :: Bool)+       it "returns True when the only value evaluates to True" $ do+         Data.RAList.all (\x -> x)+           (Data.RAList.replicate 9 True)+           `shouldBe` (True :: Bool)+       it "returns True for an empty list" $ do+         Data.RAList.all (\x -> x) empty `shouldBe` (True :: Bool)++  describe "Math operations" $ do+    describe "RAList.sum" $ do+      it "adds all ints in a list of length 1" $ do+        Data.RAList.sum (fromList [3]) `shouldBe` (3 :: Int)+      it "adds all ints in a list of length 3" $ do+        Data.RAList.sum (fromList [1,1,1]) `shouldBe` (3 :: Int)+      it "adds all ints in a list of length 9" $ do+        Data.RAList.sum (Data.RAList.replicate 9 1) `shouldBe` (9 :: Int)+      it "returns 0 when given an empty list" $ do+        Data.RAList.sum empty `shouldBe` (0 :: Int)+    describe "RAList.product" $ do+      it "multiplies all ints in a list of length 1" $ do+        Data.RAList.product (fromList [3]) `shouldBe` (3 :: Int)+      it "multiplies all ints in a list of length 3" $ do+        Data.RAList.product (fromList [2,2,2]) `shouldBe` (8 :: Int)+      it "multiplies all ints in a list of length 9" $ do+        Data.RAList.product (Data.RAList.replicate 9 2) `shouldBe`+          (512 :: Int)+      it "returns 1 when given an empty list" $ do+        Data.RAList.product empty `shouldBe` (1 :: Int)++  describe "extrema" $ do+    describe "RAList.maximum" $ do+      describe "for list of length 1" $ do+        it "returns the value" $ do+          Data.RAList.maximum (fromList [1]) `shouldBe` (1 :: Int)+      describe "for a list of length 3" $ do+        it "can return the first value" $ do+          Data.RAList.maximum (fromList [3,1,2]) `shouldBe` (3 :: Int)+        it "can return the last value" $ do+          Data.RAList.maximum (fromList [1..3]) `shouldBe` (3 :: Int)+      describe "for a list of length 9" $ do+        let ra = fromList [1..9]+        it "can return the first value" $ do+          Data.RAList.maximum (update 0 10 ra) `shouldBe` (10 :: Int)+        it "can return the second value" $ do+          Data.RAList.maximum (update 1 10 ra) `shouldBe` (10 :: Int)+        it "can return the third value" $ do+          Data.RAList.maximum (update 2 10 ra) `shouldBe` (10 :: Int)+        it "can return the fourth value" $ do+          Data.RAList.maximum (update 3 10 ra) `shouldBe` (10 :: Int)+        it "can return the last value" $ do+          -- Specifies the list rather than updating the last value+          -- because update is currently broken+          Data.RAList.maximum (fromList [1,2,3,4,5,6,7,8,10]) `shouldBe`+            (10 :: Int)+      describe "for an empty list" $ do+        it "throws an exception" $ do+          evaluate (Data.RAList.maximum (empty :: RAList Int)) `shouldThrow`+            anyException+  describe "RAList.minimum" $ do+    describe "other" $ do+      describe "for list of length 1" $ do+        it "returns the value" $ do+          Data.RAList.minimum (fromList [1]) `shouldBe` (1 :: Int)+      describe "for a list of length 3" $ do+        it "can return the first value" $ do+          Data.RAList.minimum (fromList [1,3,2]) `shouldBe` (1 :: Int)+        it "can return the last value" $ do+          Data.RAList.minimum (fromList [3,2,1]) `shouldBe` (1 :: Int)++      describe "for a list of length 9" $ do+        let ra = fromList [1..9]+        it "can return the first value" $ do+          Data.RAList.minimum (update 0 0 ra) `shouldBe` (0 :: Int)+        it "can return the second value" $ do+          Data.RAList.minimum (update 1 0 ra) `shouldBe` (0 :: Int)+        it "can return the third value" $ do+          Data.RAList.minimum (update 2 0 ra) `shouldBe` (0 :: Int)+        it "can return the fourth value" $ do+          Data.RAList.minimum (update 3 0 ra) `shouldBe` (0 :: Int)+        it "can return the last value" $ do+          Data.RAList.minimum (fromList [1,2,3,4,5,6,7,8,0]) `shouldBe`+            (0 :: Int)+      describe "for an empty list" $ do+        it "throws an exception" $ do+          evaluate (Data.RAList.minimum (empty :: RAList Int)) `shouldThrow`+            anyException++  describe "RAList.replicate" $ do+    it "creates an empty list" $ do+      Data.RAList.replicate 0 1 `shouldBe` (empty :: RAList Int)+    it "creates a list of length 1" $ do+      Data.RAList.replicate 1 1 `shouldBe` (fromList [1] :: RAList Int)+    it "creates a list of length 3" $ do+      Data.RAList.replicate 3 1 `shouldBe` (fromList [1,1,1] :: RAList Int)+    it "creates a list of length 9" $ do+      Data.RAList.replicate 9 1 `shouldBe`+        (fromList [1,1,1,1,1,1,1,1,1] :: RAList Int)++  describe "RAList.take" $ do+    let ra = fromList [1..9]+    it "takes the first Data.RAList.element of a list" $ do+      Data.RAList.take  1 ra `shouldBe` (fromList [1] :: RAList Int)+    it "takes the first 2 Data.RAList.elements of a list" $ do+      Data.RAList.take 2 ra `shouldBe` (fromList [1,2] :: RAList Int)+    it "takes the first 3 Data.RAList.elements of a list" $ do+      Data.RAList.take 3 ra `shouldBe` (fromList [1..3] :: RAList Int)+    it "takes the first 4 Data.RAList.elements of a list" $ do+      Data.RAList.take 4 ra `shouldBe` (fromList [1..4] :: RAList Int)+    it "takes all the Data.RAList.elements of a list" $ do+      Data.RAList.take 9 ra `shouldBe` (ra :: RAList Int)+    it "gives an empty list when you Data.RAList.take from an empty list" $ do+      Data.RAList.take 1 empty `shouldBe` (empty :: RAList Int)++  describe "RAList.drop" $ do+    let ra = fromList [1..9]+    it "drops the first Data.RAList.element of a list" $ do+      Data.RAList.drop  1 ra `shouldBe`+        (fromList [2..9] :: RAList Int)+    it "drops the first 2 Data.RAList.elements of a list" $ do+      Data.RAList.drop 2 ra `shouldBe`+        (fromList [3..9] :: RAList Int)+    it "drops the first 3 Data.RAList.elements of a list" $ do+      Data.RAList.drop 3 ra `shouldBe` (fromList [4..9] :: RAList Int)+    it "drops the first 4 Data.RAList.elements of a list" $ do+      Data.RAList.drop 4 ra `shouldBe` (fromList [5..9] :: RAList Int)+    it "drops all the Data.RAList.elements of a list" $ do+      Data.RAList.drop 9 ra `shouldBe` (empty :: RAList Int)+    it "gives an empty list when you drop from an empty list" $ do+      Data.RAList.drop 1 empty `shouldBe` (empty :: RAList Int)++  describe "RAList.splitAt" $ do+    let ra = fromList [1..9]+    it "splitAts the first Data.RAList.element of a list" $ do+      Data.RAList.splitAt  1 ra `shouldBe`+        ((fromList [1], fromList [2..9]) ::+        (RAList Int, RAList Int) )+    it "splitAts the second Data.RAList.element of a list" $ do+      Data.RAList.splitAt 2 ra `shouldBe`+        ((fromList [1,2], fromList [3..9]) ::+        (RAList Int, RAList Int) )+    it "splitAts the third Data.RAList.element of a list" $ do+      Data.RAList.splitAt 3 ra `shouldBe`+        ((fromList [1..3], fromList [4..9]) ::+        (RAList Int, RAList Int) )+    it "splitAts the fourth Data.RAList.element of a list" $ do+      Data.RAList.splitAt 4 ra `shouldBe`+        ((fromList [1..4], fromList [5..9]) ::+        (RAList Int, RAList Int) )+    it "splitAts the last Data.RAList.element of a list" $ do+      Data.RAList.splitAt 9 ra `shouldBe`+        ((ra, empty) :: (RAList Int, RAList Int) )+    it "gives an empty list when you splitAt from an empty list" $ do+      Data.RAList.splitAt 1 empty `shouldBe`+        ((empty, empty) :: (RAList Int, RAList Int) )++  describe "RAList.elem" $ do+    let ra = fromList [1..9]+    it "can find the first Data.RAList.element of a list" $ do+      Data.RAList.elem 1 ra `shouldBe` (True :: Bool)+    it "can find the second Data.RAList.element of a list" $ do+      Data.RAList.elem 2 ra `shouldBe` (True :: Bool)+    it "can find the third Data.RAList.element of a list" $ do+      Data.RAList.elem 3 ra `shouldBe` (True :: Bool)+    it "can find the fourth Data.RAList.element of a list" $ do+      Data.RAList.elem 4 ra `shouldBe` (True :: Bool)+    it "can find the last Data.RAList.element of a list" $ do+      Data.RAList.elem 5 ra `shouldBe` (True :: Bool)+    it "returns false if the Data.RAList.element is not present" $ do+      Data.RAList.elem 10 ra `shouldBe` (False :: Bool)+    it "returns false when given an empty list" $ do+      Data.RAList.elem 1 empty `shouldBe` (False :: Bool)++  describe "RAList.notElem" $ do+    let ra = fromList [1..9]+    it "can find the first Data.RAList.notElement of a list" $ do+      Data.RAList.notElem 1 ra `shouldBe` (False :: Bool)+    it "can find the second Data.RAList.notElement of a list" $ do+      Data.RAList.notElem 2 ra `shouldBe` (False :: Bool)+    it "can find the third Data.RAList.notElement of a list" $ do+      Data.RAList.notElem 3 ra `shouldBe` (False :: Bool)+    it "can find the fourth Data.RAList.notElement of a list" $ do+      Data.RAList.notElem 4 ra `shouldBe` (False :: Bool)+    it "can find the last Data.RAList.notElement of a list" $ do+      Data.RAList.notElem 5 ra `shouldBe` (False :: Bool)+    it "returns false if the Data.RAList.notElement is not present" $ do+      Data.RAList.notElem 10 ra `shouldBe` (True :: Bool)+    it "returns true when give an empty list" $ do+      Data.RAList.notElem 1 empty `shouldBe` (True :: Bool)++  describe "RAList.filter" $ do+    let ra = fromList [1..9]+    it "filters for the first element in a list" $ do+      Data.RAList.filter (\x -> x == 1) ra `shouldBe`+        (fromList [1] :: RAList Int)+    it "filters out the first element in a list" $ do+      Data.RAList.filter (\x -> x > 1) ra `shouldBe`+        (fromList [2..9] :: RAList Int)+    it "filters for the last element in a list" $ do+      Data.RAList.filter (\x -> x == 9) ra `shouldBe`+        (fromList [9] :: RAList Int)+    it "filters out the last element in a list" $ do+      Data.RAList.filter (\x -> x < 9) ra `shouldBe`+        (fromList [1..8] :: RAList Int)+    it "filters for alternating values" $ do+      Data.RAList.filter (\x -> x == 1) (fromList [1,2,1,2,1,2,1,2,1])+        `shouldBe` (fromList [1,1,1,1,1] :: RAList Int)+    it "filters out every value" $ do+      Data.RAList.filter (\x -> False) ra `shouldBe` (empty :: RAList Int)+    it "returns an empty list when given an empty list" $ do+      Data.RAList.filter (\x -> True) empty `shouldBe` (empty :: RAList Int)++  describe "RAList.partition" $ do+    let ra = fromList [1..9]+    it "partitions for the first element in a list" $ do+      Data.RAList.partition (\x -> x == 1) ra `shouldBe`+        ((fromList [1], fromList [2..9]) :: (RAList Int, RAList Int))+    it "partitions out the first element in a list" $ do+      Data.RAList.partition (\x -> x > 1) ra `shouldBe`+        ((fromList [2..9], fromList [1]) :: (RAList Int, RAList Int))+    it "partitions for the last element in a list" $ do+      Data.RAList.partition (\x -> x == 9) ra `shouldBe`+        ((fromList [9], fromList [1..8]) :: (RAList Int, RAList Int))+    it "partitions out the last element in a list" $ do+      Data.RAList.partition (\x -> x < 9) ra `shouldBe`+        ((fromList [1..8], fromList [9]) :: (RAList Int, RAList Int))+    it "partitions for alternating values" $ do+      Data.RAList.partition (\x -> x == 1) (fromList [1,2,1,2,1,2,1,2,1])+        `shouldBe` ((fromList [1,1,1,1,1], fromList [2,2,2,2]) ::+          (RAList Int, RAList Int))+    it "partitions out every value" $ do+      Data.RAList.partition (\x -> False) ra `shouldBe`+        ((empty, ra) :: (RAList Int, RAList Int))+    it "returns an empty list when given an empty list" $ do+      Data.RAList.partition (\x -> True) empty `shouldBe`+        ((empty, empty) :: (RAList Int, RAList Int))++  describe "zip functions" $ do+    let ra1 = (fromList [1..9])+    let ra2 = (fromList ['a','b','c','d','e','f','g','h','i'])+    let ra3 = (fromList ([(1,'a'), (2,'b'), (3,'c'),(4,'d'),(5,'e'),(6,'f'),(7,'g'),(8,'h'),(9,'i')]))+    describe "RAList.zip" $ do+      it "can zip two lists of length 9" $ do+        Data.RAList.zip ra1 ra2 `shouldBe` (ra3 :: RAList (Int, Char))+      it "can zip two lists of length 3" $ do+        Data.RAList.zip (Data.RAList.take 3 ra1) (Data.RAList.take 3 ra2)+        `shouldBe`+          ((Data.RAList.take 3 ra3) :: RAList (Int, Char))+      it "can zip two lists of length 1" $ do+        Data.RAList.zip (Data.RAList.take 1 ra1) (Data.RAList.take 2 ra2)+          `shouldBe`+          (Data.RAList.take 1 ra3 :: RAList (Int,Char))+      it "can zip two lists of different lengths" $ do+        Data.RAList.zip ra1 (Data.RAList.take 5 ra2) `shouldBe`+          (Data.RAList.take 5 ra3 :: RAList (Int, Char))+      it "can zip a list to an empty list" $ do+        Data.RAList.zip empty ra2 `shouldBe`  (empty :: RAList (Int, Char))+      it "can zip two empty lists" $ do+        Data.RAList.zip empty empty `shouldBe` (empty :: RAList (Int, Char))+    describe "RAList.unzip" $ do+      it "can unzip two lists of length 9" $ do+        Data.RAList.unzip ra3 `shouldBe`+          ((ra1,ra2) :: (RAList Int, RAList Char))+      it "can unzip two lists of length 3" $ do+        Data.RAList.unzip (Data.RAList.take 3 ra3) `shouldBe`+          (((Data.RAList.take 3 ra1),(Data.RAList.take 3 ra2)) ::+          (RAList Int, RAList Char))+      it "can unzip two lists of length 1" $ do+        Data.RAList.unzip (Data.RAList.take 1 ra3) `shouldBe`+          (((Data.RAList.take 1 ra1), (Data.RAList.take 1 ra2)) ::+          (RAList Int, RAList Char))+    describe "RAList.zipWith" $ do+      let ra1 = fromList [1..9]+      let ra2 = Data.RAList.replicate 9 1+      let ra3 = fromList [2,3..10]+      let f = (\x y -> x + y)+      it "can zip two lists of length 9" $ do+        Data.RAList.zipWith f ra1 ra2 `shouldBe` (ra3 :: RAList Int)+      it "cannp.zipWith two lists of length 3" $ do+        Data.RAList.zipWith f (Data.RAList.take 3 ra1) (Data.RAList.take 3 ra2)+          `shouldBe`+          ((Data.RAList.take 3 ra3) :: RAList Int)+      it "can zip two lists of length 1" $ do+        Data.RAList.zipWith f (Data.RAList.take 1 ra1) (Data.RAList.take 2 ra2)+          `shouldBe`+          (Data.RAList.take 1 ra3 :: RAList Int)+      it "can zip two lists of different lengths" $ do+        Data.RAList.zipWith f ra1 (Data.RAList.take 5 ra2) `shouldBe`+          (Data.RAList.take 5 ra3 :: RAList Int)+      it "can zip a list to an empty list" $ do+        Data.RAList.zipWith f empty ra2 `shouldBe` (empty :: RAList Int)+      it "can zip two empty lists" $ do+        Data.RAList.zipWith f empty empty `shouldBe`+          (empty :: RAList Int)++  describe "RAList.update" $ do+    let ra3 = fromList [1..3]+    let ra9 = fromList [1..9]+    it "can update the only value in a list" $ do+      Data.RAList.update 0 2 (fromList [1]) `shouldBe`+        (fromList [2] :: RAList Int)+    it "can update the first value in a list of length 3" $ do+      Data.RAList.update 0 4 ra3 `shouldBe` (fromList [4,2,3] :: RAList Int)+    it "can update the last value in a list of length 3" $ do+      Data.RAList.update 2 4 ra3 `shouldBe` (fromList [1,2,4] :: RAList Int)+    it "can update the first value in a list of length 9" $ do+      Data.RAList.update 0 10 ra9 `shouldBe`+        (fromList [10,2,3,4,5,6,7,8,9] :: RAList Int)+    it "can update the second value in a list of length 9" $ do+      Data.RAList.update 1 10 ra9 `shouldBe`+        (fromList [1,10,3,4,5,6,7,8,9] :: RAList Int)+    it "can update the third value in a list of length 9" $ do+      Data.RAList.update 2 10 ra9 `shouldBe`+        (fromList [1,2,10,4,5,6,7,8,9] :: RAList Int)+    it "can update the fourth value in a list of length 9" $ do+      Data.RAList.update 3 10 ra9 `shouldBe`+        (fromList [1,2,3,10,5,6,7,8,9])+    it "can update the last value in a list of length 9" $ do+      Data.RAList.update 8 10 ra9 `shouldBe`+        (fromList [1,2,3,4,5,6,7,8,10])+    it "throws an error when trying to update an index that is too large" $ do+      evaluate (Data.RAList.update 10 10 ra9 )`shouldThrow` anyException+    it "throws an error when trying to update an empty list" $ do+      evaluate (Data.RAList.update 0 0 empty) `shouldThrow` anyException++  describe "RAList.toList" $ do+    it "converts a list of length 1" $ do+      toList (fromList [1]) `shouldBe` ([1] :: [Int])+    it "converts a list of length 3" $ do+      toList (fromList[1..3]) `shouldBe` ([1..3] :: [Int])+    it "converts a list of length 9" $ do+      toList (fromList [1..9]) `shouldBe` ([1..9] :: [Int])+    it "converts an empty list" $ do+      toList (empty) `shouldBe` ([] :: [Int])+