This is a question that is in a sense a follow-up of a question I asked earlier, and which was answered.

In that question, the answer to "in which recursion scheme does data only flow bottom up, and in no other way?" was "a catamorphism".

Here, I am looking for the name for (and hence: theory about) the reverse recursion scheme, the one where data flows top-down, and in no other way.

I don't think I am looking for "anamorphism" ... but perhaps there is an error in my thinking. If so, I'd love to hear how. The reason is that an anamorphism is also in a sense a reverse of a catamorphism, but in a different sense than I'm looking for: it's its reverse because rather than collapsing a compound datastructure, it builds one.

As an example of what I'm looking for (in Python), consider the following mechanism that annotates all nodes with their depth:

def annotate_with_depth(node, parent_value=-1):
    my_value = parent_value + 1
    children = [annotate_with_depth(child, my_value) for child in node.children]
    return Node(children, my_value)

The more generic case of this could be something along these lines:

def calculate_depth_from_parent(parent_value, node_):
    return parent_value + 1

def the_generic_thing(mechanism_of_calculation, node, parent_value):
    my_value = mechanism_of_calculation(parent_value, node)

    children = [the_generic_thing(mechanism_of_calculation, child, my_value) for child in node.children]
    return Node(children, my_value)

annotate_with_depth = lambda node: the_generic_thing(calculate_depth_from_parent, node, -1)

As a more interesting example, consider the following task: in a directory tree, annotate each directory (of which you know the name) with its full path.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.