Hi,
Recently I was trying to make this function tail recursive:
flatten : Doc -> Doc
flatten doc =
case doc of
Concatenate doc1 doc2 ->
Concatenate (flatten doc1) (flatten doc2)
Nest i doc1 ->
Nest i (flatten doc1)
... -- More cases but they were already tail recursive.
To achieve this I introduced lambdas into the custom type:
type Doc
= Empty
| Concatenate (() -> Doc) (() -> Doc)
| Nest Int (() -> Doc)
... -- More constructors
flatten : Doc -> Doc
flatten doc =
case doc of
Concatenate doc1 doc2 ->
Concatenate (\() -> flatten (doc1 ())) (\() -> flatten (doc2 ()))
Nest i doc1 ->
Nest i (\() -> flatten (doc1 ()))
... -- More cases but they were already tail recursive.
But it occurs to me there is another way of doing this, which is to add a new constructor to the custom type called Flatten which stands for ‘flatten this later’. Code is going to look like:
type Doc
= Empty
| Concatenate Doc Doc
| Nest Int Doc
| Flatten Doc -- Flatten the doc later.
... -- More constructors
flatten : Doc -> Doc
flatten doc =
case doc of
Concatenate doc1 doc2 ->
Concatenate (Flatten doc1) (Flatten doc2)
Nest i doc1 ->
Nest i (Flatten doc1)
... -- More cases but they were already tail recursive.
In other code that uses this custom type, whenever a Flatten is encountered, its value can be extracted by passing it through the flatten function.
case someDoc of
Flatten doc -> doStuff (flatten doc)
My question is, is this generally going to be faster than using a lambda to make the calculation lazy? I suppose the only real answer is to benchmark and compare - but interested to see if anyone has applied this technique previously with good effect.
There is a comment on the old elm-trampoline package, which makes me think using the lambdas is likely to be slower:
https://github.com/elm-lang/trampoline - “This strategy creates intermediate closures, which is very expensive in JavaScript, so use this library only when it is essential that you recurse deeply.”
Wrapping in a constructor to make it lazy isn’t going to create a closure is it? It will keep the arguments to be passed to flatten on the heap instead?
The disadvantage of this technique is that I need to add a new constructor to the type for each function I want to lazily apply - fine in this case as I only have the flatten function or possibly a couple more.