search

amosr / merges

playing around with merges
0 stars 0 forks source link

Reference to other DFA work #1

Open FranklinChen opened 9 years ago

FranklinChen commented 9 years ago

I came from your blog post on this at http://www.cse.unsw.edu.au/~amosr/blog/2015-02-25-mergingmerges.html and was reminded of the DFA stuff in http://hackage.haskell.org/package/stream-fusion and the TODO comments regarding merging in the library http://hackage.haskell.org/package/stream-fusion-0.1.2.5/docs/src/Data-List-Stream.html !

amosr commented 9 years ago

Hi! I had a look, but I'm not sure what you mean by the DFA stuff in stream fusion? There's definitely a resemblance between the Step type and the DFAs, though.

Yeah, so the big limitation with stream fusion is that it can only fuse two things together, if the producer is inlined into the consumer. And producers won't be inlined if they're consumed multiple times - so no fusion! A sort of flow-on effect of this is that the consumer of the stream has sole control over the evaluation of its inputs. Whereas, if you want to do horizontal fusion as well, all the different bits have to agree on when to advance the inputs, so you need some scheduler that's aware of the whole picture to make these decisions.