[Haskell-cafe] Instance of Eq on cyclic data structure?

[Leonard Siebeneicher]

Hi.

I am testing a winged edge data structure.

> module Main where
>
> type Point3 = (Float, Float, Float)
>
> data Body= Body [Vertex] [Edge] [Face] deriving(Eq)
> data Face= Face Edge deriving(Eq)
> data Edge= Edge      (Vertex, Vertex)
>     (Face, Face)
>     (Edge, Edge)
>     (Edge, Edge) deriving(Eq)
> data Vertex= Vertex Point3 Edge deriving(Eq)
...
> --- Face, Edge, Vertex: Conversion
>
> getVertsFromFace :: Face -> [Vertex]
> getVertsFromFace (Face startEdge) = process_wing_clockwise startEdge
>     where
>       process_wing_clockwise (Edge
>                               (vp, _)
>                               _
>                               (_, eWing1)
>                               _)
>           | startEdge == eWing1 =
>               [vp]
>           | otherwise =
>               vp : (process_wing_clockwise eWing1)
>
>
> --- Misc procedures
> printPointList :: [Vertex] -> IO ()
> printPointList [] = return ()
> printPointList ((Vertex p _ ):vs) = putStr (show p) >>
>                                     printPointList vs
>
> --- main
> main =
>     do
>       let q = createQuad (0,0,0) (0,1,0) (1,1,0) (1,0,0)
>       let f = (\(Body _ _ (face:faces)) -> face) q
>       let verts = getVertsFromFace f
>       printPointList verts
>
>
Here I get a error message.

> (0.0,0.0,0.0)(0.0,1.0,0.0)(1.0,1.0,0.0)runhugs: Error occurred
>
> ERROR - Control stack overflow
>
I think this come because the derived Eq-Instance "==" get into an 
infinite loop

Alternatively I tried following
> --- We want to identify each Body, Face, Edge or Vertex by a number ID
> type ID = Int  --- A special number for identifying, used for Eq
>
> data Body = Body ID [Vertex] [Edge] [Face]
> data Face = Face ID (Edge)
> data Edge = Edge ID
>     (Vertex , Vertex)
>     (Face , Face)
>     (Edge , Edge)
>     (Edge , Edge)
> data Vertex = Vertex ID Edge
>
> --- Eq Instances
> instance Eq Vertex) where
>     (Vertex i1 _) == (Vertex i2 _) = i1 == i2
>
> instance Eq Face where
>     (Face i1 _ ) == (Face i2 _) = i1 == i2
>
> instance Eq Edge where
>     (Edge i1 _ _ _ _) == (Edge i2 _ _ _ _) = i1 == i2
>
>
> instance Eq (Body) where
>     (Body i1  _ _ _) == (Body i2  _ _ _) = i1 == i2
...

This way my code does not hang up. But I have to manage those ugly ID's.
Is there a better way to create instances of class Eq, without something 
like ID?

Thanks for reading.

Best regards, Leonard


>
>
> --------------------
> --------------------
> ---- Begin ----
> --------------------
> module Main where
>
> type Point3 = (Float, Float, Float)
>
> data Body= Body [Vertex] [Edge] [Face] deriving(Eq)
> data Face= Face Edge deriving(Eq)
> data Edge= Edge     (Vertex, Vertex)
>     (Face, Face)
>     (Edge, Edge)
>     (Edge, Edge) deriving(Eq)
> data Vertex= Vertex Point3 Edge deriving(Eq)
>
> {-
>   implementing simple generative modelling
> -}
>
> --- elementar object generation
> createQuad :: Point3 ->
>               Point3 ->
>               Point3 ->
>               Point3 ->
>               Body
>
> createQuad p0 p1 p2 p3 =
>     let
>         {faceFront = Face edge0
>         ;faceBack = Face edge2
>         ;vert0 = Vertex p0 edge0
>         ;edge0 = Edge
>                  (vert0, vert1)
>                  (faceFront, faceBack)
>                  (edge3, edge1)
>                  (edge1, edge3)
>         ;vert1 = Vertex p1 edge1
>         ;edge1 = Edge
>                  (vert1, vert2)
>                  (faceFront, faceBack)
>                  (edge0, edge2)
>                  (edge2, edge0)
>         ;vert2 = Vertex p2 edge2
>         ;edge2 = Edge
>                  (vert2, vert3)
>                  (faceFront, faceBack)
>                  (edge1, edge3)
>                  (edge3, edge1)
>         ;vert3 = Vertex p3 edge3
>         ;edge3 = Edge
>                  (vert3, vert0)
>                  (faceFront, faceBack)
>                  (edge2, edge0)
>                  (edge0, edge2)
>         }
>     in
>       Body [vert0, vert1, vert2, vert3] [edge0, edge1, edge2, edge3] 
> [faceFront, faceBack]
>
> --- Face, Edge, Vertex: Conversion
>
> getVertsFromFace :: Face -> [Vertex]
> getVertsFromFace (Face startEdge) = process_wing_clockwise startEdge
>     where
>       process_wing_clockwise (Edge
>                               (vp, _)
>                               _
>                               (_, eWing1)
>                               _)
>           | startEdge == eWing1 =
>               [vp]
>           | otherwise =
>               vp : (process_wing_clockwise eWing1)
>
>
> --- Misc procedures
> printPointList :: [Vertex] -> IO ()
> printPointList [] = return ()
> printPointList ((Vertex p _ ):vs) = putStr (show p) >>
>                                     printPointList vs
>
> --- main
> main =
>     do
>       let q = createQuad (0,0,0) (0,1,0) (1,1,0) (1,0,0)
>       let f = (\(Body _ _ (face:faces)) -> face) q
>       let verts = getVertsFromFace f
>       printPointList verts
> -----------------
> ---- End ----