Mutually recursive structures

Timothy Docker
Tue, 17 Oct 2000 12:30:58 +1100 (EST)

The following problem has been taxing me....

I have a list of pairs that I have parsed from a input file, which
represent a hiirarchy, where the first element is the name of the object,
and the second is the name of the parent if there is one:

     type ParseOutput = [(String,Maybe String)]

I wish to convert this to a list of "objects", where from each object I can
navigate to the parent object (if any), or the children (if any):

    data Obj = Obj { name::String,
                     parent::(Maybe Obj),
                     children::[Obj] }

    type Result = [Obj]

    convert:: ParseOutput -> Result

In a language with mutable references, this would be a relatively
straightforward. I would just create a dictionary mapping from name to
Obj, and then iterate over them, filling in the parents and children
where appropriate.

    odict = {}
    for (name,parent) in parseOutput:
        odict[name] = Obj()

    for (name,parent) in parseOutput:
        if parent:
            parent = odict[parent]
            child  = odict[name]
            child.parent = parent
            parent.children.append( child )

This gives away my background! How can I do this in Haskell? If I
don't have mutable references, I figure that I must need to use
laziness in some way, perhaps similar to how I would build an infinite

A hint or two would be great.