packages feed

ilist (empty) → 0.1.0.0

raw patch · 8 files changed

+1534/−0 lines, 8 filesdep +basedep +criteriondep +hspecsetup-changed

Dependencies added: base, criterion, hspec, ilist, lens, transformers, vector

Files

+ CHANGELOG.md view
@@ -0,0 +1,3 @@+# 0.1.0.0++First release.
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright (c) 2016, Artyom++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Artyom nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ bench/Functions.hs view
@@ -0,0 +1,268 @@+{-# LANGUAGE+MagicHash,+BangPatterns+  #-}+++-- All these functions have to be in a separate module because otherwise+-- fusion breaks for some reason (I've spent a day trying to understand why+-- my definition of 'izipWith' (currently in Data.List.Index) wasn't fusing,+-- before I tried moving it into a different module and it started fusing).+module Functions where+++import qualified Data.Vector as V+import GHC.Exts+import Data.List+import Data.List.Index+import Control.Monad+++indexed_zip :: [a] -> [(Int, a)]+indexed_zip xs = zip [0..] xs+{-# INLINE indexed_zip #-}++indexed_vec :: [a] -> [(Int, a)]+indexed_vec xs = V.toList (V.indexed (V.fromList xs))+{-# INLINE indexed_vec #-}++indexed_rec :: [a] -> [(Int, a)]+indexed_rec xs = go 0# xs+  where+    go i (a:as) = (I# i, a) : go (i +# 1#) as+    go _ _ = []+{-# INLINE indexed_rec #-}++indexed_fold :: [a] -> [(Int, a)]+indexed_fold = ifoldr (\i c -> ((i,c):)) []+{-# INLINE indexed_fold #-}++deleteAt_fold :: Int -> [a] -> [a]+deleteAt_fold n = ifoldr (\i x s -> if n == i then s else x:s) []+{-# INLINE deleteAt_fold #-}++deleteAt_rec :: Int -> [a] -> [a]+deleteAt_rec i ls+  | i < 0 = ls+  | otherwise = go i ls+  where+    go 0 (_:xs) = xs+    go n (x:xs) = x : go (n-1) xs+    go _ [] = []+{-# INLINE deleteAt_rec #-}++imapM_zip :: Monad m => (Int -> a -> m b) -> [a] -> m [b]+imapM_zip f xs = mapM (uncurry f) (zip [0..] xs)+{-# INLINE imapM_zip #-}++imapM_vec :: Monad m => (Int -> a -> m b) -> [a] -> m [b]+imapM_vec f xs = liftM V.toList (V.imapM f (V.fromList xs))+{-# INLINE imapM_vec #-}++imapM_zipWith :: Monad m => (Int -> a -> m b) -> [a] -> m [b]+imapM_zipWith f xs = zipWithM f [0..] xs+{-# INLINE imapM_zipWith #-}++imapM_rec :: Monad m => (Int -> a -> m b) -> [a] -> m [b]+imapM_rec f as = go 0# as+  where+    go _ [] = return []+    go i (x:xs) = do+      x' <- f (I# i) x+      xs' <- go (i +# 1#) xs+      return (x':xs')+{-# INLINE imapM_rec #-}++imapM__zip :: Monad m => (Int -> a -> m b) -> [a] -> m ()+imapM__zip f xs = mapM_ (uncurry f) (zip [0..] xs)+{-# INLINE imapM__zip #-}++imapM__vec :: Monad m => (Int -> a -> m b) -> [a] -> m ()+imapM__vec f xs = V.imapM_ f (V.fromList xs)+{-# INLINE imapM__vec #-}++imapM__zipWith :: Monad m => (Int -> a -> m b) -> [a] -> m ()+imapM__zipWith f xs = zipWithM_ f [0..] xs+{-# INLINE imapM__zipWith #-}++imapM__rec :: Monad m => (Int -> a -> m b) -> [a] -> m ()+imapM__rec f as = go 0# as+  where+    go _ [] = return ()+    go i (x:xs) = do+      f (I# i) x+      go (i +# 1#) xs+{-# INLINE imapM__rec #-}++iall_zip :: (Int -> a -> Bool) -> [a] -> Bool+iall_zip p xs = and (zipWith p [0..] xs)+{-# INLINE iall_zip #-}++iall_map :: (Int -> a -> Bool) -> [a] -> Bool+iall_map f xs = and (imap f xs)+{-# INLINE iall_map #-}++iall_rec :: (Int -> a -> Bool) -> [a] -> Bool+iall_rec p = go 0#+  where+    go _ [] = True+    go i (x:xs) = p (I# i) x && go (i +# 1#) xs+{-# INLINE iall_rec #-}++ifoldr_zip :: (Int -> a -> b -> b) -> b -> [a] -> b+ifoldr_zip f a xs = foldr (\(i, x) acc -> f i x acc) a (zip [0..] xs)+{-# INLINE ifoldr_zip #-}++ifoldr_vec :: (Int -> a -> b -> b) -> b -> [a] -> b+ifoldr_vec f a xs = V.ifoldr f a (V.fromList xs)+{-# INLINE ifoldr_vec #-}++{-+ifoldr1_zip :: (Int -> a -> a -> a) -> [a] -> a+ifoldr1_zip f xs = snd (foldr1 (\(i, x) (j, y) -> (j, f i x y)) (zip [0..] xs))+{-# INLINE ifoldr1_zip #-}+-}++ifoldl_zip :: (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl_zip f a xs = foldl (\acc (!i, x) -> f acc i x) a (zip [0..] xs)+{-# INLINE ifoldl_zip #-}++ifoldl_vec :: (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl_vec f a xs = V.ifoldl f a (V.fromList xs)+{-# INLINE ifoldl_vec #-}++ifoldl'_zip :: (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl'_zip f a xs = foldl' (\acc (!i, x) -> f acc i x) a (zip [0..] xs)+{-# INLINE ifoldl'_zip #-}++ifoldl'_vec :: (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl'_vec f a xs = V.ifoldl' f a (V.fromList xs)+{-# INLINE ifoldl'_vec #-}++ifoldl_fold :: (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl_fold f z xs = foldl (\g x !i -> f (g (i-1)) i x) (const z) xs (length xs - 1)+{-# INLINE ifoldl_fold #-}++ifoldl'_fold :: (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl'_fold f z xs = foldl' (\g x !i -> f (g (i - 1)) i x) (const z) xs (length xs - 1)+{-# INLINE ifoldl'_fold #-}++imap_rec :: (Int -> a -> b) -> [a] -> [b]+imap_rec p = go 0#+  where+    go _ [] = []+    go i (x:xs) = p (I# i) x : go (i +# 1#) xs+{-# INLINE imap_rec #-}++imap_fold :: (Int -> a -> b) -> [a] -> [b]+imap_fold f = ifoldr (\i x xs -> f i x : xs) []+{-# INLINE imap_fold #-}++imap_zip :: (Int -> a -> b) -> [a] -> [b]+imap_zip p xs = zipWith p [0..] xs+{-# INLINE imap_zip #-}++imap_vec :: (Int -> a -> b) -> [a] -> [b]+imap_vec p xs = V.toList (V.imap p (V.fromList xs))+{-# INLINE imap_vec #-}++ifilter_rec :: (Int -> a -> Bool) -> [a] -> [a]+ifilter_rec p = go 0#+  where+    go _ [] = []+    go i (x:xs) | p (I# i) x = x : go (i +# 1#) xs+                | otherwise = go (i +# 1#) xs+{-# INLINE ifilter_rec #-}++ifilter_fold :: (Int -> a -> Bool) -> [a] -> [a]+ifilter_fold p = ifoldr (\i x xs -> if p i x then x : xs else xs) []+{-# INLINE ifilter_fold #-}++ifilter_zip :: (Int -> a -> Bool) -> [a] -> [a]+ifilter_zip p xs = map snd (filter (uncurry p) (zip [0..] xs))+{-# INLINE ifilter_zip #-}++ifilter_vec :: (Int -> a -> Bool) -> [a] -> [a]+ifilter_vec p xs = V.toList (V.ifilter p (V.fromList xs))+{-# INLINE ifilter_vec #-}++ifindIndices_rec :: (Int -> a -> Bool) -> [a] -> [Int]+ifindIndices_rec p = go 0#+  where+    go _ [] = []+    go i (x:xs) | p (I# i) x = I# i : go (i +# 1#) xs+                | otherwise  = go (i +# 1#) xs+{-# INLINE ifindIndices_rec #-}++ifindIndices_fold :: (Int -> a -> Bool) -> [a] -> [Int]+ifindIndices_fold p = ifoldr (\i x xs -> if p i x then i : xs else xs) []+{-# INLINE ifindIndices_fold #-}++ifindIndices_zip :: (Int -> a -> Bool) -> [a] -> [Int]+ifindIndices_zip p xs = map fst (filter (uncurry p) (zip [0..] xs))+{-# INLINE ifindIndices_zip #-}++izipWith_rec :: (Int -> a -> b -> c) -> [a] -> [b] -> [c]+izipWith_rec f = go 0#+  where+    go i (a:as) (b:bs) = f (I# i) a b : go (i +# 1#) as bs+    go _ _ _ = []+{-# INLINE izipWith_rec #-}++izipWith_vec :: (Int -> a -> b -> c) -> [a] -> [b] -> [c]+izipWith_vec f xs ys = V.toList (V.izipWith f (V.fromList xs) (V.fromList ys))+{-# INLINE izipWith_vec #-}++izipWithM_vec :: Monad m => (Int -> a -> b -> m c) -> [a] -> [b] -> m [c]+izipWithM_vec f xs ys =+  liftM V.toList (V.izipWithM f (V.fromList xs) (V.fromList ys))+{-# INLINE izipWithM_vec #-}++izipWithM_rec :: Monad m => (Int -> a -> b -> m c) -> [a] -> [b] -> m [c]+izipWithM_rec f xs ys = go 0# xs ys+  where+    go i (a:as) (b:bs) = do+      c <- f (I# i) a b+      cs <- go (i +# 1#) as bs+      return (c:cs)+    go _ _ _ = return []+{-# INLINE izipWithM_rec #-}++izipWithM__vec :: Monad m => (Int -> a -> b -> m c) -> [a] -> [b] -> m ()+izipWithM__vec f xs ys = V.izipWithM_ f (V.fromList xs) (V.fromList ys)+{-# INLINE izipWithM__vec #-}++izipWithM__rec :: Monad m => (Int -> a -> b -> m c) -> [a] -> [b] -> m ()+izipWithM__rec f xs ys = go 0# xs ys+  where+    go i (a:as) (b:bs) = do+      f (I# i) a b+      go (i +# 1#) as bs+    go _ _ _ = return ()+{-# INLINE izipWithM__rec #-}++imapAccumR_rec+  :: (acc -> Int -> x -> (acc, y))+  -> acc+  -> [x]+  -> (acc, [y])+imapAccumR_rec f z ls = go 0# ls+  where+    go i (x:xs) = let (a'',y ) = f a' (I# i) x+                      (a', ys) = go (i +# 1#) xs+                  in  (a'', y:ys)+    go _ _ = (z, [])+{-# INLINE imapAccumR_rec #-}++imapAccumL_rec+  :: (acc -> Int -> x -> (acc, y))+  -> acc+  -> [x]+  -> (acc, [y])+imapAccumL_rec f z ls = go z 0# ls+  where+    go a i (x:xs) = let (a', y ) = f a (I# i) x+                        (a'',ys) = go a' (i +# 1#) xs+                  in  (a'', y:ys)+    go a _ _ = (a, [])+{-# INLINE imapAccumL_rec #-}
+ bench/Main.hs view
@@ -0,0 +1,228 @@+{-# LANGUAGE+BangPatterns,+MagicHash+  #-}+++import Control.Monad.Trans.State.Lazy++import Criterion+import Criterion.Main++import qualified Control.Lens as L+import Data.List+import Data.List.Index+import Functions+++main :: IO ()+main = defaultMain [++  bgroup "indexed" [+      bgroup "consume" [+          bench "zip" $ nf (\n -> length (indexed_zip [0..n])) (100000::Int),+          bench "vec" $ nf (\n -> length (indexed_vec [0..n])) (100000::Int),+          bench "rec" $ nf (\n -> length (indexed_rec [0..n])) (100000::Int),+          bench "fold" $ nf (\n -> length (indexed_fold [0..n])) (100000::Int),+          bench "lens" $ nf (\n -> length (L.itoList [0..n])) (100000::Int),+          bench "our" $ nf (\n -> length (indexed [0..n])) (100000::Int) ],+      bgroup "full" [+          bench "zip" $ nf (\n -> indexed_zip [0..n]) (100000::Int),+          bench "vec" $ nf (\n -> indexed_vec [0..n]) (100000::Int),+          bench "rec" $ nf (\n -> indexed_rec [0..n]) (100000::Int),+          bench "fold" $ nf (\n -> indexed_fold [0..n]) (100000::Int),+          bench "lens" $ nf (\n -> L.itoList [0..n]) (100000::Int),+          bench "our" $ nf (\n -> indexed [0..n]) (100000::Int) ] ],++  bgroup "deleteAt" [+      bgroup "consume" [+          bench "fold" $ nf (\n -> length (deleteAt_fold 1000 [0..n])) (100000::Int),+          bench "rec" $ nf (\n -> length (deleteAt_rec 1000 [0..n])) (100000::Int),+          bench "our" $ nf (\n -> length (deleteAt 1000 [0..n])) (100000::Int) ],+      bgroup "full" [+          bench "fold" $ nf (\n -> deleteAt_fold 1000 [0..n]) (100000::Int),+          bench "rec" $ nf (\n -> deleteAt_rec 1000 [0..n]) (100000::Int),+          bench "our" $ nf (\n -> deleteAt 1000 [0..n]) (100000::Int) ] ],++  bgroup "iall" [+      bgroup "full" [+          bench "zip" $ nf (\n -> iall_zip (==) [0..n]) 100000,+          bench "map" $ nf (\n -> iall_map (==) [0..n]) 100000,+          bench "rec" $ nf (\n -> iall_rec (==) [0..n]) 100000,+          bench "lens" $ nf (\n -> L.iall (==) [0..n]) 100000,+          bench "our" $ nf (\n -> iall (==) [0..n]) 100000 ],+      bgroup "early" [+          bench "zip" $ nf (\n -> iall_zip (/=) [0..n]) 100000,+          bench "map" $ nf (\n -> iall_map (/=) [0..n]) 100000,+          bench "rec" $ nf (\n -> iall_rec (/=) [0..n]) 100000,+          bench "lens" $ nf (\n -> L.iall (/=) [0..n]) 100000,+          bench "our" $ nf (\n -> iall (/=) [0..n]) 100000 ] ],++  bgroup "imap" [+      bgroup "consume" [+          bench "rec" $ nf (\n -> sum $ imap_rec (+) [0..n]) 100000,+          bench "fold" $ nf (\n -> sum $ imap_fold (+) [0..n]) 100000,+          bench "zip" $ nf (\n -> sum $ imap_zip (+) [0..n]) 100000,+          bench "vec" $ nf (\n -> sum $ imap_vec (+) [0..n]) 100000,+          bench "lens" $ nf (\n -> sum $ L.imap (+) [0..n]) 100000,+          bench "our" $ nf (\n -> sum $ imap (+) [0..n]) 100000 ],+      bgroup "full" [+          bench "rec" $ nf (\n -> imap_rec (+) [0..n]) 100000,+          bench "fold" $ nf (\n -> imap_fold (+) [0..n]) 100000,+          bench "zip" $ nf (\n -> imap_zip (+) [0..n]) 100000,+          bench "vec" $ nf (\n -> imap_vec (+) [0..n]) 100000,+          bench "lens" $ nf (\n -> L.imap (+) [0..n]) 100000,+          bench "our" $ nf (\n -> imap (+) [0..n]) 100000 ] ],++  bgroup "imapM" [+      bgroup "Just" [+          bench "zip" $ nf (\n -> imapM_zip (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "zipWith" $ nf (\n -> imapM_zipWith (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "rec" $ nf (\n -> imapM_rec (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "vec" $ nf (\n -> imapM_vec (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "lens" $ nf (\n -> L.imapM (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "our" $ nf (\n -> imapM (\i x -> if i==x then Just i else Nothing) [0..n]) 100000 ],+      bgroup "State" [+          bench "zip" $ nf (\n -> flip runState [] $ imapM_zip (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "zipWith" $ nf (\n -> flip runState [] $ imapM_zipWith (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "rec" $ nf (\n -> flip runState [] $ imapM_rec (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "vec" $ nf (\n -> flip runState [] $ imapM_vec (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "lens" $ nf (\n -> flip runState [] $ L.imapM (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "our" $ nf (\n -> flip runState [] $ imapM (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000 ] ],++  bgroup "imapM_" [+      bgroup "Just" [+          bench "zip" $ nf (\n -> imapM__zip (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "zipWith" $ nf (\n -> imapM__zipWith (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "rec" $ nf (\n -> imapM__rec (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "vec" $ nf (\n -> imapM__vec (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "lens" $ nf (\n -> L.imapM_ (\i x -> if i==x then Just i else Nothing) [0..n]) 100000,+          bench "our" $ nf (\n -> imapM_ (\i x -> if i==x then Just i else Nothing) [0..n]) 100000 ],+      bgroup "State" [+          bench "zip" $ nf (\n -> flip runState [] $ imapM__zip (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "zipWith" $ nf (\n -> flip runState [] $ imapM__zipWith (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "rec" $ nf (\n -> flip runState [] $ imapM__rec (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "vec" $ nf (\n -> flip runState [] $ imapM__vec (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "lens" $ nf (\n -> flip runState [] $ L.imapM_ (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000,+          bench "our" $ nf (\n -> flip runState [] $ imapM_ (\i x -> modify ((i+x):) >> return (i-x)) [0..n]) 100000 ] ],++  bgroup "ifilter" [+      bgroup "consume" [+          bench "rec" $ nf (\n -> sum $ ifilter_rec (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "fold" $ nf (\n -> sum $ ifilter_fold (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "zip" $ nf (\n -> sum $ ifilter_zip (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "vec" $ nf (\n -> sum $ ifilter_vec (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "our" $ nf (\n -> sum $ ifilter (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "non-indexed" $ nf (\n -> sum $ filter (\x -> rem x 5000 == 0) [0..n]) (100000::Int) ],+      bgroup "full" [+          bench "rec" $ nf (\n -> ifilter_rec (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "fold" $ nf (\n -> ifilter_fold (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "zip" $ nf (\n -> ifilter_zip (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "vec" $ nf (\n -> ifilter_vec (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "our" $ nf (\n -> ifilter (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "non-indexed" $ nf (\n -> filter (\x -> rem x 5000 == 0) [0..n]) (100000::Int) ] ],++  bgroup "ifindIndices" [+      bgroup "consume" [+          bench "rec" $ nf (\n -> sum $ ifindIndices_rec (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "fold" $ nf (\n -> sum $ ifindIndices_fold (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "zip" $ nf (\n -> sum $ ifindIndices_zip (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "our" $ nf (\n -> sum $ ifindIndices (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000 ],+      bgroup "full" [+          bench "rec" $ nf (\n -> ifindIndices_rec (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "fold" $ nf (\n -> ifindIndices_fold (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "zip" $ nf (\n -> ifindIndices_zip (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000,+          bench "our" $ nf (\n -> ifindIndices (\i x -> rem (i+x) 5000 == 0) [0..n]) 100000 ] ],++  bgroup "ifoldr" [+      bench "zip" $ nf (\n -> ifoldr_zip (\i x a -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "vec" $ nf (\n -> ifoldr_vec (\i x a -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "lens" $ nf (\n -> L.ifoldr (\i x a -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "our" $ nf (\n -> ifoldr (\i x a -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "non-indexed" $ nf (\n -> foldr (\x a -> if rem x 16 == 0 then a+3*x else a+x) 0 [0..n]) (100000::Int) ],++{-++  bgroup "ifoldr1" [+      bench "zip" $ nf (\n -> ifoldr1_zip (\i x a -> if rem x 16 == 0 then a+3*i else a+x) [0..n]) 100000,+      bench "our" $ nf (\n -> ifoldr1 (\i x a -> if rem x 16 == 0 then a+3*i else a+x) [0..n]) 100000 ],++-}++  bgroup "ifoldl" [+      bench "zip" $ nf (\n -> ifoldl_zip (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "fold" $ nf (\n -> ifoldl_fold (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "vec" $ nf (\n -> ifoldl_vec (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "lens" $ nf (\n -> L.ifoldl (\i a x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "our" $ nf (\n -> ifoldl (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+      bench "non-indexed" $ nf (\n -> foldl (\a x -> if rem x 16 == 0 then a+3*x else a+x) 0 [0..n]) (100000::Int) ],++  bgroup "ifoldl'" [+      bgroup "if" [+          bench "zip" $ nf (\n -> ifoldl'_zip (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+          bench "fold" $ nf (\n -> ifoldl'_fold (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+          bench "vec" $ nf (\n -> ifoldl'_vec (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+          bench "lens" $ nf (\n -> L.ifoldl' (\i a x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+          bench "our" $ nf (\n -> ifoldl' (\a i x -> if rem x 16 == 0 then a+3*i else a+x) 0 [0..n]) 100000,+          bench "non-indexed" $ nf (\n -> foldl' (\a x -> if rem x 16 == 0 then a+3*x else a+x) 0 [0..n]) (100000::Int) ],+      bgroup "plus" [+          bench "zip" $ nf (\n -> ifoldl'_zip (\a i x -> a+i+x) 0 [0..n]) 100000,+          bench "fold" $ nf (\n -> ifoldl'_fold (\a i x -> a+i+x) 0 [0..n]) 100000,+          bench "vec" $ nf (\n -> ifoldl'_vec (\a i x -> a+i+x) 0 [0..n]) 100000,+          bench "lens" $ nf (\n -> L.ifoldl' (\i a x -> a+i+x) 0 [0..n]) 100000,+          bench "our" $ nf (\n -> ifoldl' (\a i x -> a+i+x) 0 [0..n]) 100000,+          bench "non-indexed" $ nf (\n -> foldl' (\a x -> a+x) 0 [0..n]) (100000::Int) ] ],++  bgroup "imapAccumR" [+      bench "rec" $ nf (\n -> imapAccumR_rec (\a i x -> (2*a+i*x, x*2)) 0 [0..n]) 100000,+      bench "lens" $ nf (\n -> L.imapAccumR (\i a x -> (2*a+i*x, x*2)) 0 [0..n]) 100000,+      bench "our" $ nf (\n -> imapAccumR (\a i x -> (2*a+i*x, x*2)) 0 [0..n]) 100000,+      bench "non-indexed" $ nf (\n -> mapAccumR (\a x -> (2*a+a*x, x*2)) (0::Int) [0..n]) 100000 ],++  bgroup "imapAccumL" [+      bench "rec" $ nf (\n -> imapAccumL_rec (\a i x -> (2*a+i*x, x*2)) 0 [0..n]) 100000,+      bench "lens" $ nf (\n -> imapAccumL (\i a x -> (2*a+i*x, x*2)) 0 [0..n]) 100000,+      bench "our" $ nf (\n -> imapAccumL (\a i x -> (2*a+i*x, x*2)) 0 [0..n]) 100000,+      bench "non-indexed" $ nf (\n -> mapAccumL (\a x -> (2*a+a*x, x*2)) (0::Int) [0..n]) 100000 ],++  bgroup "ifoldrM" [+      bgroup "Just" [+          bench "lens" $ nf (\n -> L.ifoldrM (\i x a -> if i==x then Just (i+a+x) else Nothing) 0 [0..n]) 100000,+          bench "our" $ nf (\n -> ifoldrM (\i x a -> if i==x then Just (i+a+x) else Nothing) 0 [0..n]) 100000 ] ],++  bgroup "ifoldlM" [+      bgroup "Just" [+          bench "lens" $ nf (\n -> L.ifoldlM (\i a x -> if i==x then Just (i+a+x) else Nothing) 0 [0..n]) 100000,+          bench "our" $ nf (\n -> ifoldlM (\a i x -> if i==x then Just (i+a+x) else Nothing) 0 [0..n]) 100000 ] ],+  +  bgroup "izipWith" [+      bgroup "consume" [+          bench "rec" $ nf (\n -> sum $ izipWith_rec (\i x y -> i+x+y) [0..n] [0..n]) 100000,+          bench "vec" $ nf (\n -> sum $ izipWith_vec (\i x y -> i+x+y) [0..n] [0..n]) 100000,+          bench "our" $ nf (\n -> sum $ izipWith (\i x y -> i+x+y) [0..n] [0..n]) 100000,+          bench "non-indexed" $ nf (\n -> sum $ zipWith (\x y -> x+y) [0..n] [0..n]) (100000::Int) ],+      bgroup "full" [+          bench "rec" $ nf (\n -> izipWith_rec (\i x y -> i+x+y) [0..n] [0..n]) 100000,+          bench "vec" $ nf (\n -> izipWith_vec (\i x y -> i+x+y) [0..n] [0..n]) 100000,+          bench "our" $ nf (\n -> izipWith (\i x y -> i+x+y) [0..n] [0..n]) 100000,+          bench "non-indexed" $ nf (\n -> zipWith (\x y -> x+y) [0..n] [0..n]) (100000::Int) ] ],++  bgroup "izipWithM" [+      bgroup "Just" [+          bench "rec" $ nf (\n -> izipWithM_rec (\i x y -> if i==x&&x==y then Just i else Nothing) [0..n] [0..n]) 100000,+          bench "vec" $ nf (\n -> izipWithM_vec (\i x y -> if i==x&&x==y then Just i else Nothing) [0..n] [0..n]) 100000,+          bench "our" $ nf (\n -> izipWithM (\i x y -> if i==x&&x==y then Just i else Nothing) [0..n] [0..n]) 100000 ],+      bgroup "State" [+          bench "rec" $ nf (\n -> flip runState [] $ izipWithM_rec (\i x y -> modify ((i+x+y):) >> return (i-x)) [0..n] [0..n]) 100000,+          bench "vec" $ nf (\n -> flip runState [] $ izipWithM_vec (\i x y -> modify ((i+x+y):) >> return (i-x)) [0..n] [0..n]) 100000,+          bench "our" $ nf (\n -> flip runState [] $ izipWithM (\i x y -> modify ((i+x+y):) >> return (i-x)) [0..n] [0..n]) 100000 ] ],++  bgroup "izipWithM_" [+      bgroup "Just" [+          bench "rec" $ nf (\n -> izipWithM__rec (\i x y -> if i==x&&x==y then Just i else Nothing) [0..n] [0..n]) 100000,+          bench "vec" $ nf (\n -> izipWithM__vec (\i x y -> if i==x&&x==y then Just i else Nothing) [0..n] [0..n]) 100000,+          bench "our" $ nf (\n -> izipWithM_ (\i x y -> if i==x&&x==y then Just i else Nothing) [0..n] [0..n]) 100000 ],+      bgroup "State" [+          bench "rec" $ nf (\n -> flip runState [] $ izipWithM__rec (\i x y -> modify ((i+x+y):) >> return (i-x)) [0..n] [0..n]) 100000,+          bench "vec" $ nf (\n -> flip runState [] $ izipWithM__vec (\i x y -> modify ((i+x+y):) >> return (i-x)) [0..n] [0..n]) 100000,+          bench "our" $ nf (\n -> flip runState [] $ izipWithM_ (\i x y -> modify ((i+x+y):) >> return (i-x)) [0..n] [0..n]) 100000 ] ] ]
+ ilist.cabal view
@@ -0,0 +1,56 @@+name:                ilist+version:             0.1.0.0+synopsis:            Optimised list functions for doing index-related things+description:+  Optimised list functions for doing index-related things. They're faster than common idioms in all cases, and sometimes they fuse better as well.+homepage:            http://github.com/aelve/ilist+bug-reports:         http://github.com/aelve/ilist/issues+license:             BSD3+license-file:        LICENSE+author:              Artyom+maintainer:          yom@artyom.me+-- copyright:           +category:            List+tested-with:         GHC == 7.4.2, GHC == 7.6.3, GHC == 7.8.4, GHC == 7.10.3, GHC == 8.0.1+build-type:          Simple+extra-source-files:  CHANGELOG.md+cabal-version:       >=1.10++source-repository head+  type:                git+  location:            git://github.com/aelve/ilist.git++library+  exposed-modules:     Data.List.Index+  -- other-modules:       +  -- other-extensions:    +  build-depends:       base >=4.5 && <5+  ghc-options:         -O2 -Wall -fno-warn-unused-do-bind+  hs-source-dirs:      lib+  default-language:    Haskell2010++test-suite tests+  type:                exitcode-stdio-1.0+  main-is:             Main.hs+  build-depends:       base+                     , hspec+                     , ilist+                     , transformers+  ghc-options:         -O2 -Wall -fno-warn-unused-do-bind+  hs-source-dirs:      tests+  default-language:    Haskell2010++benchmark bench+  type:                exitcode-stdio-1.0+  main-is:             Main.hs+  other-modules:       Functions+  build-depends:       base+                     , criterion+                     , ilist+                     -- imapM_ is broken in 4.13.2+                     , lens >= 4.13.2.1+                     , transformers+                     , vector+  ghc-options:         -O2 -Wall -fno-warn-unused-do-bind+  hs-source-dirs:      bench+  default-language:    Haskell2010
+ lib/Data/List/Index.hs view
@@ -0,0 +1,621 @@+{-# LANGUAGE+CPP,+MagicHash,+ScopedTypeVariables,+BangPatterns+  #-}+++{- |+Note: a lot of these functions are available for other types (in their respective packages):++  * @<http://hackage.haskell.org/package/vector/docs/Data-Vector.html Data.Vector>@ provides 'indexed' and lots of other functions beginning with “i”.++  * @<http://hackage.haskell.org/package/containers/docs/Data-Map-Lazy.html Data.Map>@ and @<http://hackage.haskell.org/package/containers/docs/Data-Sequence.html Data.Sequence>@ provide similar functions, but use a different naming convention (e.g. @<http://hackage.haskell.org/package/containers/docs/Data-Map-Lazy.html#v:mapWithKey mapWithKey>@ for maps and @<http://hackage.haskell.org/package/containers/docs/Data-Sequence.html#v:foldrWithIndex foldrWithIndex>@ for sequences).++  * <http://hackage.haskell.org/package/lens lens> provides several typeclasses for indexed functions that work on maps, lists, vectors, bytestrings, and so on (in @<http://hackage.haskell.org/package/lens/docs/Control-Lens-Indexed.html Control.Lens.Indexed>@), but unfortunately they are pretty slow for lists.+-}+module Data.List.Index+(+  -- * Original functions+  indexed,+  deleteAt,+  setAt,+  modifyAt,+  updateAt,+  insertAt,++  -- * Adapted functions from "Data.List"+  -- $adapted++  -- ** Maps+  imap,+  imapM, imapM_,+  ifor, ifor_,+  -- ** Folds+  ifoldr, ifoldl, ifoldl',+  iall, iany, iconcatMap,+  -- ** Sublists+  ifilter, ipartition,+  itakeWhile, idropWhile,+  -- ** Zipping+  izipWith,+  izipWithM, izipWithM_,+  -- ** Search+  ifind,+  ifindIndex,+  ifindIndices,++  -- * Less commonly used functions++  -- ** Zipping+  izipWith3,+  izipWith4,+  izipWith5,+  izipWith6,+  izipWith7,++  -- ** Monadic functions+  iforM, iforM_,+  itraverse, itraverse_,+  ifoldrM,+  ifoldlM,+  +  -- ** Folds+  ifoldMap,+  imapAccumR,+  imapAccumL,+)+where+++#if __GLASGOW_HASKELL__ >= 710+import GHC.Base (oneShot)+#define ONE_SHOT oneShot+#else+#define ONE_SHOT+#endif++#if __GLASGOW_HASKELL__ < 710+import Control.Applicative+#endif++import Data.Maybe+import Data.Monoid+import GHC.Exts++{- Left to do:++Functions+~~~~~~~~~++alterF or something?++iscanl+iscanl'+iscanl1+iscanr+iscanr1++iiterate?++backpermute?+minIndex/maxIndex?+-}++{- |+'indexed' pairs each element with its index.++>>> indexed "hello"+[(0,'h'),(1,'e'),(2,'l'),(3,'l'),(4,'o')]++/Subject to fusion./+-}+indexed :: [a] -> [(Int, a)]+indexed xs = go 0# xs+  where+    go i (a:as) = (I# i, a) : go (i +# 1#) as+    go _ _ = []+{-# NOINLINE [1] indexed #-}++indexedFB :: ((Int, a) -> t -> t) -> a -> (Int# -> t) -> Int# -> t+indexedFB c = \x cont i -> (I# i, x) `c` cont (i +# 1#)+{-# INLINE [0] indexedFB #-}++{-# RULES+"indexed"       [~1] forall xs.    indexed xs = build (\c n -> foldr (indexedFB c) (\_ -> n) xs 0#)+"indexedList"   [1]  forall xs.    foldr (indexedFB (:)) (\_ -> []) xs 0# = indexed xs+  #-}++{- |+'deleteAt' deletes the element at an index.++If the index is negative or exceeds list length, the original list will be returned.+-}+deleteAt :: Int -> [a] -> [a]+deleteAt i ls+  | i < 0 = ls+  | otherwise = go i ls+  where+    go 0 (_:xs) = xs+    go n (x:xs) = x : go (n-1) xs+    go _ [] = []+{-# INLINE deleteAt #-}++{- |+'setAt' sets the element at the index.++If the index is negative or exceeds list length, the original list will be returned.+-}+setAt :: Int -> a -> [a] -> [a]+setAt i a ls+  | i < 0 = ls+  | otherwise = go i ls+  where+    go 0 (_:xs) = a : xs+    go n (x:xs) = x : go (n-1) xs+    go _ [] = []+{-# INLINE setAt #-}++{- |+'modifyAt' applies a function to the element at the index.++If the index is negative or exceeds list length, the original list will be returned.+-}+modifyAt :: Int -> (a -> a) -> [a] -> [a]+modifyAt i f ls+  | i < 0 = ls+  | otherwise = go i ls+  where+    go 0 (x:xs) = f x : xs+    go n (x:xs) = x : go (n-1) xs+    go _ [] = []+{-# INLINE modifyAt #-}++{- |+'updateAt' applies a function to the element at the index, and then either replaces the element or deletes it (if the function has returned 'Nothing').++If the index is negative or exceeds list length, the original list will be returned.+-}+updateAt :: Int -> (a -> Maybe a) -> [a] -> [a]+updateAt i f ls+  | i < 0 = ls+  | otherwise = go i ls+  where+    go 0 (x:xs) = case f x of+      Nothing -> xs+      Just x' -> x' : xs+    go n (x:xs) = x : go (n-1) xs+    go _ [] = []+{-# INLINE updateAt #-}++{- |+'insertAt' inserts an element at the given position:++@+(insertAt i x xs) !! i == x+@++If the index is negative or exceeds list length, the original list will be returned. (If the index is equal to the list length, the insertion can be carried out.)+-}+insertAt :: Int -> a -> [a] -> [a]+insertAt i a ls+  | i < 0 = ls+  | otherwise = go i ls+  where+    go 0 xs = a : xs+    go n (x:xs) = x : go (n-1) xs+    go _ [] = []+{-# INLINE insertAt #-}++{-++David Feuer says that drop-like functions tend to have problems when implemented with folds: <http://ircbrowse.net/browse/haskell?id=22794495&timestamp=1463607633#t1463607633>. I haven't been able to observe this, but since Data.List defines drop/dropWhile/etc that don't fuse, let's do it here as well – just in case. The original version (that does fuse) is below.++-- The plan is that if it does inline, it'll be fast; and if it doesn't+-- inline, the former definition will be used and sharing will be preserved+-- (i.e. if i == 0, it won't rebuild the whole list).+deleteAtFB :: Int -> (a -> t -> t) -> a -> (Int# -> t) -> Int# -> t+deleteAtFB (I# i) c = \x r k ->+  case k ==# i of+    0# -> x `c` r (k +# 1#)+    _  -> r (k +# 1#)+{-# INLINE [0] deleteAtFB #-}++{-# RULES+"deleteAt"       [~1] forall i xs.    deleteAt i xs = build (\c n -> foldr (deleteAtFB i c) (\_ -> n) xs 0#)+"deleteAtList"   [1]  forall i xs.    foldr (deleteAtFB i (:)) (\_ -> []) xs 0# = deleteAt i xs+  #-}++-}++{- $adapted++These functions mimic their counterparts in "Data.List" – 'imap', for instance, works like 'map' but gives the index of the element to the modifying function.++Note that left folds have the index argument /after/ the accumulator argument – that's the convention adopted by containers and vector (but not lens).+-}++{- |+/Subject to fusion./+-}+imap :: (Int -> a -> b) -> [a] -> [b]+imap f ls = go 0# ls+  where+    go i (x:xs) = f (I# i) x : go (i +# 1#) xs+    go _ _ = []+{-# NOINLINE [1] imap #-}++imapFB+  :: (b -> t -> t) -> (Int -> a -> b) -> a -> (Int# -> t) -> Int# -> t+imapFB c f = \x r k -> f (I# k) x `c` r (k +# 1#)+{-# INLINE [0] imapFB #-}++{-# RULES+"imap"       [~1] forall f xs.    imap f xs = build (\c n -> foldr (imapFB c f) (\_ -> n) xs 0#)+"imapList"   [1]  forall f xs.    foldr (imapFB (:) f) (\_ -> []) xs 0# = imap f xs+  #-}++{-+Note: we don't apply the *FB transformation to 'iconcatMap' because it uses 'ifoldr' instead of 'foldr', and 'ifoldr' might get inlined itself, and rewriting 'iconcatMap' with 'foldr' instead of 'ifoldr' is annoying. So, in theory it's a small optimisation possibility (in practice I'm not so sure, given that functions with 'build' don't seem to perform worse than functions without it).+-}+iconcatMap :: (Int -> a -> [b]) -> [a] -> [b]+iconcatMap f xs = build $ \c n ->+  ifoldr (\i x b -> foldr c b (f i x)) n xs+{-# INLINE iconcatMap #-}++ifoldMap :: Monoid m => (Int -> a -> m) -> [a] -> m+ifoldMap p ls = foldr go (\_ -> mempty) ls 0#+  where go x r k = p (I# k) x <> r (k +# 1#)+{-# INLINE ifoldMap #-}++{- |+/Subject to fusion./+-}+iall :: (Int -> a -> Bool) -> [a] -> Bool+iall p ls = foldr go (\_ -> True) ls 0#+  where go x r k = p (I# k) x && r (k +# 1#)+{-# INLINE iall #-}++{- |+/Subject to fusion./+-}+iany :: (Int -> a -> Bool) -> [a] -> Bool+iany p ls = foldr go (\_ -> False) ls 0#+  where go x r k = p (I# k) x || r (k +# 1#)+{-# INLINE iany #-}++imapM :: Monad m => (Int -> a -> m b) -> [a] -> m [b]+imapM f as = ifoldr k (return []) as+  where+    k i a r = do+      x <- f i a+      xs <- r+      return (x:xs)+{-# INLINE imapM #-}++iforM :: Monad m => [a] -> (Int -> a -> m b) -> m [b]+iforM = flip imapM+{-# INLINE iforM #-}++itraverse :: Applicative m => (Int -> a -> m b) -> [a] -> m [b]+itraverse f as = ifoldr k (pure []) as+  where+    k i a r = (:) <$> f i a <*> r+{-# INLINE itraverse #-}++ifor :: Applicative m => [a] -> (Int -> a -> m b) -> m [b]+ifor = flip itraverse+{-# INLINE ifor #-}++{- |+/Subject to fusion./+-}+imapM_ :: Monad m => (Int -> a -> m b) -> [a] -> m ()+imapM_ f as = ifoldr k (return ()) as+  where+    k i a r = f i a >> r+{-# INLINE imapM_ #-}++{- |+/Subject to fusion./+-}+iforM_ :: Monad m => [a] -> (Int -> a -> m b) -> m ()+iforM_ = flip imapM_+{-# INLINE iforM_ #-}++{- |+/Subject to fusion./+-}+itraverse_ :: Applicative m => (Int -> a -> m b) -> [a] -> m ()+itraverse_ f as = ifoldr k (pure ()) as+  where+    k i a r = f i a *> r+{-# INLINE itraverse_ #-}++{- |+/Subject to fusion./+-}+ifor_ :: Applicative m => [a] -> (Int -> a -> m b) -> m ()+ifor_ = flip itraverse_+{-# INLINE ifor_ #-}++-- Using unboxed ints here doesn't seem to result in any benefit+ifoldr :: (Int -> a -> b -> b) -> b -> [a] -> b+ifoldr f z xs = foldr (\x g i -> f i x (g (i+1))) (const z) xs 0+{-# INLINE ifoldr #-}++ifoldrM :: Monad m => (Int -> a -> b -> m b) -> b -> [a] -> m b+ifoldrM f z xs = ifoldr k (return z) xs+  where+    k i a r = f i a =<< r+{-# INLINE ifoldrM #-}++imapAccumR+  :: (acc -> Int -> x -> (acc, y))+  -> acc+  -> [x]+  -> (acc, [y])+imapAccumR f z xs =+  foldr (\x g i -> let (a, ys) = g (i+1)+                       (a', y) = f a i x+                   in  (a', y:ys))+        (const (z, [])) xs 0+{-# INLINE imapAccumR #-}++{-++ifoldr1 :: (Int -> a -> a -> a) -> [a] -> a+ifoldr1 f = go 0#+  where go _ [x]    = x+        go i (x:xs) = f (I# i) x (go (i +# 1#) xs)+        go _ []     = errorEmptyList "ifoldr1"+{-# INLINE [0] ifoldr1 #-}++-}++{- |+The index isn't the first argument of the function because that's the convention adopted by containers and vector (but not lens).++/Subject to fusion./+-}+ifoldl :: forall a b. (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl k z0 xs =+  foldr (\(v::a) (fn :: (Int, b) -> b) ->+          ONE_SHOT (\((!i)::Int, z::b) -> fn (i+1, k z i v)))+        (snd :: (Int, b) -> b)+        xs+        (0, z0)+{-# INLINE ifoldl #-}++{- |+/Subject to fusion./+-}+ifoldl' :: forall a b. (b -> Int -> a -> b) -> b -> [a] -> b+ifoldl' k z0 xs =+  foldr (\(v::a) (fn :: (Int, b) -> b) ->+          ONE_SHOT (\((!i)::Int, z::b) -> z `seq` fn (i+1, k z i v)))+        (snd :: (Int, b) -> b)+        xs+        (0, z0)+{-# INLINE ifoldl' #-}++{- |+/Subject to fusion./+-}+ifoldlM :: Monad m => (b -> Int -> a -> m b) -> b -> [a] -> m b+ifoldlM f z xs = ifoldl k (return z) xs+  where+    k a i r = do a' <- a; f a' i r+{-# INLINE ifoldlM #-}++imapAccumL+  :: (acc -> Int -> x -> (acc, y))+  -> acc+  -> [x]+  -> (acc, [y])+imapAccumL f z xs =+  foldr (\(x::a) (r :: (Int,acc) -> (acc,[y])) ->+          ONE_SHOT (\((!i)::Int, s::acc) ->+            let (s', y)   = f s i x+                (s'', ys) = r (i+1, s')+            in (s'', y:ys)))+        ((\(_, a) -> (a, [])) :: (Int,acc) -> (acc,[y]))+        xs+        (0, z)+{-# INLINE imapAccumL #-}++{-++ifoldl1 :: (a -> Int -> a -> a) -> [a] -> a+ifoldl1 f (x:xs) = ifoldl f x xs+ifoldl1 _ []     = errorEmptyList "ifoldl1"++ifoldl1' :: (a -> Int -> a -> a) -> [a] -> a+ifoldl1' f (x:xs) = ifoldl' f x xs+ifoldl1' _ []     = errorEmptyList "ifoldl1'"++-}++ifilter :: (Int -> a -> Bool) -> [a] -> [a]+ifilter p ls = go 0# ls+  where+    go i (x:xs) | p (I# i) x = x : go (i +# 1#) xs+                | otherwise  = go (i +# 1#) xs+    go _ _ = []+{-# NOINLINE [1] ifilter #-}++ifilterFB+  :: (a -> t -> t) -> (Int -> a -> Bool) -> a -> (Int# -> t) -> Int# -> t+ifilterFB c p = \x r k ->+  if p (I# k) x then x `c` r (k +# 1#) else r (k +# 1#)+{-# INLINE [0] ifilterFB #-}++{-# RULES+"ifilter"       [~1] forall p xs.    ifilter p xs = build (\c n -> foldr (ifilterFB c p) (\_ -> n) xs 0#)+"ifilterList"   [1]  forall p xs.    foldr (ifilterFB (:) p) (\_ -> []) xs 0# = ifilter p xs+  #-}++itakeWhile :: (Int -> a -> Bool) -> [a] -> [a]+itakeWhile p ls = go 0# ls+  where+    go i (x:xs) | p (I# i) x = x : go (i +# 1#) xs+                | otherwise  = []+    go _ _ = []+{-# NOINLINE [1] itakeWhile #-}++itakeWhileFB+  :: (a -> t -> t) -> (Int -> a -> Bool) -> t -> a -> (Int# -> t) -> Int# -> t+itakeWhileFB c p n = \x r k ->+  if p (I# k) x then x `c` r (k +# 1#) else n+{-# INLINE [0] itakeWhileFB #-}++{-# RULES+"itakeWhile"       [~1] forall p xs.    itakeWhile p xs = build (\c n -> foldr (itakeWhileFB c p n) (\_ -> n) xs 0#)+"itakeWhileList"   [1]  forall p xs.    foldr (itakeWhileFB (:) p []) (\_ -> []) xs 0# = itakeWhile p xs+  #-}++idropWhile :: (Int -> a -> Bool) -> [a] -> [a]+idropWhile p ls = go 0# ls+  where+    go i (x:xs) | p (I# i) x = go (i +# 1#) xs+                | otherwise  = x:xs+    go _ [] = []+{-# INLINE idropWhile #-}++ipartition :: (Int -> a -> Bool) -> [a] -> ([a],[a])+ipartition p xs = ifoldr (iselect p) ([],[]) xs+{-# INLINE ipartition #-}++iselect :: (Int -> a -> Bool) -> Int -> a -> ([a], [a]) -> ([a], [a])+iselect p i x ~(ts,fs) | p i x     = (x:ts,fs)+                       | otherwise = (ts, x:fs)++ifind :: (Int -> a -> Bool) -> [a] -> Maybe a+ifind p = listToMaybe . ifilter p++ifindIndex :: (Int -> a -> Bool) -> [a] -> Maybe Int+ifindIndex p = listToMaybe . ifindIndices p++ifindIndices :: (Int -> a -> Bool) -> [a] -> [Int]+ifindIndices p ls = go 0# ls+  where+    go _ [] = []+    go i (x:xs) | p (I# i) x = I# i : go (i +# 1#) xs+                | otherwise  = go (i +# 1#) xs+{-# NOINLINE [1] ifindIndices #-}++ifindIndicesFB+  :: (Int -> t -> t) -> (Int -> a -> Bool) -> a -> (Int# -> t) -> Int# -> t+ifindIndicesFB c p = \x r k ->+  if p (I# k) x then I# k `c` r (k +# 1#) else r (k +# 1#)+{-# INLINE [0] ifindIndicesFB #-}++{-# RULES+"ifindIndices"       [~1] forall p xs.    ifindIndices p xs = build (\c n -> foldr (ifindIndicesFB c p) (\_ -> n) xs 0#)+"ifindIndicesList"   [1]  forall p xs.    foldr (ifindIndicesFB (:) p) (\_ -> []) xs 0# = ifindIndices p xs+  #-}++{-++errorEmptyList :: String -> a+errorEmptyList fun = error ("Data.List.Index." ++ fun ++ ": empty list")++-}++{- |+/Subject to fusion in the first argument./+-}+izipWith :: (Int -> a -> b -> c) -> [a] -> [b] -> [c]+izipWith fun xs ys = go 0# xs ys+  where+    go i (a:as) (b:bs) = fun (I# i) a b : go (i +# 1#) as bs+    go _ _ _ = []+{-# NOINLINE [1] izipWith #-}++izipWithFB+  :: (c -> t -> t) -> (Int -> a -> b -> c) -> a -> b -> (Int# -> t) -> Int# -> t+izipWithFB c fun = \x y cont i -> fun (I# i) x y `c` cont (i +# 1#)+{-# INLINE [0] izipWithFB #-}++{-# RULES+"izipWith"       [~1] forall f xs ys.    izipWith f xs ys = build (\c n -> foldr2 (izipWithFB c f) (\_ -> n) xs ys 0#)+"izipWithList"   [1]  forall f xs ys.    foldr2 (izipWithFB (:) f) (\_ -> []) xs ys 0# = izipWith f xs ys+  #-}++-- Copied from GHC.List++foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c+foldr2 k z = go+  where+        go []    _ys     = z+        go _xs   []      = z+        go (x:xs) (y:ys) = k x y (go xs ys)+{-# INLINE [0] foldr2 #-}++foldr2_left :: (a -> b -> c -> d) -> d -> a -> ([b] -> c) -> [b] -> d+foldr2_left _k  z _x _r []     = z+foldr2_left  k _z  x  r (y:ys) = k x y (r ys)++{-# RULES+"foldr2/left"   forall k z ys (g::forall b.(a->b->b)->b->b) .+                  foldr2 k z (build g) ys = g (foldr2_left  k z) (\_ -> z) ys+ #-}++izipWith3+  :: (Int -> a -> b -> c -> d)+  -> [a] -> [b] -> [c] -> [d]+izipWith3 fun = go 0#+  where+    go i (a:as) (b:bs) (c:cs) =+      fun (I# i) a b c : go (i +# 1#) as bs cs+    go _ _ _ _ = []+{-# INLINE izipWith3 #-}++izipWith4+  :: (Int -> a -> b -> c -> d -> e)+  -> [a] -> [b] -> [c] -> [d] -> [e]+izipWith4 fun = go 0#+  where+    go i (a:as) (b:bs) (c:cs) (d:ds) =+      fun (I# i) a b c d : go (i +# 1#) as bs cs ds+    go _ _ _ _ _ = []+{-# INLINE izipWith4 #-}++izipWith5+  :: (Int -> a -> b -> c -> d -> e -> f)+  -> [a] -> [b] -> [c] -> [d] -> [e] -> [f]+izipWith5 fun = go 0#+  where+    go i (a:as) (b:bs) (c:cs) (d:ds) (e:es) =+      fun (I# i) a b c d e : go (i +# 1#) as bs cs ds es+    go _ _ _ _ _ _ = []+{-# INLINE izipWith5 #-}++izipWith6+  :: (Int -> a -> b -> c -> d -> e -> f -> g)+  -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g]+izipWith6 fun = go 0#+  where+    go i (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) =+      fun (I# i) a b c d e f : go (i +# 1#) as bs cs ds es fs+    go _ _ _ _ _ _ _ = []+{-# INLINE izipWith6 #-}++izipWith7+  :: (Int -> a -> b -> c -> d -> e -> f -> g -> h)+  -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [h]+izipWith7 fun = go 0#+  where+    go i (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs) =+      fun (I# i) a b c d e f g : go (i +# 1#) as bs cs ds es fs gs+    go _ _ _ _ _ _ _ _ = []+{-# INLINE izipWith7 #-}++izipWithM :: Monad m => (Int -> a -> b -> m c) -> [a] -> [b] -> m [c]+izipWithM f as bs = sequence (izipWith f as bs)+{-# INLINE izipWithM #-}++izipWithM_ :: Monad m => (Int -> a -> b -> m c) -> [a] -> [b] -> m ()+izipWithM_ f as bs = sequence_ (izipWith f as bs)+{-# INLINE izipWithM_ #-}
+ tests/Main.hs view
@@ -0,0 +1,326 @@+import Control.Exception+import Control.Monad+import Control.Monad.Trans.State.Lazy+import Data.List++import Data.List.Index++import Test.Hspec+++main :: IO ()+main = hspec $ do+  newFunctions+  transformations+  monadicFunctions+  specialFolds+  folds+  sublists+  search+  zipping+  buildingLists++newFunctions :: Spec+newFunctions = describe "new functions" $ do+  describe "indexed" $ do+    specify "basic" $ do+      indexed [1,2,3] `shouldBe` [(0,1),(1,2),(2,3::Int)]+    specify "empty" $ do+      indexed [] `shouldBe` ([] :: [(Int,Bool)])+    specify "undefined" $ do+      take 1 (indexed (1:undefined)) `shouldBe` [(0,1::Int)]+    specify "infinite" $ do+      take 2 (indexed [1..]) `shouldBe` [(0,1),(1,2::Int)]++  describe "deleteAt" $ do+    specify "basic" $ do+      deleteAt 0 [0,1,2] `shouldBe` [1,2::Int]+      deleteAt 1 [0,1,2] `shouldBe` [0,2::Int]+    specify "empty" $ do+      deleteAt 0 [] `shouldBe` ([]::[Bool])+    specify "undefined" $ do+      take 1 (deleteAt 0 (1:2:undefined)) `shouldBe` [2::Int]+    specify "infinite" $ do+      take 2 (deleteAt 1 [1..]) `shouldBe` [1,3::Int]+    specify "negative" $ do+      deleteAt (-1) [1,2] `shouldBe` [1,2::Int]+    specify "excessive" $ do+      deleteAt 5 [1,2] `shouldBe` [1,2::Int]++  describe "setAt" $ do+    specify "basic" $ do+      setAt 0 8 [0,1,2] `shouldBe` [8,1,2::Int]+      setAt 1 8 [0,1,2] `shouldBe` [0,8,2::Int]+    specify "empty" $ do+      setAt 0 undefined [] `shouldBe` ([]::[Bool])+    specify "undefined" $ do+      take 1 (setAt 0 8 (1:2:undefined)) `shouldBe` [8::Int]+    specify "infinite" $ do+      take 2 (setAt 1 8 [1..]) `shouldBe` [1,8::Int]+    specify "negative" $ do+      setAt (-1) undefined [1,2] `shouldBe` [1,2::Int]+    specify "excessive" $ do+      setAt 2 undefined [1,2] `shouldBe` [1,2::Int]++  describe "modifyAt" $ do+    specify "basic" $ do+      modifyAt 0 succ [0,1,2] `shouldBe` [1,1,2::Int]+      modifyAt 1 succ [0,1,2] `shouldBe` [0,2,2::Int]+    specify "empty" $ do+      modifyAt 0 undefined [] `shouldBe` ([]::[Bool])+    specify "undefined" $ do+      take 2 (modifyAt 0 succ (1:2:undefined)) `shouldBe` [2,2::Int]+    specify "infinite" $ do+      take 2 (modifyAt 1 succ [1..]) `shouldBe` [1,3::Int]+    specify "negative" $ do+      modifyAt (-1) undefined [1,2] `shouldBe` [1,2::Int]+    specify "excessive" $ do+      modifyAt 2 undefined [1,2] `shouldBe` [1,2::Int]++  describe "updateAt" $ do+    specify "modify" $ do+      updateAt 0 (Just . succ) [0,1,2] `shouldBe` [1,1,2::Int]+      updateAt 1 (Just . succ) [0,1,2] `shouldBe` [0,2,2::Int]+    specify "delete" $ do+      updateAt 0 (\_ -> Just 8) [0,1,2] `shouldBe` [8,1,2::Int]+      updateAt 1 (\_ -> Just 8) [0,1,2] `shouldBe` [0,8,2::Int]+    specify "empty" $ do+      updateAt 0 undefined [] `shouldBe` ([]::[Bool])+    specify "undefined" $ do+      take 1 (updateAt 0 (\_ -> Just 8) (1:2:undefined)) `shouldBe` [8::Int]+    specify "infinite" $ do+      take 2 (updateAt 1 (\_ -> Nothing) [1..]) `shouldBe` [1,3::Int]+    specify "negative" $ do+      updateAt (-1) undefined [1,2] `shouldBe` [1,2::Int]+    specify "excessive" $ do+      updateAt 2 undefined [1,2] `shouldBe` [1,2::Int]++  describe "insertAt" $ do+    specify "basic" $ do+      insertAt 0 8 [0,1,2] `shouldBe` [8,0,1,2::Int]+      insertAt 1 8 [0,1,2] `shouldBe` [0,8,1,2::Int]+    specify "end" $ do+      insertAt 2 8 [1,2] `shouldBe` [1,2,8::Int]+    specify "empty" $ do+      insertAt 0 1 [] `shouldBe` [1::Int]+    specify "undefined" $ do+      take 3 (insertAt 0 8 (1:2:undefined)) `shouldBe` [8,1,2::Int]+    specify "infinite" $ do+      take 3 (insertAt 1 8 [1..]) `shouldBe` [1,8,2::Int]+    specify "negative" $ do+      insertAt (-1) 8 [1,2] `shouldBe` [1,2::Int]+    specify "excessive" $ do+      insertAt 3 8 [1,2] `shouldBe` [1,2::Int]++transformations :: Spec+transformations = describe "transformations" $ do+  describe "imap" $ do+    specify "basic" $ do+      imap (-) [1,3..9] `shouldBe` [0-1,1-3,2-5,3-7,4-9]+    specify "empty" $ do+      imap undefined ([] :: [Int]) `shouldBe` ([] :: [Bool])+    specify "x2" $ do+      imap (-) (imap (*) [1..4]) `shouldBe` [0-0*1,1-1*2,2-2*3,3-3*4]++monadicFunctions :: Spec+monadicFunctions = describe "monadic functions" $ do+  describe "imapM/traverse" $ do+    describe "Just" $ do+      specify "success" $ do+        imapM     (\i x -> Just (i-x)) [0..4] `shouldBe` Just [0,0,0,0,0]+        itraverse (\i x -> Just (i-x)) [0..4] `shouldBe` Just [0,0,0,0,0]+      specify "failure" $ do+        imapM     (\i x -> guard (i==x)) [0,1,2,4] `shouldBe` Nothing+        itraverse (\i x -> guard (i==x)) [0,1,2,4] `shouldBe` Nothing+    describe "State" $ do+      specify "basic" $ do+        let f i x = modify ((i,x):) >> return (i-x)+        let (resA, stA) = runState (imapM     f [1,3..9]) []+        let (resB, stB) = runState (itraverse f [1,3..9]) []+        resA `shouldBe` [0-1,1-3,2-5,3-7,4-9]+        resB `shouldBe` [0-1,1-3,2-5,3-7,4-9]+        stA `shouldBe` reverse (zip [0..4] [1,3..9])+        stB `shouldBe` reverse (zip [0..4] [1,3..9])++  describe "imapM_/traverse_" $ do+    describe "Just" $ do+      specify "success" $ do+        imapM_     (\i x -> Just (i-x)) [0..4] `shouldBe` Just ()+        itraverse_ (\i x -> Just (i-x)) [0..4] `shouldBe` Just ()+      specify "failure" $ do+        imapM_     (\i x -> guard (i==x)) [0,1,2,4] `shouldBe` Nothing+        itraverse_ (\i x -> guard (i==x)) [0,1,2,4] `shouldBe` Nothing+    describe "State" $ do+      specify "basic" $ do+        let f i x = modify ((i,x):) >> return (i-x)+        let stA = execState (imapM_     f [1,3..9]) []+        let stB = execState (itraverse_ f [1,3..9]) []+        stA `shouldBe` reverse (zip [0..4] [1,3..9])+        stB `shouldBe` reverse (zip [0..4] [1,3..9])++specialFolds :: Spec+specialFolds = describe "special folds" $ do+  describe "iall" $ do+    specify "full" $ do+      iall (\i x -> i*2==x) [0,2,4,6,8] `shouldBe` True+    specify "early" $ do+      iall (\i x -> i*2==x) [1,2,4,6,8] `shouldBe` False+    specify "empty" $ do+      iall undefined ([] :: [Int]) `shouldBe` True++  describe "iany" $ do+    specify "full" $ do+      iany (\i x -> i*2==x) [1,3,5,7,9] `shouldBe` False+    specify "early" $ do+      iany (\i x -> i*2==x) [0,3,5,7,9] `shouldBe` True+    specify "late" $ do+      iany (\i x -> i*2==x) [1,3,5,7,8] `shouldBe` True+    specify "empty" $ do+      iany undefined ([] :: [Int]) `shouldBe` False++folds :: Spec+folds = describe "folds" $ do+  describe "ifoldr" $ do+    specify "basic" $ do+      ifoldr (\i x a -> if i*2==x then i:a else a) [] [0,2,5,6] `shouldBe` [0,1,3]+    specify "empty" $ do+      ifoldr undefined True [] `shouldBe` True++  describe "ifoldl(')" $ do+    specify "basic" $ do+      ifoldl  (\a i x -> if i*2==x then i:a else a) [] [0,2,5,6] `shouldBe` [3,1,0]+      ifoldl' (\a i x -> if i*2==x then i:a else a) [] [0,2,5,6] `shouldBe` [3,1,0]+    specify "empty" $ do+      ifoldl  undefined True [] `shouldBe` True+      ifoldl' undefined True [] `shouldBe` True+    describe "strictness" $ do+      describe "acc" $ do+        let f a i x = if i==1 then undefined else x:a+        specify "lazy" $ do+          evaluate (take 2 (ifoldl  f [] [1..4::Int]))+            `shouldReturn` [4,3]+        specify "strict" $ do+          evaluate (take 2 (ifoldl' f [] [1..4::Int]))+            `shouldThrow` errorCall "Prelude.undefined"+      describe "elem" $ do+        let f a i _ = a+i+        specify "lazy" $ do+          evaluate (ifoldl  f 1 [undefined, undefined, undefined])+            `shouldReturn` 4+        specify "strict" $ do+          evaluate (ifoldl' f 1 [undefined, undefined, undefined])+            `shouldReturn` 4++sublists :: Spec+sublists = describe "sublists" $ do+  describe "ifilter" $ do+    specify "all" $ do+      ifilter (\i x -> i*2==x) [0,2,4,6] `shouldBe` [0,2,4,6]+    specify "none" $ do+      ifilter (\i x -> i*2/=x) [0,2,4,6] `shouldBe` []+    specify "empty" $ do+      ifilter undefined [] `shouldBe` ([] :: [Bool])++  describe "itakeWhile" $ do+    specify "all" $ do+      itakeWhile (\i x -> i*2==x) [0,2,4,6] `shouldBe` [0,2,4,6]+    specify "none" $ do+      itakeWhile (\i x -> i*2/=x) [0,2,4,6] `shouldBe` []+    specify "some" $ do+      itakeWhile (\i x -> i*2==x) [0,2,5,6] `shouldBe` [0,2]+    specify "empty" $ do+      itakeWhile undefined [] `shouldBe` ([] :: [Bool])++  describe "idropWhile" $ do+    specify "all" $ do+      idropWhile (\i x -> i*2==x) [0,2,4,6] `shouldBe` []+    specify "none" $ do+      idropWhile (\i x -> i*2/=x) [0,2,4,6] `shouldBe` [0,2,4,6]+    specify "some" $ do+      idropWhile (\i x -> i*2==x) [0,2,5,6] `shouldBe` [5,6]+    specify "empty" $ do+      idropWhile undefined [] `shouldBe` ([] :: [Bool])++search :: Spec+search = describe "search" $ do+  describe "ifind" $ do+    specify "found" $ do+      ifind (\i x -> i*2==x) [1,3,4,7] `shouldBe` Just 4+    specify "not found" $ do+      ifind (\i x -> i*2==x) [1,3,5,7] `shouldBe` Nothing+    specify "empty" $ do+      ifind undefined [] `shouldBe` (Nothing :: Maybe Bool)++  describe "ifindIndex" $ do+    specify "found" $ do+      ifindIndex (\i x -> i*2==x) [1,3,4,7] `shouldBe` Just 2+    specify "not found" $ do+      ifindIndex (\i x -> i*2==x) [1,3,5,7] `shouldBe` Nothing+    specify "empty" $ do+      ifindIndex undefined [] `shouldBe` Nothing++  describe "ifindIndices" $ do+    specify "all" $ do+      ifindIndices (\i x -> i*2==x) [0,2,4,6] `shouldBe` [0,1,2,3]+    specify "none" $ do+      ifindIndices (\i x -> i*2/=x) [0,2,4,6] `shouldBe` []+    specify "empty" $ do+      ifindIndices undefined [] `shouldBe` []++zipping :: Spec+zipping = describe "zipping" $ do+  describe "basic" $ do+    specify "2" $ do+      izipWith (\i a b -> [i,a,b]) [1,2] [3,4]   `shouldBe` [[0,1,3],[1,2,4]]+      izipWith (\i a b -> [i,a,b]) [1,2] [3,4,0] `shouldBe` [[0,1,3],[1,2,4]]+      izipWith (\i a b -> [i,a,b]) [1,2,0] [3,4] `shouldBe` [[0,1,3],[1,2,4]]+    specify "3" $ do+      izipWith3 (\i a b c -> [i,a,b,c]) [1,2] [3,4] [5,6]+        `shouldBe` [[0,1,3,5],[1,2,4,6]]+      izipWith3 (\i a b c -> [i,a,b,c]) [1,2] [3,4] [5,6,0]+        `shouldBe` [[0,1,3,5],[1,2,4,6]]+      izipWith3 (\i a b c -> [i,a,b,c]) [1,2] [3,4,0] [5,6]+        `shouldBe` [[0,1,3,5],[1,2,4,6]]+      izipWith3 (\i a b c -> [i,a,b,c]) [1,2,0] [3,4] [5,6]+        `shouldBe` [[0,1,3,5],[1,2,4,6]]+  describe "strictness" $ do+    -- The point of this test is that zipWith should stop when it sees an+    -- empty list, even if other lists are undefined+    let u :: Bool+        u = undefined+    let su :: [Bool]+        su = undefined+    let em :: [Bool]+        em = []+    specify "2" $ do+      izipWith undefined em su `shouldBe` em+    specify "3" $ do+      izipWith3 undefined em  su su `shouldBe` em+      izipWith3 undefined [u] em su `shouldBe` em+    specify "4" $ do+      izipWith4 undefined em  su  su su `shouldBe` em+      izipWith4 undefined [u] em  su su `shouldBe` em+      izipWith4 undefined [u] [u] em su `shouldBe` em++buildingLists :: Spec+buildingLists = describe "building lists" $ do+  describe "imapAccumR" $ do+    specify "basic" $ do+      imapAccumR (\a i x -> (2*a+i*x, x*2)) 0 [1,2,3]+        `shouldBe` (2*(2*(2*0+3*2)+2*1)+1*0,[2,4,6])+    specify "non-indexed" $ do+      imapAccumR (\a _ x -> (2*a+x, 2*x+a)) 0 [1,2,3::Int]+        `shouldBe`+       mapAccumR (\a   x -> (2*a+x, 2*x+a)) 0 [1,2,3]+    specify "empty" $ do+      imapAccumR undefined 0 [] `shouldBe` (0::Int,[]::[Bool])+  describe "imapAccumL" $ do+    specify "basic" $ do+      imapAccumL (\a i x -> (2*a+i*x, x*2)) 0 [1,2,3]+        `shouldBe` (2*(2*(2*0+1*0)+2*1)+3*2,[2,4,6])+    specify "non-indexed" $ do+      imapAccumL (\a _ x -> (2*a+x, 2*x+a)) 0 [1,2,3::Int]+        `shouldBe`+       mapAccumL (\a   x -> (2*a+x, 2*x+a)) 0 [1,2,3]+    specify "empty" $ do+      imapAccumL undefined 0 [] `shouldBe` (0::Int,[]::[Bool])