[Haskell-cafe] Lazy cons, Stream-Fusion style?
lemming at henning-thielemann.de
Sun Jan 2 15:03:40 CET 2011
On Sun, 2 Jan 2011, Stephen Tetley wrote:
> I'm trying to make a Stream library, hopefully efficient enough for
> audio synthesis in the style of Jerzy Karczmarczuk's Clarion.
I am trying to code real-time audio synthesis in Haskell for some years
now. I can tell at least, that it is not so easily done. Even with the
right data structure, GHC's optimizer does not always make, what you need.
Thus the most efficiency I get by using LLVM to construct signal
processing code at run time, so far. (see synthesizer-llvm package)
> As performance is important, the obvious model is the Stream-Fusion
> library, but 'cons' is problematic in this style.
Yes, 'cons' is problematic. I think efficient 'cons' needs a material data
structure, not just a generator function as in stream-fusion:Stream.
> data Stream a = forall st. Stream !(st -> Step a st) !st
> For infinite Streams the Done constructor can be removed from the Step
> type, a truly infinite is never done:
For audio synthesis you need also finite signals. Or am I missing
At least I found that the 'Skip' constructor can be omitted for audio
>> bad_loopy :: [Int]
>> bad_loopy = S.append1 (S.take 10 v) 
>> v = 1 `S.cons` v
The problem is that S.cons must take the internal state type of 'v' and
must wrap it in a new type. Thus every S.cons makes the internal state
more complicated. This is inefficient for several applications of S.cons
and impossible for infinitely many calls.
In order to get both elegant laziness and efficiency I played around with
a head-strict list implemented via Storable. Here an efficient 'cons'
seems to be doable:
However if there remains only one bit of laziness in an inner loop, you
will not get good efficiency.
More information about the Haskell-Cafe