[Haskell-cafe] Lazy cons, Stream-Fusion style?

[Henning Thielemann]

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 
something?

At least I found that the 'Skip' constructor can be omitted for audio 
synthesis:
    http://hackage.haskell.org/packages/archive/synthesizer-core/0.4.0.4/doc/html/Synthesizer-State-Signal.html


>> bad_loopy :: [Int]
>> bad_loopy = S.append1 (S.take 10 v) []
>>   where
>>     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:
   http://code.haskell.org/storablevector/Data/StorableVector/Cursor.hs

However if there remains only one bit of laziness in an inner loop, you 
will not get good efficiency.