infinite-list 0.1.1 → 0.1.2

raw patch · 6 files changed

+365/−148 lines, 6 filesdep +containersdep −ghc-primdep ~basePVP ok

version bump matches the API change (PVP)

Dependencies added: containers

Dependencies removed: ghc-prim

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +7/−0
• README.md +3/−3
• infinite-list.cabal +10/−10
• src/Data/List/Infinite.hs +177/−58
• src/Data/List/Infinite/Set.hs +61/−0
• test/Properties.hs +107/−77

@@ -1,3 +1,10 @@+# 0.1.2++* Add `heteroZip` and `heteroZipWith`.+* Add `traverse_` and `for_`.+* Add `nubOrd` and `nubOrdBy`.+* Add `instance MonadFix`.+ # 0.1.1  * Add `mapMaybe` and `catMaybes`.

@@ -1,9 +1,9 @@-# infinite-list+# infinite-list [![Hackage](http://img.shields.io/hackage/v/infinite-list.svg)](https://hackage.haskell.org/package/infinite-list) [![Stackage LTS](http://stackage.org/package/infinite-list/badge/lts)](http://stackage.org/lts/package/infinite-list) [![Stackage Nightly](http://stackage.org/package/infinite-list/badge/nightly)](http://stackage.org/nightly/package/infinite-list)  Modern lightweight library for infinite lists with fusion:  * API similar to `Data.List`.-* No non-boot dependencies.+* No dependencies other than `base`. * Top performance, driven by fusion. * Avoid dangerous instances like `Foldable`. * Use `NonEmpty` where applicable.@@ -44,7 +44,7 @@  Altogether it means that code, polymorphic by `Foldable`, cannot confidently work with infinite lists. Even a trivial refactoring can get you in a deep trouble. It's better to save users from this pitfall and do not provide `instance Foldable` at all. We do provide a right fold however. -Since there is no `Foldable`, there could be no `Traversable`. Even if it was not prohibited because of a missing superclass, there are only a few monads, which are lazy enough to be productive for infinite traversals. If you are looking for a traverse with a lazy state, use `mapAccumL`.+Since there is no `Foldable`, there could be no `Traversable`. Even if it was not prohibited because of a missing superclass, there are only a few monads, which are lazy enough to be productive for infinite traversals. If you are looking for a traverse with a lazy state, use `mapAccumL`. We also provide `traverse_` and `for_`, but with slightly different types.  ## Laziness 

@@ -1,14 +1,14 @@ cabal-version:   2.2 name:            infinite-list-version:         0.1.1+version:         0.1.2 license:         BSD-3-Clause license-file:    LICENSE maintainer:      andrew.lelechenko@gmail.com author:          Bodigrim tested-with:-    ghc ==8.0.2 ghc ==8.2.2 ghc ==8.4.4 ghc ==8.6.5 ghc ==8.8.4-    ghc ==8.10.7 ghc ==9.0.2 ghc ==9.2.8 ghc ==9.4.8 ghc ==9.6.3-    ghc ==9.8.1+    ghc ==8.2.2 ghc ==8.4.4 ghc ==8.6.5 ghc ==8.8.4+    ghc ==8.10.7 ghc ==9.0.2 ghc ==9.2.8 ghc ==9.4.8 ghc ==9.6.5+    ghc ==9.8.4 ghc ==9.10.1 ghc ==9.12.1  homepage:        https://github.com/Bodigrim/infinite-list synopsis:        Infinite lists@@ -16,7 +16,7 @@     Modern lightweight library for infinite lists with fusion:     .     * API similar to "Data.List".-    * No non-boot dependencies.+    * No dependencies other than `base`.     * Top performance, driven by fusion.     * Avoid dangerous instances like `Foldable`.     * Use `NonEmpty` where applicable.@@ -43,15 +43,13 @@     exposed-modules:  Data.List.Infinite     hs-source-dirs:   src     other-modules:-        Data.List.Infinite.Zip         Data.List.Infinite.Internal+        Data.List.Infinite.Set+        Data.List.Infinite.Zip      default-language: Haskell2010     ghc-options:      -Wall-    build-depends:    base >=4.9 && <5--    if impl(ghc <8.2)-        build-depends: ghc-prim <1+    build-depends:    base >=4.10 && <5  test-suite infinite-properties     type:             exitcode-stdio-1.0@@ -61,6 +59,7 @@     ghc-options:      -Wall     build-depends:         base,+        containers,         infinite-list,         QuickCheck,         tasty,@@ -74,6 +73,7 @@     ghc-options:      -Wall -O0     build-depends:         base,+        containers,         infinite-list,         QuickCheck,         tasty,

