RE: [Haskell-cafe] Stream fusion for Hackage
| Will it eventually replace Data.List in GHC? | | That is the plan, yep. But first we need to solve the concatMap problem, no? So far as I know, fold/build has the property that if fusion doesn't happen, no harm is done. But streams risk making the program *worse* if Good Things do not happen to happen. This makes me anxious. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Don Stewart | Sent: 18 November 2007 20:09 | To: Tom Schrijvers | Cc: haskell-cafe@haskell.org | Subject: Re: [Haskell-cafe] Stream fusion for Hackage | | Tom.Schrijvers: | On Sat, 17 Nov 2007, Don Stewart wrote: | | Just a quick announce: the stream fusion library for lists, | that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year | is now available on Hackage as a standalone package: | | http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1 | | As described in the recent paper: | | Stream Fusion: From Lists to Streams to Nothing at All | Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007 | | This is a drop-in replacement for Data.List. | | Will it eventually replace Data.List in GHC? | | That is the plan, yep. | ___ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream fusion for Hackage
On Sat, Nov 17, 2007 at 06:31:08PM -0800, Don Stewart wrote: Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package: Just to note: I'm excited about one day using this with darcs. Right now we're using (in the unstable branch) our own list type so we can use type witnesses. I look forward to making this as efficient as the built-in lists (or more efficient?) one of these days... (and I've no suggestions on the namespace question). -- David Roundy Department of Physics Oregon State University ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream fusion for Hackage
simonpj: | Will it eventually replace Data.List in GHC? | | That is the plan, yep. But first we need to solve the concatMap problem, no? So far as I know, fold/build has the property that if fusion doesn't happen, no harm is done. But streams risk making the program *worse* if Good Things do not happen to happen. This makes me anxious. Simon Yep, me too. We'll be using it in ByteString and other strict arrays first, where the issues are much simpler, then looking at what can be done with lists. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream fusion for Hackage
On Sat, 17 Nov 2007, Don Stewart wrote: Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1 As described in the recent paper: Stream Fusion: From Lists to Streams to Nothing at All Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007 This is a drop-in replacement for Data.List. Will it eventually replace Data.List in GHC? Tom -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: [EMAIL PROTECTED] url: http://www.cs.kuleuven.be/~toms/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream fusion for Hackage
Don Stewart wrote: Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1 As described in the recent paper: Stream Fusion: From Lists to Streams to Nothing at All Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007 This is a drop-in replacement for Data.List. So let me get this straight... If I take a program that does lots of list processing, and import this module instead of Data.List, the program will magically go faster? Sounds good to me! :-D I wonder if this will make my Burrows-Weeler Transform program go any faster? That's 100% list processing... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stream fusion for Hackage
Tom.Schrijvers: On Sat, 17 Nov 2007, Don Stewart wrote: Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1 As described in the recent paper: Stream Fusion: From Lists to Streams to Nothing at All Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007 This is a drop-in replacement for Data.List. Will it eventually replace Data.List in GHC? That is the plan, yep. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Stream fusion for Hackage
Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1.1 As described in the recent paper: Stream Fusion: From Lists to Streams to Nothing at All Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007 This is a drop-in replacement for Data.List. Haddocks here, http://code.haskell.org/~dons/doc/stream-fusion/ (but note the interface is exactly the same as the Data.List library) You might expect some small percent performance improvement for list heavy programs, using ghc 6.8 and this list library with -O2 (use -ddump-simpl-stats and look for: STREAM stream/unstream fusion messages, indicating your intermediate lists are getting removed. To get an idea of what is happening, consider this list program: foo :: Int - Int foo n = sum (replicate n 1) Compiled with ghc-6.8.1 -O2 -ddump-simpl Normally, as sum is a left fold, an intermediate lazy list is allocated between the call to sum and replicate, as GHC currently does: foo :: Int# - Int# foo n = Data.List.sum (case =# n 0 of False - go n True - []) where go :: Int# - [Int] -- intermediate list! go n = case =# n 1 of False - 1 : (go (n -# 1)) True - [1] By using Data.List.Stream instead, you get a strict fused loop instead, with no intermediate structure allocated: loop_sum :: Int# - Int# - Int# loop_sum k n = case =# n 0 of False - loop_sum (k +# 1) (n -# 1) True - k foo :: Int# - Int# foo n = loop_sum 0 n This is a the halfway mark before porting other sequence types -- especially Data.ByteString -- over to the full stream fusion model (in particular, strict bytestrings will benefit a lot, due to the O(n) cost of intermediate bytestrings being removed). The stream fusion types and combinators are also available in stripped down form in the mlton sml compiler's extended prelude. Enjoy. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
