[Haskell-cafe] Functional GUI combinators for arbitrary graphs of components?

[Brian Hulley]

Hi,
I've been looking at the Fudgets research 
(http://www.cs.chalmers.se/ComputingScience/Research/Functional/Fudgets/ ) 
as an example of a purely functional gui.

Afaiu a brief summary is that a Fudget can represent a GUI widget or some 
other object, which can have some internal state, and which receives and 
passes messages to the other Fudgets it is connected to. Fudgets are 
connected to each other by combinators eg:

    second >==< first        -- sequential (first sends messages to second)
    a >*< b                       -- parallel

There is a continuation passing implementation such that the messages are 
passed and internal states of Fudgets are updated (by replacing each fudget 
with an updated fudget) as these expressions are evaluated hence the message 
passing and maintenance of state doesn't involve any IORefs though 
interaction with external devices such as the OS uses IO.

Anyway to get to my point, though all this sounds great, I'm wondering how 
to construct an arbitrary graph of Fudgets just from a fixed set of 
combinators, such that each Fudget (node in the graph) is only mentioned 
once in the expression. To simplify the question, assume we have the 
following data structure to describe the desired graph:

    data LinkDesc a
        = Series a a
        | Broadcast a [a]
        | Merge [a] a

    type GraphDesc a = [LinkDesc a]

and a function to compute a combined object (eg Fudget) corresponding to an 
arbitrary graph would be:

    mkObj :: Ord label => Map label Obj -> GraphDesc label -> Obj
    mkObj = -- ???

The result of mkObj will be some expression, composed from a finite set of 
combinators applied to the named objects, but with the all important 
property that each named object appears no more than once in the expression 
(this is what allows Fudgets to correspond to notional objects which 
maintain internal state - during evaluation each fudget gets replaced by an 
updated fudget hence can only appear once in the whole expression).

As a very simple example using existing Fudgets combinators,

    type Map label value = [(label, value)]

    mkObj [("A", objA), ("B", objB), ("C", objC)]
                [Series "A" "B", Series "B" "C"]

    ===    objC >==< objB >==< objA

and

    mkObj [("A", objA), ("B", objB), ("C", objC)]
                [Broadcast "A" ["B", "C"]]

    === (objB >*< objC) >==< objA

However:

    mkObj [("A", objA), ("B", objB), ("C", objC), ("D", objD)]
            [Broadcast "A" ["B", "C"], Series "B" "D", Series "A" "D"]

    === ???

The Fudgets library provides many combinators eg for looping, but even so, I 
don't think there are sufficient combinators to express the above graph 
(though possibly extra nodes and tagging/untagging would solve this 
example), or more heavily connected graphs such as:

        [Series "A" "B", Series "B" "C", Series "C" "D", Series "D" "B", 
Series "C" "A"]

This problem is so general (ie converting a cyclic graph into an expression 
tree such that each node appears no more than once) that I'm sure someone 
somewhere must already have determined whether or not there can be a 
solution, though I don't know where to look or what to search for.

Any ideas?
Thanks, Brian.
-- 
http://www.metamilk.com