Hello,
I come up again with a topic I mentioned some years ago.
I would like to have a comparison instruction that compares the internal
reference of two objects.
Let's call it "req".
req :: a -> a -> Bool
-- of course it is an equivalence operation
req x x = True
req x y = req y x
(req x y) && (req y z) ==> req x z
req x y = false does NOT imply that x and y are different, only that
they are represented differently.
So what?
req allows saving time when comparing larger objects.
This allows reduction mechanisms of complex, e.g. Tree-like
data structures, because equal subtrees can be represented by only one
instance.
Usign this operation contradicts partly the idea of functional programming,
but only with respect to termination.
However, it can allow tremendous run-time savings.
Equality on lists:
Without req
instance Eq a => Eq [a] where
[] == [] = True
(x:xs) == (y:ys) = x==y && xs==ys
_ == _ = False
With req
instance Eq a => Eq [a] where
[] == [] = True
xl@(x:xs) == yl@(y:ys) = (req xl yl) || (x==y && xs==ys)
_ == _ = False
The expression
let x=[1..] in x==x
would not terminate in the first case but succeed in the second.
I came up when I tried to implement Binary Decision Diagrams in
Haskell some years ago and I have the impression that I need them
again soon. It ould be so much nicer with this operation.
Andreas
---------------------------------------------------------------
Andreas C. Doering
Medizinische Universitaet zu Luebeck
Institut fuer Technische Informatik
Ratzeburger Allee 160
D-23538 Luebeck Germany
Tel.: +49 451 500-3741, Fax: -3687
Email: [EMAIL PROTECTED]
Home: http://www.iti.mu-luebeck.de/~doering
quiz, papers, VHDL, music
"The fear of the LORD is the beginning of ... science" (Proverbs 1.7)
----------------------------------------------------------------
