[Haskell-cafe] Stream fusion and span/break/group/init/tails

[Duncan Coutts]

On Mon, 2013-04-29 at 20:19 +0200, Gábor Lehel wrote:

> Thanks for the explanation. I looked at your thesis previously, but only
> read through a couple of sections (including the one about concatMap). I
> might go through the state machine parts as well now that I know the
> significance/relevance.
> 
> The thing in particular that was motivating me is that if it weren't for
> Skip, it seems that to some extent (I haven't had time to investigate
> precisely what extent) you could write a stream fusion framework in a
> datatype-generic way, parameterized over the base functor. But it wasn't
> obvious to me how (or whether) you would translate Skip. But maybe the
> state machine perspective will provide some insight into that. I'll think
> about it.

Oh I think you can write it in a data-type generic way.

If your datatype is described by a base functor F, then the skip version
is a simple transformation on that functor.

F_skip a = F a + a

And then the stream type for F is  nu a. F_skip a

See section 3.6.

In most of my theory chapter I write it in this style, rather than using
the list functor specifically.

Duncan