Speed Up Gloss Simulation by Limiting Size of Lists to Plot

I am using Gloss to simulate a spiking neural network .. I want to plot the input and generated spike histories in sliding graphs (fixed window size). I wrote the plotting functions and they work well. However, if I let the sim run for a minute, since I'm not limiting the size of the histories (but I'd like to, somewhere between 5000 and 10000), it's quite slow (it performs a convolution to convert spikes back to an 'analog' plot).

I wrote the code below to limit the list lengths, which works, but it seems a bit kludgy .. and somewhat slow.

limitHists :: Float -> Float -> World -> World
limitHists spike input w =
  let w' =  if wSGSpikeHistFull w  then w {wSGSpikeHist = (drop 1 (wSGSpikeHist w) ++[spike])}
                   else if length  (wSGSpikeHist w) > 5000
                           then w  {wSGSpikeHistFull = True}
                           else w {wSGSpikeHist = (wSGSpikeHist w) ++ [spike]}
      w'' = if wSGInputHistFull w' then w'{wSGInputHist =  (drop 1 (wSGInputHist w') ++ [input])}
                   else if length  (wSGInputHist w) > 5000
                           then w' {wSGInputHistFull = True}
                           else w' {wSGInputHist = (wSGInputHist w) ++ [input]}
  in w''

I'm duplicating the code for each 'history' type. It seems that Haskell doesn't allow me to abstract the field names.

Even though I limit the list size the profiler says it takes about 10% of the time just to do this function.. apparently there's some O(n) going on.

So, I have two questions ..

1. Is there a way to 'Don't Repeat Yourself' in my code?

2. Should I be using some other technique to do this that's faster ?

• Data.Sequence ?
• Data.Array ?
• Data.Vector ?
• Data.Circular.List ?
• Okasake amortization ?

The problem might be that since the sim is running at 60fps then the above data structures have to do a 'toList' equivalent each frame to make Gloss happy.

I know that some of this may be trial and error to find out what's faster but I just wanted to see if I was missing something obvious.

Any help appreciated,

Thanks,

Tom

The most obvious way to not repeat yourself would be to define a Hist
type and have World use two of them, something like this:

data Hist = Hist { hist :: [Float], histFull :: Bool }

data World = World { spikeHist :: Hist, inputHist :: Hist }

Probably with a function to add a value:

addDatum :: Float -> Hist -> Hist

You could avoid recalculating length all the time by keeping track of
the number of items yourself. This count would make the histFull flag
unnecessary, so it would make the logic simpler if anything.

However, you are right in thinking a list is not the best data
structure here. We can avoid calculating length but we can't avoid
adding items to the end which is also linear time. (We could keep the
list in reverse order so we could add items at the front, but then
we'd be deleting them at the end which is no better.)

Data.Sequence is what I would use. Data.Array isn't suitable
because you can't quickly modify single items. Data.Vector isn't
really for vectors that change size but you could maybe build your own
ring buffer on top of it.

David's answer is a good one. I thought it might be fun to mention another very simple data structure for implementing a queue, namely, a pair of lists. One stores the "front" of the queue in forward order, and the other stores the "back" of the queue in reverse order.

type Q a = ([a], [a])

push :: a -> Q a -> Q a
push a (front, back) = (front, a:back)

-- for simplicity of presentation, this infinitely loops if the queue is empty
pop :: Q a -> (a, Q a)
pop (a:front, back) = (a, (front, back))
pop ([], back) = pop (reverse back, [])

It's pretty simple. However, if you need to regularly traverse the entire queue in order, it may not be suitable. That seems like it might spell trouble for a convolution, but it doesn't have to. You can convolve your sequence with the (zero-padded) front of the queue, and convolve the reverse of your sequence with the (zero-padded) back of the queue, then join the two results in the middle by adding together the overlapping outputs.