7

I'm thinking specifically for signal processing. Let's say I wanted to do something like double the magnitude of an incoming signal. I would want it to be very fast, so I would want the signal to be held in contiguous memory (e.g. unboxed vectors). But this signal could go on indefinitely, so I would want it to be treated as an infinite list; I'd rather call map (*2) signal once instead of calling it for every signal chunk.

Is there a data structure in Haskell that would buffer these data chunks so that I could get contiguous memory performance, but treat the data as an infinite stream?

Ganesh Sittampalam
  • 28,821
  • 4
  • 79
  • 98
awelkie
  • 2,422
  • 1
  • 22
  • 32
  • [I explored whether it's feasible to design a DSP library this way a while ago](https://github.com/leftaroundabout/timed-media/blob/master/Media/Timed/Audio.hs). (I think it is, at least you can build some cheesy example melody things... but I've not done much serious work on it.) A chunked infinite list, but without all that time-bookkeeping would be an interesting project on its own right. – leftaroundabout Jun 28 '14 at 15:36
  • 1
    Lazy bytestrings do this, except they can only hold bytes. Internally, a lazy bytestring is a list of unboxed arrays. I don't know of a similar library for other data types. – Heatsink Jun 28 '14 at 18:20
  • Lazy bytestrings seems to be exactly what I'm asking for. It seems like [this library](http://hackage.haskell.org/package/storablevector-0.2.8.3/docs/Data-StorableVector-Lazy.html) attempts to do the same thing but with arbitrary elements. – awelkie Jun 28 '14 at 21:55

1 Answers1

6

This is just a long shot, but what about using streams of large enough chunks of unboxed vectors? This would have the advantage of vectors' performance, and at the same time, fusion thanks to streams.

Update: The idea is to define a newtype such as:

import Data.Array.Unboxed
import Data.Stream
import Data.Word

newtype Word8Stream = Word8Stream (Stream (UArray Int Word8))

and then define the generic functions you need such as

smap :: (Word8 -> Word8) -> Word8Stream -> Word8Stream
smap f (Word8Stream s) = Word8Stream $ fmap (amap f) s
Community
  • 1
  • 1
Petr
  • 62,528
  • 13
  • 153
  • 317
  • This solves the performance issue, but I can't treat the stream of chunks as one long list (or vector), can I? I would have to use map.map, instead of one invocation of map, if I wanted to apply a function that expects a vector of elements, right? – awelkie Jun 28 '14 at 19:26
  • 4
    @DurnWhippersnapper You're right, but that can be hidden in a `newtype` data type and a set of corresponding functions, so that the internal implementation is completely opaque to other modules. I updated the answer. – Petr Jun 28 '14 at 19:48
  • Just make it a functor. – PyRulez Jun 29 '14 at 18:30
  • @PyRulez Functor probably won't be possible, as for performance reasons the data type most likely won't be polymorphic. However, [ListLike](https://hackage.haskell.org/package/ListLike) could be used for this, as it supports monomorphic types as well. – Petr Jun 29 '14 at 19:28
  • What does polymorphism matter? – PyRulez Jun 29 '14 at 19:31
  • @PyRulez `Functor` instances must be fully polymorphic. – Petr Jun 29 '14 at 19:34
  • Well sure, but how does polymorphism hurt performance. Types are inferred, type-checked, and then done away with once you compile. – PyRulez Jun 29 '14 at 19:38
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/56489/discussion-between-petr-pudlak-and-pyrulez). – Petr Jun 29 '14 at 19:42