Discussion: traversing roots and leaves

[Mario Blažević]

On 2017-01-19 02:57 PM, David Feuer wrote:
> 2. Leaves are really painful. Data structures that store at most one
> element per leaf make obvious traversals expensive. For example, in
> Data.Map, the obvious implementation would be
>
> instance Traversable (Map k) where
>   traverse _ Tip = pure Tip
>   traverse f (Bin s k v l r) =
>     liftA3 (Bin s k) (f v) (traverse f l) (traverse f r)
>
> The trouble is that we would generate a slew of `pure Tip`s that we'd
> then have to combine. For instance, (Bin 1 k v Tip Tip) would give
>  liftA3 (Bin 1 k) (f v) (pure Tip) (pure Tip)
>
>
> It makes me rather sad to have to write disgustingly ugly Traversable
> instances just to avoid silly performance issues like this. Does anyone
> have an idea for fixing (2), and ideally simultaneously taking care of (1)?

	I can't offer any immediate fix, but my impression of problem (2) is 
that it's for compiler to solve. I doesn't seem right that you should be 
manually enumerating all the simple cases close to the tips and inlining 
them explicitly.

	Since traverse is forcing the entire spine of the Map, there is not 
issue with the change in strictness. The compiler should in principle be 
smart enough to enumerate all possible node shapes and expand the 
function definitions for each of them. It would be similar to loop 
unrolling in some ways.

	Since this kind of transformation would probably be expensive at 
compile-time and would increase the generated code size, it should 
likely require a command-line option (-O2) or a pragma to activate.

	In short, the solution to problem #2 is to log a GHC proposal and get 
the burden off your shoulders.