@@ -1,5 +1,4 @@ {-# LANGUAGE BangPatterns #-}-{-# LANGUAGE CPP #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TupleSections #-}@@ -8,6 +7,7 @@ {-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}  {-# HLINT ignore "Redundant lambda" #-}+{-# HLINT ignore "Avoid restricted function" #-}  -- | -- Copyright:   (c) 2022 Bodigrim@@ -16,7 +16,7 @@ -- Modern lightweight library for infinite lists with fusion: -- -- * API similar to "Data.List".--- * No non-boot dependencies.+-- * No dependencies other than @base@. -- * Top performance, driven by fusion. -- * Avoid dangerous instances like `Data.Foldable.Foldable`. -- * Use `NonEmpty` where applicable.@@ -45,6 +45,8 @@   scanl',   scanl1,   mapAccumL,+  traverse_,+  for_,    -- * Transformations   concat,@@ -113,6 +115,8 @@   zipWith6,   zip7,   zipWith7,+  heteroZip,+  heteroZipWith,   unzip,   unzip3,   unzip4,@@ -128,6 +132,7 @@    -- * Set operations   nub,+  nubOrd,   delete,   (\\),   union,@@ -138,6 +143,7 @@    -- * Generalized functions   nubBy,+  nubOrdBy,   deleteBy,   deleteFirstsBy,   unionBy,@@ -151,30 +157,31 @@  import Control.Applicative (Applicative (..)) import Control.Arrow (first, second)+import Control.Exception (assert) import Control.Monad (Monad (..))+import Control.Monad.Fix (MonadFix (..)) import Data.Bits ((.&.)) import Data.Char (Char, isSpace) import Data.Coerce (coerce) import Data.Either (Either, either) import Data.Eq (Eq, (/=), (==)) import qualified Data.Foldable as F+import Data.Function (fix, ($)) import Data.Functor (Functor (..)) import qualified Data.List as List import Data.List.NonEmpty (NonEmpty (..)) import qualified Data.List.NonEmpty as NE import Data.Maybe (maybe) import Data.Ord (Ord, Ordering (..), compare, (<), (<=), (>), (>=))+import qualified Data.Traversable as Traversable+import Data.Void (Void)+import GHC.Exts (oneShot) import qualified GHC.Exts import Numeric.Natural (Natural)-import Prelude (Bool (..), Enum, Int, Integer, Integral, Maybe (..), Word, const, enumFrom, enumFromThen, flip, id, maxBound, minBound, not, otherwise, snd, uncurry, (&&), (+), (-), (.), (||))--#if MIN_VERSION_base(4,10,0)-import GHC.Exts (oneShot)-#else-import GHC.Magic (oneShot)-#endif+import Prelude (Bool (..), Enum, Int, Integer, Integral, Maybe (..), Traversable, Word, const, enumFrom, enumFromThen, flip, fromIntegral, id, maxBound, minBound, not, otherwise, snd, uncurry, (&&), (+), (-), (.), (||))  import Data.List.Infinite.Internal+import qualified Data.List.Infinite.Set as Set import Data.List.Infinite.Zip  -- | Right-associative fold of an infinite list, necessarily lazy in the accumulator.@@ -212,7 +219,7 @@     go :: Infinite a -> b     go (x :< xs) = f x xs (go xs) --- | Convert to a list. Use 'cycle' to go in the opposite direction.+-- | Convert to a list. Use 'Data.List.Infinite.cycle' to go in the opposite direction. toList :: Infinite a -> [a] toList = foldr (:) {-# NOINLINE [0] toList #-}@@ -231,7 +238,8 @@ -- >>> Data.List.Infinite.take 10 (0...) -- [0,1,2,3,4,5,6,7,8,9] ----- Beware that for finite types '(...)' applies 'cycle' atop of @[x..]@:+-- Beware that for finite types '(...)' applies 'Data.List.Infinite.cycle'+-- atop of @[x..]@: -- -- >>> :set -XPostfixOperators -- >>> Data.List.Infinite.take 10 (EQ...)@@ -277,7 +285,8 @@ -- >>> Data.List.Infinite.take 10 ((1,3)....) -- [1,3,5,7,9,11,13,15,17,19] ----- Beware that for finite types '(....)' applies 'cycle' atop of @[x,y..]@:+-- Beware that for finite types '(....)' applies 'Data.List.Infinite.cycle'+-- atop of @[x,y..]@: -- -- >>> :set -XPostfixOperators -- >>> Data.List.Infinite.take 10 ((EQ,GT)....)@@ -332,7 +341,7 @@        in iterate' (\n -> if n < d then from else n - d) from {-# INLINE ellipsis4Natural #-} --- | Just a pointwise 'map'.+-- | Just a pointwise 'Data.List.Infinite.map'. instance Functor Infinite where   fmap = map   (<$) = const . repeat@@ -343,9 +352,7 @@   (f :< fs) <*> (x :< xs) = f x :< (fs <*> xs)   (<*) = const   (*>) = const id-#if MIN_VERSION_base(4,10,0)   liftA2 = zipWith-#endif  -- | 'Control.Applicative.ZipList' cannot be made a lawful 'Monad', -- but 'Infinite', being a@@ -356,14 +363,31 @@ -- very soon because of linear indexing, so it is not recommended to be used -- in practice. instance Monad Infinite where-  xs >>= f = go 0 xs-    where-      go !n (y :< ys) = (f y `index` n) :< go (n + 1) ys-      index :: Infinite a -> Natural -> a-      index ys n = head (genericDrop n ys)+  xs >>= f = zipWith (\(!n) -> head . genericDrop n . f) ((...) (0 :: Natural)) xs+  -- To put it simply, (xs >>= f) !! n = f (xs !! n) !! n   {-# INLINE (>>=) #-}   (>>) = (*>) +-- | @since 0.1.2+instance MonadFix Infinite where+  mfix f = map (\(!n) -> fix $ head . genericDrop n . f) ((...) (0 :: Natural))+  -- To put it simply, mfix f !! n = fix ((!! n) . f)+  --+  -- How to derive it? As in Section 1.4 of Erkok's thesis,+  -- we can start by putting mfix f = fix (>>= f).+  --+  -- mfix f !! n+  -- = fix (>>= f) !! n+  -- = [by definition of fix, fix g = g (fix g)]+  -- = (fix (>>= f) >>= f) !! n+  -- = [by the choice of >>= above, (xs >>= g) !! n = g (xs !! n) !! n]+  -- = f (fix (>>= f) !! n) !! n+  -- = ((!! n) . f) (fix (>>= f) !! n)+  -- = [restoring mfix from fix]+  -- = ((!! n) . f) (mfix f !! n)+  --+  -- Then mfix f !! n = fix ((!! n) . f).+ -- | Get the first elements of an infinite list. head :: Infinite a -> a head (x :< _) = x@@ -379,7 +403,7 @@ tail :: Infinite a -> Infinite a tail (_ :< xs) = xs --- | Split an infinite list into its 'head' and 'tail'.+-- | Split an infinite list into its 'Data.List.Infinite.head' and 'Data.List.Infinite.tail'. uncons :: Infinite a -> (a, Infinite a) uncons (x :< xs) = (x, xs) @@ -411,7 +435,7 @@  -- | Flatten out an infinite list of non-empty lists. ----- The peculiar type with 'NonEmpty' is to guarantee that 'concat'+-- The peculiar type with 'NonEmpty' is to guarantee that 'Data.List.Infinite.concat' -- is productive and results in an infinite list. Otherwise the -- concatenation of infinitely many @[a]@ could still be a finite list. concat :: Infinite (NonEmpty a) -> Infinite a@@ -424,9 +448,9 @@     build (\cons -> foldr (flip (F.foldr cons)) xs)   #-} --- | First 'map' every element, then 'concat'.+-- | First 'Data.List.Infinite.map' every element, then 'Data.List.Infinite.concat'. ----- The peculiar type with 'NonEmpty' is to guarantee that 'concatMap'+-- The peculiar type with 'NonEmpty' is to guarantee that 'Data.List.Infinite.concatMap' -- is productive and results in an infinite list. Otherwise the -- concatenation of infinitely many @[b]@ could still be a finite list. concatMap :: (a -> NonEmpty b) -> Infinite a -> Infinite b@@ -457,7 +481,7 @@ -- | Insert a non-empty list between adjacent elements of an infinite list, -- and subsequently flatten it out. ----- The peculiar type with 'NonEmpty' is to guarantee that 'intercalate'+-- The peculiar type with 'NonEmpty' is to guarantee that 'Data.List.Infinite.intercalate' -- is productive and results in an infinite list. If separator is an empty list, -- concatenation of infinitely many @[a]@ could still be a finite list. intercalate :: NonEmpty a -> Infinite [a] -> Infinite a@@ -478,11 +502,17 @@ transpose :: Functor f => f (Infinite a) -> Infinite (f a) transpose xss = fmap head xss :< transpose (fmap tail xss) --- | Generate an infinite list of all subsequences of the argument.+-- | Generate an infinite list of all finite subsequences of the argument.+--+-- >>> take 8 (subsequences (0...))+-- [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]] subsequences :: Infinite a -> Infinite [a] subsequences = ([] :<) . map NE.toList . subsequences1 --- | Generate an infinite list of all non-empty subsequences of the argument.+-- | Generate an infinite list of all non-empty finite subsequences of the argument.+--+-- >>> take 7 (subsequences1 (0...))+-- [0 :| [],1 :| [],0 :| [1],2 :| [],0 :| [2],1 :| [2],0 :| [1,2]] subsequences1 :: Infinite a -> Infinite (NonEmpty a) subsequences1 = foldr go   where@@ -491,7 +521,12 @@       where         f ys r = ys :< (x `NE.cons` ys) :< r --- | Generate an infinite list of all permutations of the argument.+-- | Generate an infinite list of all finite+-- (such that only finite number of elements change their positions)+-- permutations of the argument.+--+-- >>> take 6 (fmap (take 3) (permutations (0...)))+-- [[0,1,2],[1,0,2],[2,1,0],[1,2,0],[2,0,1],[0,2,1]] permutations :: Infinite a -> Infinite (Infinite a) permutations xs0 = xs0 :< perms xs0 []   where@@ -530,7 +565,7 @@     tail (scanl f a bs)   #-} --- | Same as 'scanl', but strict in accumulator.+-- | Same as 'Data.List.Infinite.scanl', but strict in accumulator. scanl' :: (b -> a -> b) -> b -> Infinite a -> Infinite b scanl' f z0 = (z0 :<) . flip (foldr (\x acc z -> let !fzx = f z x in fzx :< acc fzx)) z0 @@ -606,7 +641,7 @@ "iterateFB" [1] iterateFB (:<) = iterate   #-} --- | Same as 'iterate', but strict in accumulator.+-- | Same as 'Data.List.Infinite.iterate', but strict in accumulator. iterate' :: (a -> a) -> a -> Infinite a iterate' f = go   where@@ -686,7 +721,7 @@  -- | Generate an infinite list of @f@ 0, @f@ 1, @f@ 2... ----- 'tabulate' and '(!!)' witness that 'Infinite' is+-- 'tabulate' and '(Data.List.Infinite.!!)' witness that 'Infinite' is -- [@Representable@](https://hackage.haskell.org/package/adjunctions/docs/Data-Functor-Rep.html#t:Representable). tabulate :: (Word -> a) -> Infinite a tabulate f = unfoldr (\n -> (f n, n + 1)) 0@@ -769,7 +804,8 @@  -- | Drop the longest prefix satisfying a predicate. ----- This function isn't productive (e. g., 'head' . 'dropWhile' @f@ won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.' 'Data.List.Infinite.dropWhile' @f@ won't terminate), -- if all elements of the input list satisfy the predicate. dropWhile :: (a -> Bool) -> Infinite a -> Infinite a dropWhile p = para (\x xs -> if p x then id else const (x :< xs))@@ -777,7 +813,7 @@ -- | Split an infinite list into the longest prefix satisfying a predicate and the rest. -- -- This function isn't productive in the second component of the tuple--- (e. g., 'head' . 'snd' . 'span' @f@ won't terminate),+-- (e. g., 'Data.List.Infinite.head' '.' 'snd' '.' 'Data.List.Infinite.span' @f@ won't terminate), -- if all elements of the input list satisfy the predicate. span :: (a -> Bool) -> Infinite a -> ([a], Infinite a) span p = para (\x xs -> if p x then first (x :) else const ([], x :< xs))@@ -785,7 +821,7 @@ -- | Split an infinite list into the longest prefix /not/ satisfying a predicate and the rest. -- -- This function isn't productive in the second component of the tuple--- (e. g., 'head' . 'snd' . 'break' @f@ won't terminate),+-- (e. g., 'Data.List.Infinite.head' '.' 'snd' '.' 'Data.List.Infinite.break' @f@ won't terminate), -- if no elements of the input list satisfy the predicate. break :: (a -> Bool) -> Infinite a -> ([a], Infinite a) break = span . (not .)@@ -804,7 +840,7 @@ group :: Eq a => Infinite a -> Infinite (NonEmpty a) group = groupBy (==) --- | Overloaded version of 'group'.+-- | Overloaded version of 'Data.List.Infinite.group'. groupBy :: (a -> a -> Bool) -> Infinite a -> Infinite (NonEmpty a) -- Quite surprisingly, 'groupBy' is not a simple catamorphism. -- Since @f@ is not guaranteed to be transitive, it's a full-blown@@ -816,6 +852,16 @@         (ys, zs) = span (f x) xs  -- | Generate all prefixes of an infinite list.+--+-- >>> :set -XPostfixOperators+-- >>> Data.List.Infinite.take 5 $ Data.List.Infinite.inits (0...)+-- [[],[0],[0,1],[0,1,2],[0,1,2,3]]+--+-- If you need reversed prefixes, they can be generated cheaper using 'scanl'':+--+-- >>> :set -XPostfixOperators+-- >>> Data.List.Infinite.take 5 $ Data.List.Infinite.scanl' (flip (:)) [] (0...)+-- [[],[0],[1,0],[2,1,0],[3,2,1,0]] inits :: Infinite a -> Infinite [a] inits =   map (\(SnocBuilder _ front rear) -> front List.++ List.reverse rear)@@ -865,13 +911,15 @@  -- | Filter an infinite list, removing elements which does not satisfy a predicate. ----- This function isn't productive (e. g., 'head' . 'filter' @f@ won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.' 'Data.List.Infinite.filter' @f@ won't terminate), -- if no elements of the input list satisfy the predicate. -- -- A common objection is that since it could happen that no elements of the input -- satisfy the predicate, the return type should be @[a]@ instead of 'Infinite' @a@.--- This would not however make 'filter' any more productive. Note that such--- hypothetical 'filter' could not ever generate @[]@ constructor, only @(:)@, so+-- This would not however make 'Data.List.Infinite.filter' any more productive.+-- Note that such hypothetical 'Data.List.Infinite.filter' could not ever+-- generate @[]@ constructor, only @(:)@, so -- we would just have a more lax type gaining nothing instead. Same reasoning applies -- to other filtering \/ partitioning \/ searching functions. filter :: (a -> Bool) -> Infinite a -> Infinite a@@ -902,7 +950,7 @@ -- satisfying a predicate, and the second one the rest. -- -- This function isn't productive in the first component of the tuple--- (e. g., 'head' . 'Data.Tuple.fst' . 'partition' @f@ won't terminate),+-- (e. g., 'Data.List.Infinite.head' '.' 'Data.Tuple.fst' '.' 'Data.List.Infinite.partition' @f@ won't terminate), -- if no elements of the input list satisfy the predicate. -- Same for the second component, -- if all elements of the input list satisfy the predicate.@@ -913,11 +961,18 @@ -- On contrary to @Data.List.@'List.!!', this function takes 'Word' instead of 'Int' -- to avoid 'Prelude.error' on negative arguments. --+-- If you are concerned that unsigned indices may accidentally underflow,+-- compile with [@-fno-ignore-asserts@](https://downloads.haskell.org/ghc/latest/docs/users_guide/using-optimisation.html#ghc-flag--fignore-asserts):+-- there is an assert checking that the index does not exceed+-- 'fromIntegral' ('maxBound' :: 'Int').+-- -- This is actually @index@ from -- [@Representable@](https://hackage.haskell.org/package/adjunctions/docs/Data-Functor-Rep.html#t:Representable) -- type class in disguise. (!!) :: Infinite a -> Word -> a-(!!) = foldr (\x acc m -> if m == 0 then x else acc (m - 1))+(!!) xs n =+  assert (n <= fromIntegral (maxBound :: Int)) $+    foldr (\x acc m -> if m == 0 then x else acc (m - 1)) xs n  infixl 9 !! @@ -928,7 +983,8 @@  -- | Return indices of all elements, equal to a given. ----- This function isn't productive (e. g., 'head' . 'elemIndices' @f@ won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.' 'Data.List.Infinite.elemIndices' @f@ won't terminate), -- if no elements of the input list are equal the given one. elemIndices :: Eq a => a -> Infinite a -> Infinite Word elemIndices = findIndices . (==)@@ -940,11 +996,34 @@  -- | Return indices of all elements, satisfying a predicate. ----- This function isn't productive (e. g., 'head' . 'elemIndices' @f@ won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.'' 'Data.List.Infinite.findIndices' @f@ won't terminate), -- if no elements of the input list satisfy the predicate. findIndices :: (a -> Bool) -> Infinite a -> Infinite Word findIndices f = flip (foldr (\x acc !m -> (if f x then (m :<) else id) (acc (m + 1)))) 0 +-- | Zip an 'Infinite' with any 'Traversable', maintaining the shape of the+-- latter.+--+-- >>> import Data.Functor.Compose (Compose(..))+-- >>> heteroZip (0...) (Compose [Just 10, Nothing, Just 20])+-- Compose [Just (0,10),Nothing,Just (1,20)]+--+-- @since 0.1.2+heteroZip :: Traversable t => Infinite a -> t b -> t (a, b)+heteroZip = heteroZipWith (,)++-- | Use a given function to zip an 'Infinite' with any 'Traversable',+-- maintaining the shape of the latter.+--+-- >>> import Data.Functor.Compose (Compose(..))+-- >>> heteroZipWith (+) (0...) (Compose [Just 10, Nothing, Just 20])+-- Compose [Just 10,Nothing,Just 21]+--+-- @since 0.1.2+heteroZipWith :: Traversable t => (a -> b -> c) -> Infinite a -> t b -> t c+heteroZipWith f = (snd .) . Traversable.mapAccumL (\(x :< xs) b -> (xs, f x b))+ -- | Unzip an infinite list of tuples. unzip :: Infinite (a, b) -> (Infinite a, Infinite b) unzip = foldr (\(a, b) ~(as, bs) -> (a :< as, b :< bs))@@ -978,7 +1057,7 @@ -- | Split an infinite string into lines, by @\\n@. Empty lines are preserved. -- -- In contrast to their counterparts from "Data.List", it holds that--- 'unlines' @.@ 'lines' @=@ 'id'.+-- 'Data.List.Infinite.unlines' @.@ 'Data.List.Infinite.lines' @=@ 'id'. lines :: Infinite Char -> Infinite [Char] lines = foldr go   where@@ -988,7 +1067,7 @@ -- | Concatenate lines together with @\\n@. -- -- In contrast to their counterparts from "Data.List", it holds that--- 'unlines' @.@ 'lines' @=@ 'id'.+-- 'Data.List.Infinite.unlines' @.@ 'Data.List.Infinite.lines' @=@ 'id'. unlines :: Infinite [Char] -> Infinite Char unlines = foldr (\l xs -> l `prependList` ('\n' :< xs)) @@ -1030,9 +1109,9 @@  -- | Concatenate words together with a space. ----- The function is meant to be a counterpart of with 'words'.+-- The function is meant to be a counterpart of with 'Data.List.Infinite.words'. -- If you need to concatenate together 'Infinite' @[@'Char'@]@,--- use 'intercalate' @(@'pure' @' ')@.+-- use 'Data.List.Infinite.intercalate' @(@'pure' @' ')@. unwords :: Infinite (NonEmpty Char) -> Infinite Char unwords = foldr (\(l :| ls) acc -> l :< ls `prependList` (' ' :< acc)) @@ -1049,18 +1128,33 @@   #-}  -- | Remove duplicate from a list, keeping only the first occurrence of each element.+-- Because of a very weak constraint on @a@, this operation takes /O/(/n/²) time.+-- Consider using 'nubOrd' instead. nub :: Eq a => Infinite a -> Infinite a nub = nubBy (==) --- | Overloaded version of 'nub'.+-- | Overloaded version of 'Data.List.Infinite.nub'.+-- Consider using 'nubOrdBy' instead. nubBy :: (a -> a -> Bool) -> Infinite a -> Infinite a nubBy eq = flip (foldr (\x acc seen -> if List.any (`eq` x) seen then acc seen else x :< acc (x : seen))) [] +-- | Same as 'nub', but asymptotically faster, taking only /O/(/n/ log /n/) time.+--+-- @since 0.1.2+nubOrd :: Ord a => Infinite a -> Infinite a+nubOrd = nubOrdBy compare++-- | Overloaded version of 'Data.List.Infinite.nubOrd'.+--+-- @since 0.1.2+nubOrdBy :: (a -> a -> Ordering) -> Infinite a -> Infinite a+nubOrdBy cmp = flip (foldr (\x acc seen -> if Set.member cmp x seen then acc seen else x :< acc (Set.insert cmp x seen))) Set.empty+ -- | Remove all occurrences of an element from an infinite list. delete :: Eq a => a -> Infinite a -> Infinite a delete = deleteBy (==) --- | Overloaded version of 'delete'.+-- | Overloaded version of 'Data.List.Infinite.delete'. deleteBy :: (a -> b -> Bool) -> a -> Infinite b -> Infinite b deleteBy eq x = para (\y ys acc -> if eq x y then ys else y :< acc) @@ -1069,7 +1163,7 @@ (\\) :: Eq a => Infinite a -> [a] -> Infinite a (\\) = deleteFirstsBy (==) --- | Overloaded version of '(\\)'.+-- | Overloaded version of '(Data.List.Infinite.\\)'. deleteFirstsBy :: (a -> b -> Bool) -> Infinite b -> [a] -> Infinite b deleteFirstsBy eq = List.foldl (flip (deleteBy eq)) @@ -1079,7 +1173,7 @@ union :: Eq a => [a] -> Infinite a -> Infinite a union = unionBy (==) --- | Overloaded version of 'union'.+-- | Overloaded version of 'Data.List.Infinite.union'. unionBy :: (a -> a -> Bool) -> [a] -> Infinite a -> Infinite a unionBy eq xs ys = xs `prependList` List.foldl (flip (deleteBy eq)) (nubBy eq ys) xs @@ -1088,7 +1182,7 @@ insert :: Ord a => a -> Infinite a -> Infinite a insert = insertBy compare --- | Overloaded version of 'insert'.+-- | Overloaded version of 'Data.List.Infinite.insert'. insertBy :: (a -> a -> Ordering) -> a -> Infinite a -> Infinite a insertBy cmp x = para (\y ys acc -> case cmp x y of GT -> y :< acc; _ -> x :< y :< ys) @@ -1097,7 +1191,7 @@ intersect :: Eq a => Infinite a -> [a] -> Infinite a intersect = intersectBy (==) --- | Overloaded version of 'intersect'.+-- | Overloaded version of 'Data.List.Infinite.intersect'. intersectBy :: (a -> b -> Bool) -> Infinite a -> [b] -> Infinite a intersectBy eq xs ys = filter (\x -> List.any (eq x) ys) xs @@ -1107,7 +1201,8 @@  -- | Apply a function to every element of an infinite list and collect 'Just' results. ----- This function isn't productive (e. g., 'head' . 'mapMaybe' @f@ won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.' 'mapMaybe' @f@ won't terminate), -- if no elements of the input list result in 'Just'. -- -- @since 0.1.1@@ -1116,7 +1211,8 @@  -- | Keep only 'Just' elements. ----- This function isn't productive (e. g., 'head' . 'catMaybes' won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.' 'catMaybes' won't terminate), -- if no elements of the input list are 'Just'. -- -- @since 0.1.1@@ -1126,8 +1222,8 @@ -- | Apply a function to every element of an infinite list and -- separate 'Data.Either.Left' and 'Data.Either.Right' results. ----- This function isn't productive (e. g., 'head' . 'Data.Tuple.fst' .--- 'mapEither' @f@ won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.' 'Data.Tuple.fst' '.' 'mapEither' @f@ won't terminate), -- if no elements of the input list result in 'Data.Either.Left' or 'Data.Either.Right'. -- -- @since 0.1.1@@ -1136,10 +1232,33 @@  -- | Separate 'Data.Either.Left' and 'Data.Either.Right' elements. ----- This function isn't productive (e. g., 'head' . 'Data.Tuple.fst' . 'partitionEithers'--- won't terminate),+-- This function isn't productive+-- (e. g., 'Data.List.Infinite.head' '.' 'Data.Tuple.fst' '.' 'partitionEithers' won't terminate), -- if no elements of the input list are 'Data.Either.Left' or 'Data.Either.Right'. -- -- @since 0.1.1 partitionEithers :: Infinite (Either a b) -> (Infinite a, Infinite b) partitionEithers = foldr (either (first . (:<)) (second . (:<)))++-- | Map each element to an action, evaluate these actions from left to right+-- and ignore the results. Note that the return type is 'Void' instead of usual @()@.+--+-- >>> traverse_ print (0...) -- hit Ctrl+C to terminate+-- 0+-- 1+-- 2Interrupted+--+-- 'traverse_' could be productive for some short-circuiting @f@:+--+-- >>> traverse_ (\x -> if x > 10 then Left x else Right ()) (0...)+-- Left 11+--+-- @since 0.1.2+traverse_ :: Applicative f => (a -> f ()) -> Infinite a -> f Void+traverse_ = foldr . ((*>) .)++-- | Flipped 'traverse_'.+--+-- @since 0.1.2+for_ :: Applicative f => Infinite a -> (a -> f ()) -> f Void+for_ = flip traverse_

@@ -0,0 +1,61 @@+{-# LANGUAGE LambdaCase #-}++-- |+-- Copyright:   (c) 2024 Bodigrim+-- License:     BSD3+module Data.List.Infinite.Set (+  Set,+  empty,+  member,+  insert,+) where++data Color = Red | Black+  deriving (Show)++-- | Okasaki red-black tree.+data Set a = Empty | Node !Color !(Set a) !a !(Set a)+  deriving (Show)++empty :: Set a+empty = Empty++member :: (a -> a -> Ordering) -> a -> Set a -> Bool+member cmp = member'+  where+    member' x = go+      where+        go = \case+          Empty -> False+          Node _ left center right -> case cmp x center of+            LT -> go left+            EQ -> True+            GT -> go right++insert :: (a -> a -> Ordering) -> a -> Set a -> Set a+insert cmp = insert'+  where+    insert' x = blacken . go+      where+        go = \case+          Empty -> Node Red Empty x Empty+          Node color left center right -> case cmp x center of+            LT -> balance color (go left) center right+            EQ -> Node color left center right+            GT -> balance color left center (go right)++    blacken = \case+      Empty -> Empty+      Node _ left center right -> Node Black left center right++balance :: Color -> Set a -> a -> Set a -> Set a+balance Black (Node Red (Node Red a b c) d e) f g =+  Node Red (Node Black a b c) d (Node Black e f g)+balance Black (Node Red a b (Node Red c d e)) f g =+  Node Red (Node Black a b c) d (Node Black e f g)+balance Black a b (Node Red (Node Red c d e) f g) =+  Node Red (Node Black a b c) d (Node Black e f g)+balance Black a b (Node Red c d (Node Red e f g)) =+  Node Red (Node Black a b c) d (Node Black e f g)+balance color left center right =+  Node color left center right

@@ -24,6 +24,7 @@  import Control.Applicative import Control.Monad+import Control.Monad.Fix (mfix) import Data.Bifunctor import Data.Bits import Data.Either@@ -32,6 +33,8 @@ import qualified Data.List.Infinite as I import Data.List.NonEmpty (NonEmpty(..)) import qualified Data.List.NonEmpty as NE+import Data.Map.Strict (Map)+import qualified Data.Map.Strict as Map import Data.Maybe import Data.Word (Word32) import Numeric.Natural@@ -69,18 +72,18 @@       Just (fmap trim (I.uncons xs)) === L.uncons (trim1 xs)    , testProperty "map" $-    \(applyFun -> f :: Int -> Word) (Blind (xs :: Infinite Int)) ->+    \(applyFun -> (f :: Int -> Word)) (Blind (xs :: Infinite Int)) ->       trim (I.map f xs) === L.map f (trim xs)    , testProperty "fmap" $-    \(applyFun -> f :: Int -> Int) (Blind (xs :: Infinite Int)) ->+    \(applyFun -> (f :: Int -> Int)) (Blind (xs :: Infinite Int)) ->       trim (fmap f xs) === fmap f (trim xs)   , testProperty "<$" $     \(x :: Word) (Blind (xs :: Infinite Int)) ->       trim (x <$ xs) === trim (fmap (const x) xs)    , testProperty "pure" $-    \(applyFun -> f :: Int -> Word) (x :: Int) ->+    \(applyFun -> (f :: Int -> Word)) (x :: Int) ->       trim (pure f <*> pure x) === trim (pure (f x))   , testProperty "*>" $     \(Blind (xs :: Infinite Int)) (Blind (ys :: Infinite Word)) ->@@ -90,13 +93,13 @@       trim (xs <* ys) === trim (liftA2 const xs ys)    , testProperty ">>= 1" $-    \x ((I.cycle .) . applyFun -> k :: Int -> Infinite Word) ->+    \x ((I.cycle .) . applyFun -> (k :: Int -> Infinite Word)) ->       trim (return x >>= k) === trim (k x)   , testProperty ">>= 2" $     \(Blind (xs :: Infinite Int)) ->       trim (xs >>= return) === trim xs   , testProperty ">>= 3" $-    \(Blind xs) ((I.cycle .) . applyFun -> k :: Int -> Infinite Word)  ((I.cycle .) . applyFun -> h :: Word -> Infinite Char) ->+    \(Blind xs) ((I.cycle .) . applyFun -> (k :: Int -> Infinite Word))  ((I.cycle .) . applyFun -> (h :: Word -> Infinite Char)) ->       trim (xs >>= (k >=> h)) === trim ((xs >>= k) >>= h)   , testProperty ">>" $     \(Blind (xs :: Infinite Int)) (Blind (ys :: Infinite Word)) ->@@ -106,23 +109,23 @@     \(Blind (xs :: Infinite (NonEmpty Int))) ->       trim (I.concat xs) === L.take 10 (L.concatMap NE.toList (I.toList xs))   , testProperty "concatMap" $-    \(applyFun -> f :: Int -> NonEmpty Word) (Blind xs) ->+    \(applyFun -> (f :: Int -> NonEmpty Word)) (Blind xs) ->       trim (I.concatMap f xs) === L.take 10 (L.concatMap (NE.toList . f) (I.toList xs))    , testProperty "intersperse" $     \(x :: Int) (Blind xs) ->       I.take 19 (I.intersperse x xs) === L.intersperse x (trim xs)-  , testProperty "intersperse laziness 1" $+  , testProperty "intersperse laziness 1" $ once $     I.head (I.intersperse undefined ('q' :< undefined)) === 'q'-  , testProperty "intersperse laziness 2" $+  , testProperty "intersperse laziness 2" $ once $     I.take 2 (I.intersperse 'w' ('q' :< undefined)) === "qw"    , testProperty "intercalate" $     \(x :: NonEmpty Int) (Blind xs) ->       I.take (sum (map length (trim xs)) + 9 * length x) (I.intercalate x xs) === L.intercalate (NE.toList x) (trim xs)-  , testProperty "intercalate laziness 1" $+  , testProperty "intercalate laziness 1" $ once $     I.take 3 (I.intercalate undefined ("foo" :< undefined)) === "foo"-  , testProperty "intercalate laziness 2" $+  , testProperty "intercalate laziness 2" $ once $     I.take 6 (I.intercalate (NE.fromList "bar") ("foo" :< undefined)) === "foobar"    , testProperty "interleave 1" $@@ -131,32 +134,32 @@   , testProperty "interleave 2" $     \(Blind (xs :: Infinite Int)) (Blind ys) ->       trim (I.map snd (I.filter fst (I.zip (I.cycle (False :| [True])) (I.interleave xs ys)))) === trim ys-  , testProperty "interleave laziness" $+  , testProperty "interleave laziness" $ once $     I.head (I.interleave ('a' :< undefined) undefined) === 'a'    , testProperty "transpose []" $-    \(fmap getBlind -> xss :: [Infinite Int]) -> not (null xss) ==>+    \(fmap getBlind -> (xss :: [Infinite Int])) -> not (null xss) ==>       trim (I.transpose xss) === L.transpose (map trim xss)   , testProperty "transpose NE" $-    \(fmap getBlind -> xss :: NonEmpty (Infinite Int)) ->+    \(fmap getBlind -> (xss :: NonEmpty (Infinite Int))) ->       NE.fromList (trim (I.transpose xss)) === NE.transpose (NE.map (NE.fromList . trim) xss)-  , testProperty "transpose laziness 1" $+  , testProperty "transpose laziness 1" $ once $     I.head (I.transpose ['a' :< undefined, 'b' :< undefined]) === "ab"-  , testProperty "transpose laziness 2" $+  , testProperty "transpose laziness 2" $ once $     I.head (I.transpose (('a' :< undefined) :| ['b' :< undefined])) === 'a' :| "b"    , testProperty "subsequences" $     \(Blind (xs :: Infinite Int)) ->       I.take 16 (I.subsequences xs) === L.subsequences (I.take 4 xs)-  , testProperty "subsequences laziness 1" $+  , testProperty "subsequences laziness 1" $ once $     I.head (I.subsequences undefined) === ""-  , testProperty "subsequences laziness 2" $+  , testProperty "subsequences laziness 2" $ once $     I.take 2 (I.subsequences ('q' :< undefined)) === ["", "q"]    , testProperty "permutations" $     \(Blind (xs :: Infinite Int)) ->       map (I.take 4) (I.take 24 (I.permutations xs)) === L.permutations (I.take 4 xs)-  , testProperty "permutations laziness" $+  , testProperty "permutations laziness" $ once $     I.take 6 (I.map (I.take 3) (I.permutations ('q' :< 'w' :< 'e' :< undefined))) === ["qwe","wqe","ewq","weq","eqw","qew"]    , testProperty "... Bool" $@@ -209,36 +212,36 @@       L.take 10 (I.toList xs) === trim xs    , testProperty "scanl" $-    \(curry . applyFun -> f :: Word -> Int -> Word) s (Blind xs) ->+    \(curry . applyFun -> (f :: Word -> Int -> Word)) s (Blind xs) ->       trim1 (I.scanl f s xs) === L.scanl f s (trim xs)-  , testProperty "scanl laziness" $+  , testProperty "scanl laziness" $ once $     I.head (I.scanl undefined 'q' undefined) === 'q'   , testProperty "scanl'" $-    \(curry . applyFun -> f :: Word -> Int -> Word) s (Blind xs) ->+    \(curry . applyFun -> (f :: Word -> Int -> Word)) s (Blind xs) ->       trim1 (I.scanl' f s xs) === L.scanl' f s (trim xs)-  , testProperty "scanl' laziness" $+  , testProperty "scanl' laziness" $ once $     I.head (I.scanl' undefined 'q' undefined) === 'q'   , testProperty "scanl1" $-    \(curry . applyFun -> f :: Int -> Int -> Int) (Blind xs) ->+    \(curry . applyFun -> (f :: Int -> Int -> Int)) (Blind xs) ->       trim (I.scanl1 f xs) === L.scanl1 f (trim xs)-  , testProperty "scanl1 laziness" $+  , testProperty "scanl1 laziness" $ once $     I.head (I.scanl1 undefined ('q' :< undefined)) === 'q'    , testProperty "mapAccumL" $-    \(curry . applyFun -> f :: Bool -> Int -> (Bool, Word)) (Blind xs) ->+    \(curry . applyFun -> (f :: Bool -> Int -> (Bool, Word))) (Blind xs) ->       trim (I.mapAccumL f False xs) === snd (L.mapAccumL f False (trim xs))-  , testProperty "mapAccumL laziness" $+  , testProperty "mapAccumL laziness" $ once $     I.head (I.mapAccumL (\_ x -> (undefined, x)) undefined ('q' :< undefined)) === 'q'    , testProperty "iterate" $-    \(applyFun -> f :: Int -> Int) s ->+    \(applyFun -> (f :: Int -> Int)) s ->       trim (I.iterate f s) === L.take 10 (L.iterate f s)-  , testProperty "iterate laziness" $+  , testProperty "iterate laziness" $ once $       I.head (I.iterate undefined 'q') === 'q'   , testProperty "iterate'" $-    \(applyFun -> f :: Int -> Int) s ->+    \(applyFun -> (f :: Int -> Int)) s ->       trim (I.iterate' f s) === L.take 10 (L.iterate f s)-  , testProperty "iterate' laziness" $+  , testProperty "iterate' laziness" $ once $       I.head (I.iterate' undefined 'q') === 'q'    , testProperty "repeat" $@@ -248,83 +251,83 @@   , testProperty "cycle" $     \(xs :: NonEmpty Int) ->       trim (I.cycle xs) === L.take 10 (L.cycle (NE.toList xs))-  , testProperty "cycle laziness" $+  , testProperty "cycle laziness" $ once $     I.head (I.cycle ('q' :| undefined)) === 'q'    , testProperty "unfoldr" $-    \(applyFun -> f :: Word -> (Int, Word)) s ->+    \(applyFun -> (f :: Word -> (Int, Word))) s ->       trim (I.unfoldr f s) === L.take 10 (L.unfoldr (Just . f) s)-  , testProperty "unfoldr laziness" $+  , testProperty "unfoldr laziness" $ once $     I.head (I.unfoldr (, undefined) 'q') === 'q'    , testProperty "take" $     \n (Blind (xs :: Infinite Int)) ->       L.take 10 (I.take n xs) === L.take n (trim xs)-  , testProperty "take laziness 1" $+  , testProperty "take laziness 1" $ once $     I.take 0 undefined === ""-  , testProperty "take laziness 2" $+  , testProperty "take laziness 2" $ once $     I.take 1 ('q' :< undefined) === "q"   , testProperty "drop" $     \n (Blind (xs :: Infinite Int)) ->       trim (I.drop n xs) === L.drop n (I.take (max n 0 + 10) xs)-  , testProperty "drop laziness" $+  , testProperty "drop laziness" $ once $     I.head (I.drop 0 ('q' :< undefined)) === 'q'   , testProperty "splitAt" $     \n (Blind (xs :: Infinite Int)) ->       bimap (L.take 10) trim (I.splitAt n xs) ===         first (L.take 10) (L.splitAt n (I.take (max n 0 + 10) xs))-  , testProperty "splitAt laziness 1" $+  , testProperty "splitAt laziness 1" $ once $     fst (I.splitAt 0 undefined) === ""-  , testProperty "splitAt laziness 2" $+  , testProperty "splitAt laziness 2" $ once $     fst (I.splitAt 1 ('q' :< undefined)) === "q"    , testProperty "takeWhile" $-    \(applyFun -> f :: Ordering -> Bool) (Blind xs) ->+    \(applyFun -> (f :: Ordering -> Bool)) (Blind xs) ->       L.take 10 (L.takeWhile f (I.foldr (:) xs)) ===         L.take 10 (I.takeWhile f xs)-  , testProperty "takeWhile laziness 1" $+  , testProperty "takeWhile laziness 1" $ once $       L.null (I.takeWhile (const False) ('q' :< undefined))-  , testProperty "takeWhile laziness 2" $+  , testProperty "takeWhile laziness 2" $ once $       L.head (I.takeWhile (const True) ('q' :< undefined)) === 'q'   , testProperty "fst . span" $-    \(applyFun -> f :: Ordering -> Bool) (Blind xs) ->+    \(applyFun -> (f :: Ordering -> Bool)) (Blind xs) ->       let ys = L.take 10 (fst (I.span f xs)) in         L.take 10 (L.takeWhile f (I.take (length ys + 10) xs)) ===           L.take 10 (fst (I.span f xs))   , testProperty "fst . break" $-    \(applyFun -> f :: Ordering -> Bool) (Blind xs) ->+    \(applyFun -> (f :: Ordering -> Bool)) (Blind xs) ->       let ys = L.take 10 (fst (I.break f xs)) in         L.take 10 (L.takeWhile (not . f) (I.take (length ys + 10) xs)) ===           L.take 10 (fst (I.break f xs))   , testProperty "dropWhile" $-    \(applyFun -> f :: Ordering -> Bool) (Blind xs) ->+    \(applyFun -> (f :: Ordering -> Bool)) (Blind xs) ->       trim (L.foldr (:<) (I.dropWhile f xs) (I.takeWhile f xs)) === trim xs   , testProperty "snd . span" $-    \(applyFun -> f :: Ordering -> Bool) (Blind xs) ->+    \(applyFun -> (f :: Ordering -> Bool)) (Blind xs) ->       trim (L.foldr (:<) (snd (I.span f xs)) (I.takeWhile f xs)) === trim xs   , testProperty "snd . break" $-    \(applyFun -> f :: Ordering -> Bool) (Blind xs) ->+    \(applyFun -> (f :: Ordering -> Bool)) (Blind xs) ->       trim (L.foldr (:<) (snd (I.break f xs)) (I.takeWhile (not . f) xs)) === trim xs-  , testProperty "span laziness" $+  , testProperty "span laziness" $ once $     L.head (fst (I.span (/= '\n') ('q' :< undefined))) === 'q'-  , testProperty "break laziness" $+  , testProperty "break laziness" $ once $     L.head (fst (I.break (== '\n') ('q' :< undefined))) === 'q'    , testProperty "stripPrefix" $     \(xs :: [Int]) (Blind (ys :: Infinite Int)) ->       fmap trim (I.stripPrefix xs ys) === fmap (L.take 10) (L.stripPrefix xs (I.take (length xs + 10) ys))-  , testProperty "stripPrefix laziness 1" $+  , testProperty "stripPrefix laziness 1" $ once $     isNothing (I.stripPrefix ('q' : undefined) ('w' :< undefined))-  , testProperty "stripPrefix laziness 2" $+  , testProperty "stripPrefix laziness 2" $ once $     isJust (I.stripPrefix "foo" ('f' :< 'o' :< 'o' :< undefined))   , testProperty "isPrefixOf" $     \(xs :: [Int]) (Blind (ys :: Infinite Int)) ->       I.isPrefixOf xs ys === L.isPrefixOf xs (I.take (length xs + 10) ys)-  , testProperty "isPrefixOf laziness 1" $+  , testProperty "isPrefixOf laziness 1" $ once $     I.isPrefixOf "" undefined-  , testProperty "isPrefixOf laziness 2" $+  , testProperty "isPrefixOf laziness 2" $ once $     not (I.isPrefixOf ('q' : undefined) ('w' :< undefined))-  , testProperty "isPrefixOf laziness 3" $+  , testProperty "isPrefixOf laziness 3" $ once $     I.isPrefixOf "foo" ('f' :< 'o' :< 'o' :< undefined)    , testProperty "zip" $@@ -346,6 +349,22 @@     \(Blind (xs1 :: Infinite Int)) (Blind (xs2 :: Infinite Word)) (Blind (xs3 :: Infinite Bool)) (Blind (xs4 :: Infinite Char)) (Blind (xs5 :: Infinite Ordering)) (Blind (xs6 :: Infinite String)) (Blind (xs7 :: Infinite Integer)) ->       trim (I.zip7 xs1 xs2 xs3 xs4 xs5 xs6 xs7) === L.zip7 (trim xs1) (trim xs2) (trim xs3) (trim xs4) (trim xs5) (trim xs6) (trim xs7) +  , testProperty "heteroZip" $+    \(Blind (xs1 :: Infinite Int)) (xs2 :: Map Word Word) ->+      I.heteroZip xs1 xs2 === Map.fromList (L.zipWith (\x1 (k, x2) -> (k, (x1, x2))) (I.toList xs1) (Map.toList xs2))+  , testProperty "heteroZipWith" $+    \(curry . applyFun -> (f :: Int -> Word -> Char)) (Blind (xs1 :: Infinite Int)) (xs2 :: Map Word Word) ->+      I.heteroZipWith f xs1 xs2 === Map.fromList (L.zipWith (\x1 (k, x2) -> (k, f x1 x2)) (I.toList xs1) (Map.toList xs2))++  , testProperty "heteroZip laziness" $+    \(Blind (xs1 :: Infinite Int)) (xs2 :: Map Word Word) ->+      let xs1' = I.take (Map.size xs2) xs1 `I.prependList` undefined+      in I.heteroZip xs1' xs2 === Map.fromList (L.zipWith (\x1 (k, x2) -> (k, (x1, x2))) (I.toList xs1) (Map.toList xs2))+  , testProperty "heteroZipWith laziness" $+    \(curry . applyFun -> (f :: Int -> Word -> Char)) (Blind (xs1 :: Infinite Int)) (xs2 :: Map Word Word) ->+      let xs1' = I.take (Map.size xs2) xs1 `I.prependList` undefined+      in I.heteroZipWith f xs1' xs2 === Map.fromList (L.zipWith (\x1 (k, x2) -> (k, f x1 x2)) (I.toList xs1) (Map.toList xs2))+   , testProperty "unzip" $     \(Blind (xs :: Infinite (Int, Word))) ->       bimap trim trim (I.unzip xs) === L.unzip (trim xs)@@ -368,24 +387,24 @@   , testProperty "lines" $     \(Blind (xs :: Infinite Char)) ->       I.take 3 (I.lines xs) === L.take 3 (L.lines (I.foldr (:) xs))-  , testProperty "lines laziness 1" $+  , testProperty "lines laziness 1" $ once $     L.head (I.head (I.lines ('q' :< undefined))) === 'q'-  , testProperty "lines laziness 2" $+  , testProperty "lines laziness 2" $ once $     L.null (I.head (I.lines ('\n' :< undefined)))   , testProperty "words" $     \(Blind (xs :: Infinite Char)) ->       I.take 3 (I.map NE.toList (I.words xs)) === L.take 3 (L.words (I.foldr (:) xs))-  , testProperty "words laziness" $+  , testProperty "words laziness" $ once $     NE.head (I.head (I.words ('q' :< undefined))) === 'q'   , testProperty "unlines" $     \(Blind (xs :: Infinite [Char])) ->       trim (I.unlines xs) === L.take 10 (L.unlines (trim xs))-  , testProperty "unlines laziness" $+  , testProperty "unlines laziness" $ once $     I.take 2 (I.unlines ("q" :< undefined)) === "q\n"   , testProperty "unwords" $     \(Blind (xs :: Infinite (NonEmpty Char))) ->       trim (I.unwords xs) === L.take 10 (L.unwords (L.map NE.toList (I.foldr (:) xs)))-  , testProperty "unwords laziness" $+  , testProperty "unwords laziness" $ once $     I.take 2 (I.unwords (('q' :| []) :< undefined)) === "q "   , testProperty "unlines . lines" $     \(Blind (xs :: Infinite Char)) ->@@ -395,50 +414,55 @@     \(Blind (ys :: Infinite Ordering)) ->       trim (I.group ys) === L.take 10 (NE.group (I.foldr (:) ys))   , testProperty "groupBy" $-    \(curry . applyFun -> f :: Ordering -> Ordering -> Bool) (Blind ys) ->+    \(curry . applyFun -> (f :: Ordering -> Ordering -> Bool)) (Blind ys) ->       all (\x -> not $ all (f x) [minBound..maxBound]) [minBound..maxBound] ==>         trim (I.groupBy f ys) === L.take 10 (NE.groupBy f (I.foldr (:) ys))-  , testProperty "group laziness" $+  , testProperty "group laziness" $ once $     NE.head (I.head (I.group ('q' :< undefined))) === 'q'   , testProperty "nub" $     \(Blind (ys :: Infinite (Large Int))) ->       fmap getLarge (I.take 3 (I.nub ys)) === fmap getLarge (L.take 3 (L.nub (I.foldr (:) ys)))-  , testProperty "nub laziness" $+  , testProperty "nub laziness" $ once $     I.head (I.nub ('q' :< undefined)) === 'q'+  , testProperty "nubOrd" $+    \(Blind (ys :: Infinite (Large Int))) ->+      fmap getLarge (I.take 3 (I.nubOrd ys)) === fmap getLarge (L.take 3 (L.nub (I.foldr (:) ys)))+  , testProperty "nubOrd laziness" $ once $+    I.head (I.nubOrd ('q' :< undefined)) === 'q'    , testProperty "delete" $     \(x :: Ordering) (Blind xs) ->       trim (I.delete x xs) === L.take 10 (L.delete x (I.foldr (:) xs))-  , testProperty "delete laziness" $+  , testProperty "delete laziness" $ once $     I.head (I.delete 'q' ('w' :< undefined)) === 'w'   , testProperty "insert" $     \(x :: Int) (Blind xs) ->       trim (I.insert x xs) === L.take 10 (L.insert x (I.foldr (:) xs))-  , testProperty "insert laziness" $+  , testProperty "insert laziness" $ once $     I.take 2 (I.insert 'q' ('w' :< undefined)) === "qw"    , testProperty "\\\\" $     \(Blind (xs :: Infinite Ordering)) ys ->       trim (xs I.\\ ys) === L.take 10 (I.foldr (:) xs L.\\ ys)-  , testProperty "\\\\ laziness" $+  , testProperty "\\\\ laziness" $ once $     I.head (('q' :< undefined) I.\\ []) === 'q'   , testProperty "union" $     \xs (Blind (ys :: Infinite Ordering)) ->       I.take 3 (I.union xs ys) === L.take 3 (xs `L.union` I.foldr (:) ys)-  , testProperty "union laziness" $+  , testProperty "union laziness" $ once $     I.head (I.union ('q' : undefined) undefined) === 'q'   , testProperty "intersect" $     \(Blind (xs :: Infinite Ordering)) ys -> not (null ys) ==>       I.head (I.intersect xs ys) === L.head (I.foldr (:) xs `L.intersect` ys)-  , testProperty "intersect laziness" $+  , testProperty "intersect laziness" $ once $     I.head (I.intersect ('q' :< undefined) ('q' : undefined)) === 'q'    , testProperty "inits" $     \(Blind (xs :: Infinite Int)) ->       I.take 21 (I.inits xs) === L.inits (I.take 20 xs)-  , testProperty "inits laziness 1" $+  , testProperty "inits laziness 1" $ once $     L.null (I.head (I.inits undefined))-  , testProperty "inits laziness 2" $+  , testProperty "inits laziness 2" $ once $     I.take 2 (I.inits ('q' :< undefined)) === ["", "q"]   , testProperty "inits1" $     \(Blind (xs :: Infinite Int)) ->@@ -446,28 +470,28 @@   , testProperty "tails" $     \(Blind (xs :: Infinite Int)) ->       map trim (trim (I.tails xs)) === map (L.take 10) (L.take 10 (L.tails (I.take 20 xs)))-  , testProperty "tails laziness" $+  , testProperty "tails laziness" $ once $     I.head (I.head (I.tails ('q' :< undefined))) === 'q'    , testProperty "lookup" $     \(xs :: [(Int, Word)]) y zs ->       let pairs = NE.fromList (xs ++ (y : zs)) in         Just (I.lookup (fst y) (I.cycle pairs)) === L.lookup (fst y) (NE.toList pairs)-  , testProperty "lookup laziness" $+  , testProperty "lookup laziness" $ once $     I.lookup True ((True, 'q') :< undefined) === 'q'   , testProperty "find" $     \(xs :: [(Int, Word)]) y zs ->       let pairs = NE.fromList (xs ++ (y : zs)) in         Just (I.find ((== snd y) . snd) (I.cycle pairs)) === L.find ((== snd y) . snd) (NE.toList pairs)-  , testProperty "find laziness" $+  , testProperty "find laziness" $ once $     I.find odd (1 :< undefined) === (1 :: Int)    , testProperty "filter" $-    \(applyFun -> f :: Int -> Bool) xs (Blind ys) ->+    \(applyFun -> (f :: Int -> Bool)) xs (Blind ys) ->       let us = L.filter f xs in         us === I.take (length us) (I.filter f (I.prependList xs ys))   , testProperty "mapMaybe" $-    \(applyFun -> f :: Int -> Maybe Word) xs (Blind ys) ->+    \(applyFun -> (f :: Int -> Maybe Word)) xs (Blind ys) ->       let us = mapMaybe f xs in         us === I.take (length us) (I.mapMaybe f (I.prependList xs ys))   , testProperty "catMaybes" $@@ -475,12 +499,12 @@       let us = catMaybes xs in         us === I.take (length us) (I.catMaybes (I.prependList xs ys))   , testProperty "partition" $-    \(applyFun -> f :: Int -> Bool) xs (Blind ys) ->+    \(applyFun -> (f :: Int -> Bool)) xs (Blind ys) ->       let (us, vs) = L.partition f xs in         let (us', vs') = I.partition f (I.prependList xs ys) in           us === I.take (length us) us' .&&. vs === I.take (length vs) vs'   , testProperty "mapEither" $-    \(applyFun -> f :: Int -> Either Word Char) xs (Blind ys) ->+    \(applyFun -> (f :: Int -> Either Word Char)) xs (Blind ys) ->       let (us, vs) = mapEither f xs in         let (us', vs') = I.mapEither f (I.prependList xs ys) in           us === I.take (length us) us' .&&. vs === I.take (length vs) vs'@@ -494,7 +518,7 @@     \(Blind (xs :: Infinite Int)) n ->       xs I.!! n === I.foldr (:) xs L.!! fromIntegral n   , testProperty "tabulate" $-    \(applyFun -> f :: Word -> Char) n ->+    \(applyFun -> (f :: Word -> Char)) n ->       I.tabulate f I.!! n === f n    , testProperty "elemIndex" $@@ -507,8 +531,14 @@         let is = L.elemIndices x (xs ++ [x]) in           map fromIntegral (I.take (length is) (I.elemIndices x zs)) === is -  , testProperty ">>= 32bit" $+  , testProperty "for_" $ once $+    I.for_ (0 I....) (\x -> if x > 10 then Left x else Right ()) === Left (11 :: Int)++  , testProperty ">>= 32bit" $ once $     let ix = maxBound :: Word32 in       finiteBitSize (0 :: Word) /= 32 ||         I.head (I.tail (I.genericDrop ix (I.repeat () >>= const (False :< I.repeat True))))+  , testProperty "mfix" $ once $+    (L.take 5 $ fmap (L.take 5) $ mfix $ \fib -> L.map (\n -> 1 : n : L.zipWith (+) fib (L.drop 1 fib)) [2..]) ===+      (I.take 5 $ fmap (I.take 5) $ mfix $ \fib -> I.map (\n -> 1 :< n :< I.zipWith (+) fib (I.drop 1 fib)) ((2 :: Int) I....))   ]