[Initial version of fusible list lib Duncan Coutts **20070302132947 Takes streams code from the ByteString lib, partially re-written. Takes list code from base with extensive rewrites for effeciency. QuickCheck tests and benchmarks to follow... ] [Fixes to list functions caught by QuickCheck Duncan Coutts **20070307172329 Lost a case in take & drop Wasn't dealing with ngative numbers in replicate and [] case for lines was wrong. ] [Add implementation of List and PreludeList taken from the Haskell 98 spec. Duncan Coutts **20070307172522 We'll use this as a spec and compare our optimised implementation(s) gainst it. At the moment it doesn't include some of the new things that have been added to Data.List, like foldl', foldr' and isInfixOf. ] [QuickCheck tests comparing H98Spec.List <=> Experimental.Data.List Duncan Coutts **20070307172807 For each function we compare the H98 spec version against our new implementation. Currently some tests don't get enough test cases and the sortBy property fails because the H98 spec and our version get different results for comparison functions that are not total orders. How do we generate random total orders? Perhaps we just use a fixed list [(==), (<), etc] ] [Only white space changes Duncan Coutts **20070308153303] [Export the stream conversion functions from Experimental.Data.List Duncan Coutts **20070308153342 We need them for the QC properties ] [Fix the type of Stream.foldl Duncan Coutts **20070308153434] [Make Streams an instance of Functor Duncan Coutts **20070308153537] [Fix implementation of and/or Duncan Coutts **20070308153552 Caught by QC ] [Fix implementation of replicate for negative n Duncan Coutts **20070308153612 Caught by QC ] [Rename NumA type to just N Duncan Coutts **20070308153743] [Add monomorphic specialisations of all the spec & list functions Duncan Coutts **20070308154133 We need to do this to be able to QC them. It's just boilerplate code and it makes the actual properties files much smaller and simpler. ] [Import the monomorphic versions and remove the type sigs Duncan Coutts **20070308154257 We no longer need to give explicit type sigs to constrain the types to be monomorphic since we're using monomorphic versions to start with. This change doesn't matter for lists so much, but it'll allow use to do the streams properties in the same style. ] [Add monomorphic specialisation and properties for streams functions Duncan Coutts **20070308154458 The monomorphic specialisaion also does the wrapping/unwrapping from lists to streams, so we can always do our QC tests at the list type. So far there are only properties for the few functions currently exported from the streams module. All these properties so far now pass (after a couple fixes). ] [Correct the list properties to deal with preconditions Duncan Coutts **20070308154726 Eg non-null lists, indexes withing range etc. All tests except for sortBy now pass. ] [Add trivial Makefile for the tests Duncan Coutts **20070308154941] [Make the list & stream properties modules more similar Duncan Coutts **20070314050217 Have them both import the modules they're testing as Test so ideally there should be essentually no difference between the mdoules except for what they import. Also merge across some changes to the properties that was done for the list properties module, like non-empty list pre-conditions etc. ] [Rewrite list version of intersperse Duncan Coutts **20070314051019 Now needs less lookahead ] [Add sum, product, minimum, maximum to stream properties Duncan Coutts **20070314052437] [Add Stream.intersperse Duncan Coutts **20070314052638 and add it and map to the properties ] [add setup script Don Stewart **20070314055947] [Set up imports so it can be compiled in context of base package Duncan Coutts **20070314060324 It's all a bit tricky :-( ] [use -DEXTERNAL_PACKAGE, to invert import tests. Then we don't need to hack ghc's build system Don Stewart **20070315030626] [tweak imports to build inside ghc Don Stewart **20070315040225] [typo Don Stewart **20070315051223] [add {-# OPTIONS_GHC -fno-implicit-prelude #-} to top of files Don Stewart **20070315053342] [reuse specifically GHC.Base.{map,foldr,(++)} Don Stewart **20070315054343] [-Wall police Duncan Coutts **20070315053855] [list concat & concatMap workers now a mututally recursive go/to pair Duncan Coutts **20070315053920 Allows the initial state to be more direct and makes it more similar to the stream version. ] [Move modules out from Experimental namespace Duncan Coutts **20070315060032 Now just Data.Stream and Data.List.Stream ] [update sync script Don Stewart **20070315061131] [Update module header meta-data Duncan Coutts **20070315060315] [Remove unused stream maximum & minimum Duncan Coutts **20070315061102 We have new versions now, I'm not even sure these versions were correct since the spec uses max/min rather than >= can we actually rely on properties of min max for all instances? ] [Add stream concat & concatMap Duncan Coutts **20070315061300] [comments only (copyright, paper refs) Don Stewart **20070315070418] [add todo Don Stewart **20070315071324] [add stub readme Don Stewart **20070315071714] [add initial benchmark helpers Don Stewart **20070315073615] [add benchmark suite Don Stewart **20070315074624] [more benchmarks Don Stewart **20070315074917] [Add ListExts to spec module collection Duncan Coutts **20070315074734 And rename to Spec rather than H98Spec since they're not all H98 any more ] [Add intercalate Duncan Coutts **20070315074918] [Add tests for the strict folds and isInfixOf Duncan Coutts **20070315075352] [Add stream properties for list extras: foldl', foldl1' Duncan Coutts **20070315232906 prop_isInfixOf is still commented out ] [Add stream versions of elem, lookup, find and filter Duncan Coutts **20070315233229 And add quick check properties ] [Rerange cases branches to be consistent Duncan Coutts **20070315233757] [Do the strictness of stream foldl' and foldl1' properly Duncan Coutts **20070315233825 Could also do it in a 'let x = .. in sex x ..' style to be more portable ] [Add commented-out stream intercalate Duncan Coutts **20070316013522 Just so we don't forget it. ] [data files Don Stewart **20070316041702] [add 'make bench' target Don Stewart **20070316042629] [and add DEXTERNAL_PACKAGE to Makefile for QC properties Don Stewart **20070316042755] [untab ListProperties Don Stewart **20070316042942] [untab StreamProperties.hs Don Stewart **20070316043105] [untab streammonomorphic Don Stewart **20070316043228] [untab ListMono* Don Stewart **20070316043539] [comments Don Stewart **20070316044117] [enable fusion rules for folds, comments. Don Stewart **20070316061627] [fusion rule for concatMap Don Stewart **20070316062410] [fusion for concat/ concatMap Don Stewart **20070316063538] [strict length. fusion for intersperse and or Don Stewart **20070316064747] [sum/prod fusion Don Stewart **20070316065257] [Make the forcible [a] instance more generic Duncan Coutts **20070316060317 Force the contents (assuming the contents are forcible) not just the spine ] [Make the bench not recompile so much Duncan Coutts **20070316060518] [Generate bigdata from data by cating 5 copies Duncan Coutts **20070316060652] [Make more forced imput values available Duncan Coutts **20070316060744 Use an input type to hold various forced strings: short, big, huge, long list of chunks. ] [Add test for intercalate Duncan Coutts **20070316060916 This uses a short string and a long list of meduim size strings ] [Add the fusion rule (!!) Duncan Coutts **20070316061114 We're not going to get very far without this! ] [Add rewrite rules for sum Duncan Coutts **20070316061214 These do not seem to work with ghc-6.6, it looks like the Num dict gets in the way. ] [Add 'optimised' version of intercalate Duncan Coutts **20070316065137 Turns out it's not obviously faster ] [update 'bench' makefile target Duncan Coutts **20070316065252] [Add FuseTest and makefile target Duncan Coutts **20070316065339] [Use "blah -> fusible" as the rule name rather than "blah -> fused" Duncan Coutts **20070316065445 since it's not actually fusing there, just turning into a form where it might. ] [maximum/minimum rule Don Stewart **20070316065725] [comments Don Stewart **20070316070133] [Use a GHC var in the Makefile so we can easily change the ghc version Duncan Coutts **20070316065948 make fusiontest GHC=ghc-6.7 ] [more rules Don Stewart **20070316073433] [comments Don Stewart **20070316073608] [Put -O2 into GHC_FLAGS not in all the rules Duncan Coutts **20070316074657 Makes it easier to test with -O rather than -O2 ] [rm -f not rm -r in make clean Duncan Coutts **20070316074728] [Don't inline stream or unstream too early Duncan Coutts **20070316074743] [Fix infinte loop in rules Duncan Coutts **20070316074809 Rule for concatMap had incorrect phasing ] [support for haddock Don Stewart **20070317043637] [-Wall police Don Stewart **20070317044049] [tweak tests Don Stewart **20070317045404] [more clean Don Stewart **20070317045437] [formatting only Don Stewart **20070317062208] [test List against Data.List and H98 Lists Don Stewart **20070317062243] [wrong arguments applied to 'f' in foldl1/foldl1', caught by QuickCheck Don Stewart **20070317071946] [import and rebind ++, map and foldr, so we can write docs. remove notElem Don Stewart **20070317072013] [tweaks Don Stewart **20070317072257] [comments Don Stewart **20070317072502] [also test Stream properties against Data.List and h98 Don Stewart **20070317072557] [commentary: an introduction to stream fusoin Don Stewart **20070317073710] [implement fusion and tests for scanl Don Stewart **20070317080605] [add QC ways for compiled code Don Stewart **20070317081315] [fuse intercalate by rewriting to concat . intersperse Don Stewart **20070318022033] [add properties for Stream.index Don Stewart **20070318032621] [add preliminary list of functions not yet fused. some easy pickings there Don Stewart **20070318032636] [add Stream implementation of index Don Stewart **20070318032656] [docs, and INLINE [1] on top level decls, to be safe Don Stewart **20070318032720] [add missing BSD license Don Stewart **20070318032923] [no regents involved Don Stewart **20070318032958] [whitespace, comments Don Stewart **20070318033354] [dump of ideas from pub chat Don Stewart **20070318083821] [comments, implement fusion for genericLength Don Stewart **20070318101515] [add fusion for genericTake/Drop/Index Don Stewart **20070318104505] [fusion for generic* Don Stewart **20070318110312] [findIndex, maximumBy, minimumBy Don Stewart **20070318115220] [update list of done functions Don Stewart **20070318115410] [strictness on some internal counters Don Stewart **20070318115954] [haddock doesn't like dangling 'where' clauses Don Stewart **20070318125714] [spotted bug in Skip/index handling. *not* spotted by QuickCheck yet, since it doesn't generate Skips except when fusion with filter (and friends) occurs Don Stewart **20070319000309] [add stub for internal properties Don Stewart **20070319004700] [tweaks Don Stewart **20070319004713] [fusion for zipWith Don Stewart **20070319010240] [Properties for zipWith fusion Don Stewart **20070319010249] [Add fusion for 'zip' Don Stewart **20070319010803] [Add fusion properties for zip Don Stewart **20070319010812] [Fusion for zipWith3 Don Stewart **20070319012025] [properties for zipWith3 Don Stewart **20070319012036] [fusion for zip3 Don Stewart **20070319013023] [properties for zip3 Don Stewart **20070319013029] [start recording QC properties for each function in the documentation Don Stewart **20070319014352] [and add these documented QCs to the InternalProperties.hs test Don Stewart **20070319014404] [more properties Don Stewart **20070319015124] [fusion for elemIndices Don Stewart **20070319021015] [properties for elemIndices Don Stewart **20070319021031] [one less thing todo Don Stewart **20070319021042] [add fusion for findIndices Don Stewart **20070319021856] [add properties for findIndices Don Stewart **20070319021909] [property for findIndex Don Stewart **20070319022636] [more properties Don Stewart **20070319023224] [add Arbitrary Stream a Don Stewart **20070319030457] [fusion for unlines (!) (via concatMap (snoc x '\n') Don Stewart **20070319034809] [properties for unlines Don Stewart **20070319034827] [fusion for (:) Don Stewart **20070319035652] [typo in (:) rule Don Stewart **20070319040821] [use Stream.snoc for scanl Don Stewart **20070319041614] [give up on scanr for now Don Stewart **20070319043752] [help haddock Don Stewart **20070319044004] [Rename StreamMonomorphic -> StreamListMonomorphic Duncan Coutts **20070319044040] [This version exposes an api in terms of Stream a, not [a] Duncan Coutts **20070319044215 So we will be able to test at the Stream type and check things like streams with skips in them which we can't do when we test at type [a]. ] [Only test against SpecMonomorphic (Spec.List) in StreamProperties Duncan Coutts **20070319044522 StreamProperties2 will be against SpecBaseMonomorphic (Data.List) StreamProperties3 will be against SpecStreamMonomorphic (Spec.List with a Stream wrapper) ] [Add other versions of StreamProperties Duncan Coutts **20070319050348 The SpecStreamMonomorphic is a Stream wrapper around the H98 spec implemementations of the list functions, it's so that in StreamProperties3 we can do comparative tests at the Stream type. ] [Merge with Don's latest changes to scanr Duncan Coutts **20070319050601] [Fix compilation of ListProperties.hs Duncan Coutts **20070319050641 opts got moved into QuickCheckUtils ] [Add Show and Eq instances for Stream to QuickCheckUtils Duncan Coutts **20070319050732] [Split ListProperties into two, one for Spec.List and one for Data.List Duncan Coutts **20070319051704] [move opts out Don Stewart **20070319053733] [Add cons to SpecStreamMonomorphic Duncan Coutts **20070319053622] [Update StreamMonomorphic with latest stream additions Duncan Coutts **20070319053713] [Sync the three StreamProperties modules with each other Duncan Coutts **20070319053856 Only StreamProperties3 is significantly different since there are not stream versions of everything yet. ] [run all the properties Don Stewart **20070319061620] [Be consistent about the order of Step constructors in cases Duncan Coutts **20070319060810] [Add prop_nubsortby to InternalProperties Duncan Coutts **20070319062153 Fails for the same reason as prop_sortBy, same fix will work for both, oe only testing it with total orders rather than arbitrary comparitors. ] [Run all the compiled tests in a batch, and fix GHC_FLAGS Duncan Coutts **20070319062512] [Add alternative Stream.zip implementation Duncan Coutts **20070319062853] [Modify zip to only yield once, and use Maybe not Either Duncan Coutts **20070319063936] [Fix up zip/zipWith zip3/zipWith3 Duncan Coutts **20070319070012] [non-space leakey snoc. and fix scanl test Don Stewart **20070319072134] [Add Stream.unzip :: Stream (a, b) -> ([a], [b]) Duncan Coutts **20070319071238 Yeilding lists is the best we can do, you can stream those lists again if it'd ever help (which it probably wouldn't). ] [Add tests for snoc Duncan Coutts **20070319072515] [Unbreak prop_snoc Duncan Coutts **20070319072923] [Simple implementations of and,or in terms of foldr gives same code Duncan Coutts **20070319073642 ghc's simplifier isn't broken :-) ] [wibbles Don Stewart **20070319090925] [fix some tests. steal some build flags from ndp Don Stewart **20070319092414] [update readme Don Stewart **20070319234404] [disable explicit SPECIALISE. we can use our own fusible rules instead Don Stewart **20070319234924] [fusion for insertBy Don Stewart **20070320001651] [properties for insertBy Don Stewart **20070320001703] [and thus 'insert' can fuse too Don Stewart **20070320001812] [comments Don Stewart **20070320042454] [log of points raised in today's meeting Don Stewart **20070320042500] [Fix types of stream wrappers for (un)lines and (un)words Duncan Coutts **20070320071342] [Add fusion for 'lines' Don Stewart **20070320072327] [wibble Duncan Coutts **20070320081341] [Remove unused types Duncan Coutts **20070320081351] [Add QuickCheck tests for strictness properties of list functions Duncan Coutts **20070320081431 So far it just compares Spec.List === Data.List.Stream That is it compares for full equality, so there are several tests that fail, most likely due to the fact that we actually refine the spec. We're currently only testing for partial lists, not lists with bottoms in the elements. That should be easy to add however. We'll also want to compare Spec.List === Data.List to see if the current Data.List does any refinement. Comparing Data.List === Data.List.Stream might be interesting too. The other important one though is Data.List.stream === Data.Stream either at type [a] or at type Stream a, to make sure our stream versions have the same strictness as our list versions. We don't really want to be changing strictness behaviour when fusing, not even refinement. If our Stream versions refine our List versions, we should update the List versions to be that lazy. ] [add strictness properties to makefile Don Stewart **20070320105154] [more internal properties, from h98 report Don Stewart **20070320113811] [fusion for isPrefixOf Don Stewart **20070320232500] [properties for isPrefixOf Don Stewart **20070320232527] [docs Don Stewart **20070320232539] [move some things around Don Stewart **20070320233307] [fusion for scanl1 Don Stewart **20070321013957] [Properties for scanl1 Don Stewart **20070321014009] [less things to do Don Stewart **20070321014127] [depend on the 'strict' package, http://hackage.haskell.org/cgi-bin/hackage-scripts/package/strict-0.1 Don Stewart **20070321030021] [Fix our genericTake to match the spec Duncan Coutts **20070321010220] [Fix up bottoms utility code Duncan Coutts **20070321025815] [uncomment zipWith strictness properties Duncan Coutts **20070321030228] [Fix genericIndex strictness property Duncan Coutts **20070321030336 Can't test for n being less than the length of the list since it's a partial list! however indexing off the end of the list is just _|_, so that's just fine. :-) ] [We refine H98 List spec for unwords, intersperse and intercalate Duncan Coutts **20070321030453] [Revert our fast lines and words impls because they're too strict Duncan Coutts **20070321030559 caught by the strictness QuickCheck properties ] [Add more notes to the TODO, strictness issues and sharing Duncan Coutts **20070321030917] [Add back missing type sig for lines Duncan Coutts **20070321031809] [Rename SpecBaseMonomorphic to BaseMonomorphic Duncan Coutts **20070321050724 So the prefixes are just: Spec -- Haskell 98 List spec Base -- base.Data.List impl List -- our Data.List.Stream impl ] [option pragmas in src, for base Don Stewart **20070321061739] [Rename SpecBaseMonomorphic to BaseMonomorphic Duncan Coutts *-20070321050724 So the prefixes are just: Spec -- Haskell 98 List spec Base -- base.Data.List impl List -- our Data.List.Stream impl ] [Rename SpecBaseMonomorphic to BaseMonomorphic (properly this time) Duncan Coutts **20070321053245] [Rename module import so both modules are essentially the same Duncan Coutts **20070321053401] [tweaks for building in base Don Stewart **20070321062750] [disable cons fusion rule. kicks ghc's butt too badly Don Stewart **20070321064003] [tag the fusion rule so its easier to spot Don Stewart **20070321064220] [don't reimplement map/foldr/++. breaks ghc builds too badly Don Stewart **20070321064635] [Remove bogus comment Duncan Coutts **20070321070536] [Add EqPartial (,,) instance and export A,B constructors Duncan Coutts **20070321070553 Having the constructors exported makes reproducing failing tests easier ] [ListPartialProperties2 to compare H98 spec with base.Data.List Duncan Coutts **20070321071156 note two failing cases, base.Data.List is stricter than the spec for at least partition and is inconsistent with the spec on genericTake. Currently we're only adding _|_'s to lists, not list elements or atomic types, so we're not currently catching the strictness bug in splitAt for example. ] [Add StreamPartialProperties to compare our list and stream impls Duncan Coutts **20070321071337 These must match exactly, no refinement allowed. Currently a couple failures, scanl & scanl1 are too strict and lines follows the old too-strict list implementation that we had to revert. ] [Note more strictness issues with the H98 spec Duncan Coutts **20070321071634] [Fix genericTake to do the right thing rather than followng the spec Duncan Coutts **20070321071703 So we now follow Data.List rather than the H98 spec. ] [Fix import Duncan Coutts **20070321071938] [Change implementations of take, drop and splitAt Duncan Coutts **20070321072449 They were needlessly complex, also splitAt now is strict in 'n' as is Data.List though the H98 spec is wrong and specifies that it should be lazy in n. ] [no Integer import. fingers crossed this helps .hi-boots Don Stewart **20070321075229] [simplify imports further Don Stewart **20070321075643] [Allow partial atomic values and hence lists with partial elements Duncan Coutts **20070321075313 All you need to do is change the type, for example you could change: splitAt :: Int -> Partial [A] -> ([A], [A]) splitAt :: Partial Int -> Partial [A] -> ([A], [A]) ] [Generalise the type of the 'u' unwrap function Duncan Coutts **20070321075418 so we can use it on atomic partial values ] [back port some module import tweaks from base Don Stewart **20070322015830] [Remove stream/unstream from the List module Duncan Coutts **20070322064116 Moving it into the Stream module ] [Use strict states in Streams Duncan Coutts **20070322064229 Loads of code changes. Add an unlifted type class and make our various strict constructors instances of it. Use these strict pairs/Either/Maybe etc in the Stream states for all the stream algorithms. Use the 'expose' function in all stream consumers to expsose the stream state structure to the simplifier. Make user state use L or S boxes. Also add stream/unstream to the Stream module. ] [Fix up import breakage due to changing which module stream/unstream are in Duncan Coutts **20070322064931] [Add ListPartialProperties2 and StreamPartialProperties to Makefile Duncan Coutts **20070322065440] [don't need to use -O2 since it's already in GHC_FLAGS Duncan Coutts **20070322065520 and extend make clean ] [Remove lengths in Stream constructor Duncan Coutts **20070322070608] [Fix one more case to remove length from stream Duncan Coutts **20070322071028] [tweaks Don Stewart **20070322131101] [don't need fromIntegral Don Stewart **20070323003211] [use optimised (when unfused) take/drop/splitAt from ghc Don Stewart **20070323012038] [and hand-specialise sumInt Don Stewart **20070323013834] [merge dons@cse.unsw.edu.au**20070323014318] [Export take' Duncan Coutts **20070323015318] [no need to unbox take/drop/splitAt, once we float out the <= tests Don Stewart **20070323015812] [make reverse a fusible consumer (in terms of foldl) Don Stewart **20070323022554] [notes on slow downs Don Stewart **20070323055345] [Put expose in the right place in the stream consumers Duncan Coutts **20070323055110] [our 'length' was 3x slower.. Don Stewart **20070323060916] [some strict internal indices for find/elem* functions Don Stewart **20070323063204] [fold' for reverse Don Stewart **20070323072400] [more benchmarks Don Stewart **20070323073623] [provide strict fusible maximum,minimum, as GHC does Don Stewart **20070323075720] [haddock Don Stewart **20070323082948] [Fix cycle to give an error when the list is empty Duncan Coutts **20070323071932 Previously it did not terminate :-) ] [Rearrange tests and add new strictness tests Duncan Coutts **20070324024738 The strictness tests bundle a modified version of SmallCheck but require the ChasingBottoms lib: http://www.cs.chalmers.se/~nad/software/ http://www.cs.chalmers.se/~nad/software/ChasingBottoms/ChasingBottoms.tar.gz ] [Move Bench/BenchUtils.hd -> Bench/Utils.hs Duncan Coutts **20070324032045] [Fix up 'compiled' target in Makefile Duncan Coutts **20070324032122] [tag loop() with the name of the wrapper function. Don Stewart **20070324065348] [add compiled properties to Makefile Don Stewart **20070324065400] [Add Test.SmallCheck.Partial Duncan Coutts **20070324065843] [Strictify !s in many stream consumers and transformers Duncan Coutts **20070324075444 We only need to do this for stream states where we don't already pattern match eg (_ :!: _) since that's already fully strict. ] [inline 'next' functions as ndp does Don Stewart **20070324092234] [some inlines Don Stewart **20070324093440] [ditch haddock help in Stream.hs Don Stewart **20070324094122] [wibbles Don Stewart **20070324095145] [fusion for zip4, needed by calendar Don Stewart **20070324101517] [tweaks Don Stewart **20070324110839] [slightly nicer `elem` Don Stewart **20070324111757] [tweak to concatMap Don Stewart **20070324112308] [undo Don Stewart **20070324112924] [details on building with ghc Don Stewart **20070325004147] [enumFromTo for Int and Char (for now) Don Stewart **20070325022054] [Make the instance Serial Char more useful Duncan Coutts **20070325041724 include space, newline and '\0' ] [Make evil Num instances for N, I that are neither assocuiative or commutative Duncan Coutts **20070325041938 This is to catch cases where we rely on these properties, which we cannot assume to hold in general for all Num instances ] [prop_genericReplicate needs to use eqfinite2 Duncan Coutts **20070325042131] [Include stream strictness properties for zip3, zip4, zipWith4 Duncan Coutts **20070325042230 Since we now have stream versions of these functions. ] [Use '\0' in the instance Arbitrary Char Duncan Coutts **20070325042401] [Add comment about genericIndex Duncan Coutts **20070325042547] [Fix ordinary list sum and product Duncan Coutts **20070325042654 They were assuming that + and * were commutative. just fix (x + a) to (a + x). ] [Stream isPrefixOf was too strict Duncan Coutts **20070325042822 It was forcing elements by putting them in strict boxes: Yield x s' -> loop s' (S.Just x) should be: Yield x s' -> loop s' (S.Just (L x)) Making S.Just require an Unboxed a => context would catch these bugs. ] [Fix stream genericLength to be a foldr rather than a foldl Duncan Coutts **20070325043034 The report defines it as a foldr. Bug caught by using a non-associative (+) opertaor :-) ] [Fix corner cases in stream versions of generic take, drop and index. Duncan Coutts **20070325043239 Wasn't returning error for negative indexes. Also was assuming too much about what (\n -> n-1) does: we do have to check n > 0 each time round the loop :-(. We can only do better for sane instances. ] [Give same error messages as base versions Duncan Coutts **20070325043533 ie make stream functions pretend that they're list functions for the purposes of error messages. ] [Fix stream splitAt to be stricter and make it return a pair of list Duncan Coutts **20070325043708 rather than a pair of streams same for genericSplitAt. ] [Define strict stream state construtors locally and use Unlifted context Duncan Coutts **20070325044234 By using an unlifted type constraint on the data constructors: data Unlifted a => Maybe a = Nothing | Just !a we can eliminate a class of errors where we accidentally put user state into a strict data constructor. This also means we don't depend on the strict package (we were only using the three data delcs from that package not any instances or helper functions). ] [Rename the properties modules again to make things clearer Duncan Coutts **20070325053130 They're now named FoovsBar to indicate what is being compared to what Also checked that all the comments describing this are correct and have it print the same title when the tests are run. Also add ListVsBase strictness comparison since we often agree with base but we both disagree with the spec. ] [Misc tidyups to a couple properties modules Duncan Coutts **20070325053425] [todos Don Stewart **20070326005043] [prelim Integer fusion support Don Stewart **20070326024243] [update tests Don Stewart **20070326063730] [wibbles Don Stewart **20070326063903] [Add stream implementations of foldM and foldM_ Duncan Coutts **20070326050828 All the other monadic functions that consume lists can be defined in terms of foldr. ] [Use a simpler approach to concatMap, only fuse outer stream Duncan Coutts **20070326070744] [wibble Don Stewart **20070326071649] [some things done. Don Stewart **20070326095421] [Add benchmark of stream vs list Duncan Coutts **20070327021657] [Fix up Makefile, remember to use make bench GHC=ghc-6.7.xxxx Duncan Coutts **20070327021742] [Use product of sums rather than sum of products for stream states Duncan Coutts **20070327021905 This optimises much better ] [Add commented-out contat and conataMap alternatives Duncan Coutts **20070327022136 Sadly they're slower :-( ] [Add dummy method to Unlifted to make the simplifier happier Roman Leshchinskiy **20070327033309] [Do the Unlifted instances for L and S manually Duncan Coutts **20070327052209 Just for paranoia ] [Don't inline in concat and concatMap Duncan Coutts **20070327052242] [Add spec rules for strict stream max and min Duncan Coutts **20070327054205] [Expand elem slightly, seems to be faster Duncan Coutts **20070327054240] [Always put expose on the outside Duncan Coutts **20070327054259] [Whitespace Duncan Coutts **20070327054429] [Factor out the n <= 0 test in list replicate Duncan Coutts **20070327054529 Sadly this is faster. I did file a bug about it though: http://hackage.haskell.org/trac/ghc/ticket/1246 ] [make the "replicate -> fusible" more likely to fire Duncan Coutts **20070327054710 Don't require that it be fully applied. ] [Expand elem slightly, seems to be a tad faster. Duncan Coutts **20070327054742] [-fmax-simpl not needed here. Don Stewart **20070327060701] [Don't use a fusible concatMap for testing Stream vs List Duncan Coutts **20070327055324] [Must inline maximum & minimum to get the type specialisation in the benchmark Duncan Coutts **20070327055358] [Make drop a tad faster by factoring out the <= 0 test Duncan Coutts **20070327065311] [Refactor the zipWith3 and zipWith4 stream state types Duncan Coutts **20070327071457] [Make Stream.index work the same way as List.index Duncan Coutts **20070327080938 ie counting from n down to 0 rather than 0 up to n. ] [Fix up insertBy, mainly missing an {-# INLINE next #-} Duncan Coutts **20070327081028] [missing inline pragams for 'next' steppers Don Stewart **20070327081324] [Add append' that shares it's 2nd arg Duncan Coutts **20070327113342 and rules for using it when normal append isn't going to fuse on its second arg. ] [-Wall police Don Stewart **20070327233638] [add enum example from x2n1 benchmark Don Stewart **20070327233651] [Change fusion for ++ Roman Leshchinskiy **20070328005454] [Use simple definition of concatMap and turn off other rules for it Duncan Coutts **20070328015011 concatMap f = foldr (\x y -> f x ++ y) [] ] [Use our own definitions of (++) map and foldr when not in base Duncan Coutts **20070328015115 Otherwise we share the definitions and we get build/foldr firing. When we build in base we want to turn off the build/forldr rules. ] [We can't be strict in the assumulator of sum and product in general Duncan Coutts **20070328033246 Only for some strict types like Int, but we already have specialisations for Int. Could add further specialisations. ] [Define strict foldl's in a more direct fashion Duncan Coutts **20070328033404 Should be precisely the same from a strictness point of view. ] [Add another version of stream intersperse Duncan Coutts **20070328033809 still not much faster but this version might be interesting if we come back to look at it again. ] [Eta-expand (!!) in benchmark, doesn't optimise at all otherwise Duncan Coutts **20070328033948] [Correct names of a couple rules Duncan Coutts **20070328061826] [Optimise list versions of intersperse and intercalate and turn off streaming Duncan Coutts **20070328065546 The stream versions were slower so just turn them off. ] [Use NOINLINE [1] rather than INLINE [1] on most list functions Duncan Coutts **20070328065902 This has much the same effect with respect to staging but lets ghc decide in the end if it should get inlined. We noticed good effects with things like drop, where when we don't force inlining ghc can float the worker loop out (and generate good code for that) and just inline the little non-recursive wrapper bit that does the unboxing and initial n < 0 check. Current base versions of list functions mostly do not have INLINE pragmas at all. We still always inline the fold functions. ] [Add a note about {-# INLINE [1] zipWith #-} Duncan Coutts **20070328070058] [Optimise elemIndex and elemIndices Duncan Coutts **20070328090144 Turns out both are better by defining in terms of the versions that take general predicates since that gets the dictionary nearest the surface so when you inline you generate a special case predicate. ] [Tweak benchmark output to make it clearer Duncan Coutts **20070328090326] [Enable testing of minimum/maximum in stream vs list test Duncan Coutts **20070328234636 since neither cause a stack overflow ] [Need to inline wraped versions of elemIndex elemIndices to get it to optimise Duncan Coutts **20070328234733 since it needs to generate specialsied (x==) functions in the calling context. ] [inline elemIndex and elemIndices and turn off their rules Duncan Coutts **20070328234849 We get stream versions of these two just by inlining to get their definitions in terms of findIndex and findIndices which have rules to get stream versions ] [disable dodgy concatMap rule Duncan Coutts **20070330054642] [Make concatMap use pairs rather than Either in the stream state Duncan Coutts **20070330054657 This version of concatMap is still disabled. ] [Don't export Stream.lines, we don't use it and it's broken (too strict) Duncan Coutts **20070330071657] [Never ever ever ever construct _|_ streams Duncan Coutts **20070330072603 Don't force args when constructing streams, delay it until the stepper function gets called. ] [Add FIXME note to scanl Duncan Coutts **20070330072922 They're just broken and need fixing. ] [Comment out tests of stream lines / unlines Duncan Coutts **20070330073019] [Fix types of things in strictness check modules that use concat / concatMap Duncan Coutts **20070330073045] [Add desugarer program Duncan Coutts **20070330131610 Use like so: runghc Desugar.hs < Examples.hs > ExamplesDesugared.hs It's not quite in the form of a pre-processor however, but it is handy for comparing original and desugared versions since it prints them both out next to each other. The 'let decls' bit isn't quite finished. ] [Add stream functions used for list comprehensions Duncan Coutts **20070402000714] [Fix name clashes when compiled in base Duncan Coutts **20070402000749] [Fix stream concatMap Duncan Coutts **20070402000820 though this version is still commented out ] [Fix needed to make it build in base Duncan Coutts **20070402035655] [Modify guard for better optimisation Roman Leshchinskiy **20070404060623] [Real concatMap for streams Roman Leshchinskiy **20070404061208] [Fix bug in Stream.bind Roman Leshchinskiy **20070404103838] [Fuse (++) with [] and (:) Roman Leshchinskiy **20070404170305] [comment out missing lines code Don Stewart **20070418211910] [fix one property. concat still needs fixing. Don Stewart **20070418212905] [add ref to new pper Don Stewart **20070715032140] [tweaks for 6.8 Don Stewart **20071031184202] [add Control.Monad.Stream --fusible monad functions Don Stewart **20071031184436] [add Control.Monad.Stream Don Stewart **20071031184839] [some examples Don Stewart **20071117224939] [Make tests run Samuel Bronson **20070419174539] [remodel .cabal file for hackage. -Wall police Don Stewart **20071118004152] [update to newer QuickCheck Don Stewart **20071118010418] [update readme Don Stewart **20071118010643] [example Don Stewart **20071118010925] [tweaks Don Stewart **20071118011026] [TAG stream-fusion-0.1 Don Stewart **20071118011323] [tweak Don Stewart **20071118011453] [another typo Don Stewart **20071118011621] [tweaks Don Stewart **20081011065704] [Disable rewriting unfused versions back. Don Stewart **20081107183005 Ignore-this: c9266b71f801ea1e96bbc9ff92f8056a ] [bump Don Stewart **20081107183348 Ignore-this: f20a44e54168a88152ea2be339ff1f0 ] [let ./Data/List/Stream.hs run through haddock Don Stewart **20071118015657] [some docs for Data.Stream Don Stewart **20071118015750] [update docs a bit Don Stewart **20071118020035] [doc changes only, tag Don Stewart **20071118020143] [typo Don Stewart **20071118215638] [ensure benchmarks build again Don Stewart **20071118215647] [tweak Don Stewart **20071118215659] [rule for strict minimum fusion was wrong Don Stewart **20080120084050] [actually get the rules right for strictMinimum/Maximum Don Stewart **20080120084612] [Merge Don Stewart **20081108180137 Ignore-this: 64c77012dba10f1a72f87f66b228c787 ] [bump Don Stewart **20081108180501 Ignore-this: 7d8e789de85825839cc018c3ff67521b ] [Fix documentation for Haddock 2 Reiner Pope **20090719093231 Ignore-this: ebf768f01c6368f08364687694304f64 ] [bump Don Stewart **20090719215209 Ignore-this: 1f0ac16b9169e3afec7abb294c367e78 ] [Polish Don Stewart **20110522185550 Ignore-this: 4b603c89eea54c998ccae65c88888348 ] [base Don Stewart **20110522185648 Ignore-this: 73b0aa3d65f62e40cef1fa85d4312620 ] [Maintain .cabal file. Don Stewart **20130112143355 Ignore-this: 18175da0de06ac4bf23586df89ae7d95 ] [Remove bogus -XDatatypesContextt Don Stewart **20130112172641 Ignore-this: ddfcc3c3df57dfc4afdfd05c92739e13 ] [Add missing language pragmas to help GHCi use Don Stewart **20130112173209 Ignore-this: 8ee50988296055c921b4881846ff6560 ] [Keep testsuite running Don Stewart **20130112173225 Ignore-this: e1c6c9620f232fe903f0633b76335e62 ] [Add some missing language pragmas caught by ghci Don Stewart **20130112181629 Ignore-this: dbcaff06e898d72f489c615e5ee9048a ] [Get testsuite running again Don Stewart **20130112181640 Ignore-this: d37be04dc0b1e75390e332fe2cf0af4c ] ['time' is builtin Don Stewart **20130112182159 Ignore-this: 2d55a54a484e03f0aa4471fd2053c44c ] [Bump min cabal versionn Don Stewart **20130112182354 Ignore-this: 5469393af6ba87e0ffb178a80700bb8f ] [Bump version Don Stewart **20130112182603 Ignore-this: a2ebb4140211e40eab0aaaafb52ff682 ]