Lazy Layout: single-pass layout algorithm using circular programming

Links
1
13 Likes
3

That’s a good question. I mostly wrote this because I found it cleaner this way, and the performance answer is probably “it depends on what you’re trying to do”.

For this blogpost, it probably doesn’t matter – the layout algorithm’s performance is completely insignificant compared to the time needed to read and
write images. We do traverse things only once, but as you noticed there is some (insignificant) overhead in returning tuples.

In more hypothetical scenarios:

  • You could envision needing to do more traversals than just two. The technique isn’t really limited at two, and depending on your datatype may yield a speedup once you hit N traversals.

  • Maybe there’s a way to combine it with other lazy patterns so that you can
    avoid traversing large parts of your datastructure.

  • I suspect it could be combined with foldr/build fusion in certain cases to avoid building the entire tree…

I think it probably helps more with writing clean code than performance. If the two traversals share computations or patterns, this can help avoid repetition.

For the collage function I have, writing a two pass is sort of tricky since the equivalent of findmin is something like:

measure
  :: Sized a
  => Collage a -> Size

But we’d need to call this traversal at every step of the recursion in collage, so we end up repeating a lot of work!

In order to avoid the extra work, we can store the Size info in all nodes, not just leaves:

data Collage i a
  = S i a
  | H i (Collage i a)
  | V i (Collage i a)

And then we could have:

measure
  :: Sized a
  => Collage i a
  -> Collage (i, Size) a

I don’t like that it makes the datatype a more complex though… maybe I would even introduce a second datatype? I think it becomes clear at that point that the single pass can be cleaner…

1 Like