How to elegantly represent infinite Haskell recursive datastructure in Python?

Question

Regarding How to elegantly represent finite Haskell recursive datastructure in Python?, I was thinking how would I represent an infinite data structure (without any non-constructor function inside it) from Haskell in Python using Haskell FFI.

Unfortunately I haven't found anything as elegant as was in this great this answer (JSON representation of finite structure) from leftaroundabout.

Is there any similarly elegant way to represent infinite data structure from Haskell to Python?

Answer 1

I suggest one of two routes.

• Pass an opaque pointer to Python. Define an API in Haskell for observing and constructing things of the appropriate type, and expose that API through the FFI. (I also suggested this at the linked question...)
• Explicitly construct graphs in the first place, and pass the graph structure to Python. For example, you could use data-reify to be able to do this while retaining the usual syntax for constructing and pattern matching on your custom types.

Answer 2

I think Auto-vivification provides an interesting way to create a recursive data structure. For python...

>>> class Tree(dict):
...     def __missing__(self, key):
...         value = self[key] = type(self)()
...         return value

>>> # Common names by class, order, genus, and type-species
>>> common_names = Tree()
>>> common_names['Mammalia']['Primates']['Homo']['H. sapiens'] = 'human being'
>>> common_names
{'Mammalia': {'Primates': {'Homo': {'H. sapiens': 'human being'}}}}

There is also a more compact implementation using defaultdict by Stephan

import collections

def Tree():
    return collections.defaultdict(Tree)