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

13 May 2008


      Using IDs is the only way.  Haskell has no concept of circular data
structures.  An implementation might use them internally, but there is no
such language concept.  So what you have are infinitely unfolding trees and
they cannot be compared for equality.

  -- Lennart

On Tue, May 13, 2008 at 5:29 PM, Leonard Siebeneicher 
wrote:
...
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 ----
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

Lennart Augustsson