Описание тега tailrecursion-modulo-cons

Описание тега Вопросы с тегом

Tail recursion modulo cons is similar to ordinary tail recursion, except that the recursive call is wrapped in a tail call to a constructor, which can be allocated and partially filled in _before_ the recursive call which thus becomes tail.

Tail recursion modulo cons is similar to ordinary tail recursion, except that the recursive call is made inside a tail call to a data cons tructor.

If we first make the recursive call to find out its result, and only then create the data record to be returned holding that recursive result (as well as some additional, "local" data in other fields), the overall call is not tail. It would be tail, if not for the cons truction of that data record to be returned as the overall result.

Instead, that data record can be cons tructed (i.e. allocated and have all its local data fields filled) before the recursive call is made which fills the remaining slot.

This recursive call thus becomes actual tail call, open to tail call optimization.

In terms of e.g. lists this means building them in top-down manner, having the recursion extend the list's tail, as opposed to the bottom-up order where the recursive call builds the whole tail first and only then the head element is prepended to it, as in regular recursion.

It is thus closely related to co recursion, and to the "tail recursion with accumulator" technique, which itself is closely related to monoidal types of values where

   A + (B + (C + (D + (....))))  ==   (A + B) + (C + (D + (....)))
                                 ==  ((A + B) + C) + (D + (....))
                                 ==  ....