Ticket #915 (new task)

Opened 3 years ago

Last modified 9 months ago

Implement list fusion using streams instead of foldr/build

Reported by: simonpj Assigned to:
Priority: normal Milestone: 6.12 branch
Component: libraries/base Version: 6.8
Severity: normal Keywords: fusion
Cc: dons@galois.com, duncan.coutts@worc.ox.ac.uk, rl@cse.unsw.edu.au, Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com, johan.tibell@gmail.com, Deewiant Difficulty: Project (> 1 week)
Test Case: N/A Operating System: Unknown/Multiple
Architecture: Unknown/Multiple

Description

We'd like to try using the stream-fusion idea of Don Stewart, Duncan Coutts and Roman Leshchinskiy, and replace the (somewhat fragile) foldr/build stuff.

See #876.

Change History

09/28/06 03:33:46 changed by simonpj

  • owner set to simonpj.

10/21/06 10:16:31 changed by igloo

  • testcase set to N/A.

03/16/07 20:41:55 changed by dons

  • keywords set to fusion.
  • difficulty changed from Unknown to Project (> 1 week).
  • version changed from 6.4.2 to 6.6.
  • architecture changed from Unknown to Multiple.

This task has its own website now:

http://www.cse.unsw.edu.au/~dons/streams.html.

07/03/07 04:39:02 changed by guest

  • cc set to Bulat.Ziganshin@gmail.com.

it will be great to see this included in ghc base if this work is already completed

07/03/07 05:38:31 changed by duncan

It's not done yet. There's a paper on it but we still have issues with complex list comprehensions.

The new streams stuff will be included in the new bytestring-1.0 package though (as you know, the base package is being split up and ByteString? will be in its own package).

08/29/07 08:38:53 changed by guest

  • cc changed from Bulat.Ziganshin@gmail.com to Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com.

11/12/07 06:43:20 changed by simonmar

  • milestone changed from 6.8 branch to 6.10 branch.

11/12/07 06:43:52 changed by simonmar

  • owner deleted.

11/12/07 09:05:45 changed by dons

  • cc changed from Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com to dons@galois.com, duncan.coutts@worc.ox.ac.uk, rl@cse.unsw.edu.au, Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com.
  • version changed from 6.6 to 6.8.

We should also rerun the benchmarks in the light of the changes that made it into head since April when the fusion library was last benchmarked. There's no that much more to do here, to finish the job.

01/20/08 03:22:11 changed by tibbe

  • cc changed from dons@galois.com, duncan.coutts@worc.ox.ac.uk, rl@cse.unsw.edu.au, Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com to dons@galois.com, duncan.coutts@worc.ox.ac.uk, rl@cse.unsw.edu.au, Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com, johan.tibell@gmail.com.

07/14/08 07:44:41 changed by igloo

  • milestone changed from 6.10 branch to 6.12 branch.

09/27/08 09:18:15 changed by Deewiant

  • cc changed from dons@galois.com, duncan.coutts@worc.ox.ac.uk, rl@cse.unsw.edu.au, Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com, johan.tibell@gmail.com to dons@galois.com, duncan.coutts@worc.ox.ac.uk, rl@cse.unsw.edu.au, Bulat.Ziganshin@gmail.com, kfrdbs@gmail.com, johan.tibell@gmail.com, Deewiant.

09/27/08 09:20:16 changed by dons

This library has been written and released,

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion

To replace GHC's existing list fusion, we'll need to work out how concatMap is optimised, and push the desugaring for list comprehensions into GHC.

For now though, users can just use the library, and avoid list comprehensions and [n .. m] (use enumFromTo).

09/30/08 08:45:06 changed by simonmar

  • architecture changed from Multiple to Unknown/Multiple.

09/30/08 08:51:08 changed by simonmar

  • os changed from Unknown to Unknown/Multiple.