[Haskell-cafe] An ugly zip3 problem..

[Bryan O'Sullivan]

Michael Feathers wrote:

> Would Haskell's type system allow you to pass a function of arbitrary
> arity, discern its arity, use that information to construct the
> appropriate structure for iteration, and then apply it?

The answer is probably "yes", because almost every time I've thought
that a type system related question had an answer of "no", someone has
been able to point me at a paper by Oleg Kiselyov.

But if you're convolving a one-dimensional vector, and it's structured
as a list, a simpler approach is to use a variant of a zipper data
structure.  Basically, as you traverse the list, you build a new list of
the elements that you've already consumed.

Let's say your list looks like this:

[1,2,3,4,5,6,7,8]

You start off with an empty list of items you've consumed, and for each
item you pull off the list you're consuming, you push it onto the list
you've consumed.

[] 1 [2,3,4,5,6,7,8]
[1] 2 [3,4,5,6,7,8]
...
[4,3,2,1] 5 [6,7,8]
...

Your consumption function can then use pattern matching to pick out an
appropriate number of neighbouring elements from the fronts of the list
you're about to consume and the list you've just consumed.  To change
the number of elements you're looking at, you just modify the two
patterns, not the types or data structures you're using.

This technique, though cute, has several drawbacks.

1.  Lists won't exactly make your performance fly.  You're also
constructing an entire list of already seen values when you only need a
handful from near the front.  This capability makes sense when you need
to be able to switch the direction of iteration for some reason, but
that doesn't apply here.
2.  Because you can't pattern match on elements in an array, you can't
pick this approach up and transplant it to a different underlying data
structure.
3.  I don't know how to construct a useful zipper over lists of higher
order (e.g. lists of lists), so at least with my limited brain power and
attention span, the approach falls apart if you want to convolve a 2D or
higher vector.

	<b