rle (empty) → 0.1.0.0
raw patch · 5 files changed
+645/−0 lines, 5 filesdep +QuickCheckdep +basedep +cereal
Dependencies added: QuickCheck, base, cereal, deepseq, portray, portray-diff, rle, test-framework, test-framework-quickcheck2, wrapped
Files
- CHANGELOG.md +4/−0
- LICENSE +202/−0
- rle.cabal +65/−0
- src/Data/RLE.hs +288/−0
- test/RLETest.hs +86/−0
+ CHANGELOG.md view
@@ -0,0 +1,4 @@+# 0.1.0.0++Initial version.+
+ LICENSE view
@@ -0,0 +1,202 @@++ Apache License+ Version 2.0, January 2004+ http://www.apache.org/licenses/++ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION++ 1. Definitions.++ "License" shall mean the terms and conditions for use, reproduction,+ and distribution as defined by Sections 1 through 9 of this document.++ "Licensor" shall mean the copyright owner or entity authorized by+ the copyright owner that is granting the License.++ "Legal Entity" shall mean the union of the acting entity and all+ other entities that control, are controlled by, or are under common+ control with that entity. For the purposes of this definition,+ "control" means (i) the power, direct or indirect, to cause the+ direction or management of such entity, whether by contract or+ otherwise, or (ii) ownership of fifty percent (50%) or more of the+ outstanding shares, or (iii) beneficial ownership of such entity.++ "You" (or "Your") shall mean an individual or Legal Entity+ exercising permissions granted by this License.++ "Source" form shall mean the preferred form for making modifications,+ including but not limited to software source code, documentation+ source, and configuration files.++ "Object" form shall mean any form resulting from mechanical+ transformation or translation of a Source form, including but+ not limited to compiled object code, generated documentation,+ and conversions to other media types.++ "Work" shall mean the work of authorship, whether in Source or+ Object form, made available under the License, as indicated by a+ copyright notice that is included in or attached to the work+ (an example is provided in the Appendix below).++ "Derivative Works" shall mean any work, whether in Source or Object+ form, that is based on (or derived from) the Work and for which the+ editorial revisions, annotations, elaborations, or other modifications+ represent, as a whole, an original work of authorship. For the purposes+ of this License, Derivative Works shall not include works that remain+ separable from, or merely link (or bind by name) to the interfaces of,+ the Work and Derivative Works thereof.++ "Contribution" shall mean any work of authorship, including+ the original version of the Work and any modifications or additions+ to that Work or Derivative Works thereof, that is intentionally+ submitted to Licensor for inclusion in the Work by the copyright owner+ or by an individual or Legal Entity authorized to submit on behalf of+ the copyright owner. For the purposes of this definition, "submitted"+ means any form of electronic, verbal, or written communication sent+ to the Licensor or its representatives, including but not limited to+ communication on electronic mailing lists, source code control systems,+ and issue tracking systems that are managed by, or on behalf of, the+ Licensor for the purpose of discussing and improving the Work, but+ excluding communication that is conspicuously marked or otherwise+ designated in writing by the copyright owner as "Not a Contribution."++ "Contributor" shall mean Licensor and any individual or Legal Entity+ on behalf of whom a Contribution has been received by Licensor and+ subsequently incorporated within the Work.++ 2. Grant of Copyright License. Subject to the terms and conditions of+ this License, each Contributor hereby grants to You a perpetual,+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable+ copyright license to reproduce, prepare Derivative Works of,+ publicly display, publicly perform, sublicense, and distribute the+ Work and such Derivative Works in Source or Object form.++ 3. Grant of Patent License. Subject to the terms and conditions of+ this License, each Contributor hereby grants to You a perpetual,+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable+ (except as stated in this section) patent license to make, have made,+ use, offer to sell, sell, import, and otherwise transfer the Work,+ where such license applies only to those patent claims licensable+ by such Contributor that are necessarily infringed by their+ Contribution(s) alone or by combination of their Contribution(s)+ with the Work to which such Contribution(s) was submitted. If You+ institute patent litigation against any entity (including a+ cross-claim or counterclaim in a lawsuit) alleging that the Work+ or a Contribution incorporated within the Work constitutes direct+ or contributory patent infringement, then any patent licenses+ granted to You under this License for that Work shall terminate+ as of the date such litigation is filed.++ 4. Redistribution. You may reproduce and distribute copies of the+ Work or Derivative Works thereof in any medium, with or without+ modifications, and in Source or Object form, provided that You+ meet the following conditions:++ (a) You must give any other recipients of the Work or+ Derivative Works a copy of this License; and++ (b) You must cause any modified files to carry prominent notices+ stating that You changed the files; and++ (c) You must retain, in the Source form of any Derivative Works+ that You distribute, all copyright, patent, trademark, and+ attribution notices from the Source form of the Work,+ excluding those notices that do not pertain to any part of+ the Derivative Works; and++ (d) If the Work includes a "NOTICE" text file as part of its+ distribution, then any Derivative Works that You distribute must+ include a readable copy of the attribution notices contained+ within such NOTICE file, excluding those notices that do not+ pertain to any part of the Derivative Works, in at least one+ of the following places: within a NOTICE text file distributed+ as part of the Derivative Works; within the Source form or+ documentation, if provided along with the Derivative Works; or,+ within a display generated by the Derivative Works, if and+ wherever such third-party notices normally appear. The contents+ of the NOTICE file are for informational purposes only and+ do not modify the License. You may add Your own attribution+ notices within Derivative Works that You distribute, alongside+ or as an addendum to the NOTICE text from the Work, provided+ that such additional attribution notices cannot be construed+ as modifying the License.++ You may add Your own copyright statement to Your modifications and+ may provide additional or different license terms and conditions+ for use, reproduction, or distribution of Your modifications, or+ for any such Derivative Works as a whole, provided Your use,+ reproduction, and distribution of the Work otherwise complies with+ the conditions stated in this License.++ 5. Submission of Contributions. Unless You explicitly state otherwise,+ any Contribution intentionally submitted for inclusion in the Work+ by You to the Licensor shall be under the terms and conditions of+ this License, without any additional terms or conditions.+ Notwithstanding the above, nothing herein shall supersede or modify+ the terms of any separate license agreement you may have executed+ with Licensor regarding such Contributions.++ 6. Trademarks. This License does not grant permission to use the trade+ names, trademarks, service marks, or product names of the Licensor,+ except as required for reasonable and customary use in describing the+ origin of the Work and reproducing the content of the NOTICE file.++ 7. Disclaimer of Warranty. Unless required by applicable law or+ agreed to in writing, Licensor provides the Work (and each+ Contributor provides its Contributions) on an "AS IS" BASIS,+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or+ implied, including, without limitation, any warranties or conditions+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A+ PARTICULAR PURPOSE. You are solely responsible for determining the+ appropriateness of using or redistributing the Work and assume any+ risks associated with Your exercise of permissions under this License.++ 8. Limitation of Liability. In no event and under no legal theory,+ whether in tort (including negligence), contract, or otherwise,+ unless required by applicable law (such as deliberate and grossly+ negligent acts) or agreed to in writing, shall any Contributor be+ liable to You for damages, including any direct, indirect, special,+ incidental, or consequential damages of any character arising as a+ result of this License or out of the use or inability to use the+ Work (including but not limited to damages for loss of goodwill,+ work stoppage, computer failure or malfunction, or any and all+ other commercial damages or losses), even if such Contributor+ has been advised of the possibility of such damages.++ 9. Accepting Warranty or Additional Liability. While redistributing+ the Work or Derivative Works thereof, You may choose to offer,+ and charge a fee for, acceptance of support, warranty, indemnity,+ or other liability obligations and/or rights consistent with this+ License. However, in accepting such obligations, You may act only+ on Your own behalf and on Your sole responsibility, not on behalf+ of any other Contributor, and only if You agree to indemnify,+ defend, and hold each Contributor harmless for any liability+ incurred by, or claims asserted against, such Contributor by reason+ of your accepting any such warranty or additional liability.++ END OF TERMS AND CONDITIONS++ APPENDIX: How to apply the Apache License to your work.++ To apply the Apache License to your work, attach the following+ boilerplate notice, with the fields enclosed by brackets "[]"+ replaced with your own identifying information. (Don't include+ the brackets!) The text should be enclosed in the appropriate+ comment syntax for the file format. We also recommend that a+ file or class name and description of purpose be included on the+ same "printed page" as the copyright notice for easier+ identification within third-party archives.++ Copyright [yyyy] [name of copyright owner]++ Licensed under the Apache License, Version 2.0 (the "License");+ you may not use this file except in compliance with the License.+ You may obtain a copy of the License at++ http://www.apache.org/licenses/LICENSE-2.0++ Unless required by applicable law or agreed to in writing, software+ distributed under the License is distributed on an "AS IS" BASIS,+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+ See the License for the specific language governing permissions and+ limitations under the License.
+ rle.cabal view
@@ -0,0 +1,65 @@+cabal-version: 1.12++-- This file has been generated from package.yaml by hpack version 0.33.0.+--+-- see: https://github.com/sol/hpack+--+-- hash: 5dd2df18ed4d9085540be3036e2efcf42e04d42f9c0549217d35bbef7e9f9aeb++name: rle+version: 0.1.0.0+synopsis: A data type of run-length-encoded lists+description: Provides an @RLE@ type that stores a sequence of elements in the form of+ length/value pairs, stored in a normal form with no adjacent runs of equal+ values.+category: Data Structures+homepage: https://github.com/google/hs-rle#readme+bug-reports: https://github.com/google/hs-rle/issues+author: Andrew Pritchard <awpr@google.com>+maintainer: Andrew Pritchard <awpr@google.com>+copyright: 2019-2021 Google LLC+license: Apache-2.0+license-file: LICENSE+build-type: Simple+extra-source-files:+ CHANGELOG.md++source-repository head+ type: git+ location: https://github.com/google/hs-rle++library+ exposed-modules:+ Data.RLE+ other-modules:+ Paths_rle+ hs-source-dirs:+ src+ build-depends:+ base >=4.12 && <4.16+ , cereal >=0.5.2 && <0.6+ , deepseq >=1.4 && <1.5+ , portray >=0.1 && <0.2+ , portray-diff >=0.1 && <0.2+ , wrapped >=0.1 && <0.2+ default-language: Haskell2010++test-suite RLE-test+ type: exitcode-stdio-1.0+ main-is: RLETest.hs+ other-modules:+ Paths_rle+ hs-source-dirs:+ test+ build-depends:+ QuickCheck+ , base >=4.12 && <4.16+ , cereal >=0.5.2 && <0.6+ , deepseq >=1.4 && <1.5+ , portray >=0.1 && <0.2+ , portray-diff >=0.1 && <0.2+ , rle+ , test-framework+ , test-framework-quickcheck2+ , wrapped >=0.1 && <0.2+ default-language: Haskell2010
+ src/Data/RLE.hs view
@@ -0,0 +1,288 @@+-- Copyright 2019-2021 Google LLC+--+-- Licensed under the Apache License, Version 2.0 (the "License");+-- you may not use this file except in compliance with the License.+-- You may obtain a copy of the License at+--+-- http://www.apache.org/licenses/LICENSE-2.0+--+-- Unless required by applicable law or agreed to in writing, software+-- distributed under the License is distributed on an "AS IS" BASIS,+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+-- See the License for the specific language governing permissions and+-- limitations under the License.++{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveFunctor #-}+{-# LANGUAGE DeriveFoldable #-}+{-# LANGUAGE DerivingVia #-}+{-# LANGUAGE DeriveAnyClass #-}+{-# LANGUAGE OverloadedStrings #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TupleSections #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE ViewPatterns #-}++-- | A data type of run-length-encoded lists.+--+-- This module is meant to be imported qualified with the exception of the type+-- RLE itself. It exports names that clash with things in Prelude and many+-- other data structure modules.++module Data.RLE+ ( -- * Run-Length Encoded Lists+ RLE+ , toList, fromList, singleton, empty, cons, uncons+ , reverse, splitAt, take, init, null, length, (++)+ , map, mapInvertible, traverse, zipWith+ -- ** Runs+ , Run(..), toRuns, fromRuns, consRun, unconsRun, runs+ ) where++import Prelude hiding+ ( (++), init, length, map, null, reverse+ , splitAt, take, traverse, zipWith+ )+import qualified Prelude as P++import Control.Applicative (Applicative(..))+import Control.Monad (replicateM)+import Data.Coerce (coerce)+import Data.Functor.Contravariant (Contravariant(..))+import Data.Maybe (fromJust)+import Data.Semigroup (Semigroup(stimes))+import Data.Void (absurd)+import GHC.Exts (IsList, IsString(..))+import qualified GHC.Exts (IsList(..))+import GHC.Generics (Generic)+import GHC.Stack (HasCallStack)++import Control.DeepSeq (NFData)+import Data.Portray (Portray(..), Portrayal(..))+import Data.Portray.Diff (Diff(..))+import Data.Serialize (Serialize)+import Data.Wrapped (Wrapped(..))++infixr 5 :><+-- | @n :>< x@ denotes a sequence of @n@ copies of @x@, as part of an 'RLE'.+data Run a = Int :>< a+ deriving stock (Eq, Show, Generic, Functor)+ deriving anyclass (NFData, Serialize)+ deriving (Portray, Diff) via Wrapped Generic (Run a)++instance Foldable Run where foldMap f (n :>< x) = stimes n (f x)++-- | After all, why not?+--+-- This is basically Writer (Product Int).+instance Applicative Run where+ pure = (1 :><)+ liftA2 f (m :>< x) (n :>< y) = m*n :>< f x y+ (m :>< f) <*> (n :>< x) = m*n :>< f x++instance Monad Run where (m :>< x) >>= f = case f x of n :>< y-> m*n :>< y++-- Invariant: 'RLE' never contains two adjacent entries with equal @a@ values.+-- Invariant: 'RLE' never contains zero-length runs.+--+-- These two together ensure we can use generated Eq/Ord instances and can+-- implement certain functions faster by omitting tests for zero or duplicated+-- runs.++-- | A run-length encoded representation of a @[a]@.+--+-- This doesn't have a 'Functor' or 'Traversable' instance because it would+-- need an 'Eq' constraint on the element type to uphold invariants, but there+-- are 'map' and 'traverse' functions exported.+newtype RLE a = RLE+ { toRuns :: [Run a]+ -- ^ Extract the contents of an 'RLE' as a list of runs.+ --+ -- This is not a retraction of 'fromRuns': @toRuns . fromRuns@ merges+ -- adjacent runs of equal values and eliminates empty runs.+ }+ deriving stock (Eq, Show, Generic, Foldable)+ deriving anyclass (NFData, Serialize)++instance Portray a => Portray (RLE a) where+ portray rle = Apply "fromRuns" [List $ portray <$> toRuns rle]++instance (Portray a, Diff a) => Diff (RLE a) where+ diff x y = Apply "fromRuns" . pure <$> diff (toRuns x) (toRuns y)++instance Eq a => IsList (RLE a) where+ type Item (RLE a) = a+ fromList = fromList+ toList = toList++instance a ~ Char => IsString (RLE a) where+ fromString = fromList++instance Eq a => Semigroup (RLE a) where+ (<>) = (++)++ stimes 0 _ = empty+ stimes _ (RLE []) = empty+ stimes n (RLE [nx :>< x]) = RLE [(fromIntegral n * nx :>< x)]+ stimes n0 (RLE (r0:rs0)) = RLE $ go (n0 - 1) rs0+ where+ adjustedCycle = toRuns $ RLE rs0 ++ RLE [r0]++ go 0 rs = r0:rs+ go n rs = go (n-1) (adjustedCycle P.++ rs)++instance Eq a => Monoid (RLE a) where+ mempty = empty++-- | An empty 'RLE'.+empty :: RLE a+empty = RLE []++-- | Returns 'True' iff the argument contains no elements.+null :: RLE a -> Bool+null = P.null . toRuns++-- | 'Data.Foldable.length' specialized to 'RLE'.+length :: RLE a -> Int+length (RLE rs0) = go rs0+ where+ go [] = 0+ go ((n :>< _) : rs) = n + go rs++-- | Run-length-encode a list by testing adjacent elements for equality.+fromList :: Eq a => [a] -> RLE a+fromList = foldr cons empty++-- | 'Data.Foldable.toList' specialized to 'RLE'.+toList :: RLE a -> [a]+toList (RLE []) = []+toList (RLE ((n :>< x):xs)) = replicate n x <> toList (RLE xs)++-- | Add an element onto the beginning of the sequence.+cons :: Eq a => a -> RLE a -> RLE a+cons = consRun . (1 :><)++consRun_ :: Eq a => Run a -> [Run a] -> [Run a]+consRun_ (nx :>< x) ((ny :>< y) : rs) | x == y = (nx+ny :>< x) : rs+consRun_ (0 :>< _) rs = rs+consRun_ r rs = r : rs++-- | Add a run of equal elements onto the beginning of the sequence.+consRun :: forall a. Eq a => Run a -> RLE a -> RLE a+consRun = coerce (consRun_ @a)++-- | Split the first element from the rest of the sequence.+uncons :: Eq a => RLE a -> Maybe (a, RLE a)+uncons (unconsRun -> Just (n :>< a, rest)) = Just (a, consRun (n-1 :>< a) rest)+uncons _ = Nothing++-- | Split the first run of equal elements from the rest of the sequence.+unconsRun :: RLE a -> Maybe (Run a, RLE a)+unconsRun (RLE (r:rs)) = Just (r, RLE rs)+unconsRun _ = Nothing++-- | Return an 'RLE' containing the first @n@ elements of the input.+take :: Int -> RLE a -> RLE a+take n (RLE xs) = RLE (go n xs)+ where+ go 0 _ = []+ go _ [] = []+ go i ((l :>< x):rs) = (min i l :>< x) : go (max 0 (i - l)) rs++-- | Returns a tuple where the first element contains the first n elements of+-- the sequence, and the second element is the remainder of the sequence.+splitAt :: (HasCallStack, Eq a) => Int -> RLE a -> (RLE a, RLE a)+splitAt n rle = go rle n empty+ where+ go r i prev+ | null r || i <= 0 = (reverse prev, r)+ | i < len = ( reverse ((i :>< a) `consRun` prev)+ , consRun (len - i :>< a) r')+ | otherwise = go r' (i - len) ((len :>< a) `consRun` prev)+ where+ -- Safe since we check for null above+ ((len :>< a), r') = fromJust $ unconsRun r++-- | Reverse the order of the elements in the sequence.+reverse :: RLE a -> RLE a+reverse (RLE r) = RLE (P.reverse r)++-- | Creates an RLE with a single element.+singleton :: a -> RLE a+singleton a = RLE [1 :>< a]++-- | Append two sequences.+(++) :: Eq a => RLE a -> RLE a -> RLE a+(++) (RLE (x0:xs@(_:_))) = \ys -> RLE $ x0 : toRuns (RLE xs ++ ys)+(++) (RLE [r]) = consRun r+(++) (RLE []) = id++-- | Map the given function over each element of the sequence.+map :: Eq b => (a -> b) -> RLE a -> RLE b+map f (RLE xs) = fromRuns (fmap (fmap f) xs)++-- | Map the given invertible function over each element of the sequence. This+-- is only safe when the function is invertible.+--+-- This is slightly faster than @map@ and does not require an Eq constraint on+-- the result type.+mapInvertible :: (a -> b) -> RLE a -> RLE b+mapInvertible f (RLE xs) = RLE (fmap (fmap f) xs)++-- | Visit each element of the sequence in an 'Applicative'.+--+-- @+-- traverse :: Eq b => Traversal (RLE a) (RLE b) a b+-- @+traverse :: (Eq b, Applicative f) => (a -> f b) -> RLE a -> f (RLE b)+traverse f rle = case unconsRun rle of+ Nothing -> pure empty+ Just (n :>< x, rs) -> flip (foldr cons)+ <$> replicateM n (f x)+ <*> traverse f rs++-- | @Fold@ over the contained runs in order.+--+-- This is as strong a type as this can have without breaking any laws, due to+-- the invariants that no empty or mergeable runs exist: if we make it a+-- @Traversal@, it can end up changing the number of targets, and if we make it+-- an @Iso@ to @[(Int, a)]@, the reverse direction is not an isomorphism.+--+-- If you want to use a law-breaking @Iso@ or @Traversal@ for this anyway, use+-- @iso 'fromRuns' 'toRuns'@ to inline the problematic @Iso@.+--+-- @+-- runs :: Fold (RLE a) (Int, a)+-- @+runs+ :: (Contravariant f, Applicative f)+ => (Run a -> f (Run a))+ -> RLE a -> f (RLE a)+runs f rle = fmap absurd $ contramap absurd $ P.traverse f $ toRuns rle++-- | Construct an 'RLE' from a list of runs.+--+-- This is a retraction of 'toRuns'.+fromRuns :: Eq a => [Run a] -> RLE a+fromRuns = foldr consRun empty++-- | Zip two sequences together.+zipWith :: Eq c => (a -> b -> c) -> RLE a -> RLE b -> RLE c+zipWith f (RLE xs0) (RLE ys0) = RLE $ go xs0 ys0+ where+ go [] _ = []+ go _ [] = []+ go ((nx :>< x) : xs) ((ny :>< y) : ys) = case compare nx ny of+ LT -> (nx :>< f x y) `consRun_` go xs ((ny-nx :>< y) : ys)+ GT -> (ny :>< f x y) `consRun_` go ((nx-ny :>< x) : xs) ys+ EQ -> (nx :>< f x y) `consRun_` go xs ys++-- | Return an 'RLE' containing all but the last element of the input.+init :: HasCallStack => RLE a -> RLE a+init (RLE rs0) = RLE $ go rs0+ where+ go [] = error "RLE.init: empty RLE"+ go (r0:r:rs) = r0 : go (r:rs)+ go [n :>< x] = [n-1 :>< x | n > 1]
+ test/RLETest.hs view
@@ -0,0 +1,86 @@+-- Copyright 2019-2021 Google LLC+--+-- Licensed under the Apache License, Version 2.0 (the "License");+-- you may not use this file except in compliance with the License.+-- You may obtain a copy of the License at+--+-- http://www.apache.org/licenses/LICENSE-2.0+--+-- Unless required by applicable law or agreed to in writing, software+-- distributed under the License is distributed on an "AS IS" BASIS,+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+-- See the License for the specific language governing permissions and+-- limitations under the License.++{-# LANGUAGE AllowAmbiguousTypes #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TypeApplications #-}++module Main where++import Control.Monad (replicateM)++import Test.Framework (defaultMain)+import Test.Framework.Providers.QuickCheck2 (testProperty)+import Test.QuickCheck+ ( (===), Arbitrary(..), Property+ , Gen, choose, forAll, sized, getPositive+ )++import Data.RLE (RLE, Run((:><)), fromList, toList)+import qualified Data.RLE as RLE++arbitrarySizedRLE :: Eq a => Gen a -> Int -> Gen (RLE a)+arbitrarySizedRLE genElement n = do+ maxRun <- arbitrary+ resultList <- replicateM n $ do+ element <- genElement+ runLen <- choose (1, getPositive maxRun)+ pure (runLen :>< element)+ pure (RLE.fromRuns resultList)++rles :: (Eq a, Arbitrary a) => Gen (RLE a)+rles = sized (arbitrarySizedRLE arbitrary)++prop_reverse :: (Eq a, Show a) => RLE a -> Property+prop_reverse rle = RLE.reverse rle === (fromList . reverse . toList) rle++prop_length :: (Eq a, Show a) => RLE a -> Property+prop_length rle = RLE.length rle === (length . toList) rle++prop_fromList_toList :: (Eq a, Show a) => RLE a -> Property+prop_fromList_toList rle = rle === (fromList . toList) rle++prop_toList_fromList :: (Eq a, Show a) => [a] -> Property+prop_toList_fromList xs = xs === (toList . fromList) xs++prop_take :: forall a . (Arbitrary a, Eq a, Show a) => Property+prop_take =+ forAll rles $ \rle ->+ forAll (choose (-1, RLE.length rle + 1)) $ \i ->+ prop_take' @a i rle++prop_take' :: (Eq a, Show a) => Int -> RLE a -> Property+prop_take' i rle =+ take i (toList rle) === toList (RLE.take i rle)++prop_splitAt :: forall a . (Arbitrary a, Eq a, Show a) => Property+prop_splitAt =+ forAll rles $ \rle ->+ forAll (choose (-1, RLE.length rle + 1)) $ \i ->+ prop_splitAt' @a i rle++prop_splitAt' :: (Eq a, Show a) => Int -> RLE a -> Property+prop_splitAt' i rle = (fromList l, fromList r) === RLE.splitAt i rle+ where (l, r) = splitAt i (toList rle)++main :: IO ()+main = defaultMain+ [ testProperty "reverse" (forAll rles $ prop_reverse @Int)+ , testProperty "length" (forAll rles $ prop_length @Int)+ , testProperty "toList . fromList" (prop_toList_fromList @Int)+ , testProperty "fromList . toList" (forAll rles $ prop_fromList_toList @Int)+ , testProperty "splitAt" (prop_splitAt @Int)+ , testProperty "take" (prop_take @Int)+ ]+