[Haskell-cafe] Fusion of lists and chunky sequences

[Don Stewart]

lemming:
> 
> On the one hand I like to use lists in my code because element types can
> be freely chosen and maximum laziness allows feedback and other tricks. On
> the other hand there are ByteString.Lazy and one could build chunky
> sequences from other fast array implementations. They have constraints on
> the element types like Storable in
>   http://code.haskell.org/~sjanssen/storablevector
>  and IArray multi-parameter type class for UArray.
> 
>  I like to continue writing code for lists, and let the optimizer replace
> it by operations on chunky sequences whereever possible. E.g.
>   Chunky.fromList (List.map f (List.unfoldr g x))
>  might be transformed to
>   Chunky.unfoldr (f ... g) x
> 
> Chunky.fromList serves two purposes:
>  1. I obtain the result in a data structure that can be quickly accessed
> by further operations.
>  2. It tells the optimizer that element granularity for laziness is not
> needed and that the element type fulfills the constraint of the fast array
> type, and thus fusion can go on safely. (As far as I can see.)
> 
>  Is there some framework which fuses lists and chunky sequences? When
> writing fusion rules like the above one by myself, then they interfer with
> Prelude's fusion rules (and they would probably also interfer with those
> of an alternative list fusion framework). The 'map' and 'unfoldr' is
> certainly already fused to the internal 'build' or to another auxiliary
> function. As far as I know, I cannot disable the Prelude rules and give
> the List-Chunk rules priority higher than Prelude's ones.

You can, with some caveats, use a single fusion system across data
structures, and avoid the built in build/foldr system.

I'd start by installing the stream-fusion list library, from hackage,
which gives you the list api, and a fusion mechanism.

To avoid the build in fusion system, you need to:

    * avoid list comprehensions
    * avoid .. (use Stream.enumFromTo instead)

then you can write fusion rules for your structure in terms of streams,
and they'll fuse with list operations as well.

Duncan, Roman and I plan to have strict and lazy bytestrings fusing
on top of the stream-fusion package in Q1 this year, but you can start
now looking at other data structures.

>  I hoped to be able to apply application specific fusion rules by defining
> a newtype wrapper around the chunky sequence type, while keeping the rest
> of the list code unchanged. You might argue, that code cannot be
> application specific if it still relies on the generic list type. Maybe
> it's the best to wrap the list type in a newtype and lift all of the
> application relevant list functions to this type and then define fusion
> rules on the lifted functions.

-- Don