How to implement an half-edge data structure in Haskell ?

Question

For a description of the data structure see

• http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml
• http://www.cgal.org/Manual/latest/doc_html/cgal_manual/HalfedgeDS/Chapter_main.html

An half-edge data structure involves cycles.

• is it possible to implement it in a functional language like Haskell ?
• are mutable references (STRef) to way to go ?

Thanks

Answer 1

Obviously the problem is that a half-edge references the next and the opposite half-edge (the other references are no problem). You can "break the cycle" e.g. by referencing not directly to other half-edges, but to reference just an ID (e.g. simple Ints). In order to look up a half-edge by ID, you can store them in a Data.Map. Of course this approach requires some book-keeping in order to avoid a big hairy mess, but it is the easiest way I can think of.

Stupid me, I'm not thinking lazy enough. The solution above works for strict functional languages, but is unnecessary for Haskell.

Answer 2

If the task in question allows you to build the half-edge structure once and then query it many times, then lazy tying-the-know approach is the way to go, as was pointed out in the comments and the other answer.

However, if you want to update your structure, then purely-functional interface might prove cumbersome to work with. Also, you need to consider O(..) requirements for update functions. It might turn out that you need mutable internal representation (probably with pure API on top) after all.