Yes I agree, so far StableNames have been a good approximation, except for the problem I described when using monads/class constraints :-(
2012/6/26 Lorenzo Bolla <lbo...@gmail.com> > This is very tricky and it really depends on what you mean... > Formally, two functions are the same if they have the same domain and f(x) > == g(x) for each x in the domain. But this is not always > easy/feasible/efficient to implement! (See also > http://en.wikipedia.org/wiki/Rice%27s_theorem and > http://stackoverflow.com/questions/4844043/are-two-functions-equal.) > > Depending on your problem, you might get away with just defining a > "signature" of your function and compare them: for example the signature > could be the concat of the function name, args types, etc. But I'm > speculating here... > > L. > > > > On Tue, Jun 26, 2012 at 4:50 PM, Ismael Figueroa Palet < > ifiguer...@gmail.com> wrote: > >> thanks again for your comments, any idea on how to implement >> "Equivalence" for functions? >> >> 2012/6/26 Lorenzo Bolla <lbo...@gmail.com> >> >>> In other words there is a difference between Identity and Equivalence. >>> What you have implemented with StableName is an "Identity" (sometimes >>> called "reference equality"), as opposed to an "Equivalence" (aka "value >>> equality"). >>> >>> In Python, for example: >>> >>> >>> x = {1:2} >>> >>> y = {1:2} >>> >>> x == y >>> True >>> >>> x is y >>> False >>> >>> L. >>> >>> >>> On Tue, Jun 26, 2012 at 3:42 PM, Lorenzo Bolla <lbo...@gmail.com> wrote: >>> >>>> I think about StableName like the "&" operator in C, that returns you >>>> the memory address of a variable. It's not the same for many reasons, but >>>> by analogy, if &x == &y then x == y, but &x != &y does not imply x != y. >>>> >>>> So, values that are semantically equal, may be stored in different >>>> memory locations and have different StableNames. >>>> >>>> The fact that changing the order of the lines also changes the result >>>> of the computation is obviously stated in the type signature of >>>> makeStableName, which lives in the IO monad. On the other hand >>>> hashStableNAme is a pure function. >>>> >>>> L. >>>> >>>> >>>> >>>> On Tue, Jun 26, 2012 at 3:26 PM, Ismael Figueroa Palet < >>>> ifiguer...@gmail.com> wrote: >>>> >>>>> >>>>> >>>>> 2012/6/26 Lorenzo Bolla <lbo...@gmail.com> >>>>> >>>>>> The point I was making is that StableName might be what you want. You >>>>>> are using it to check if two functions are the same by comparing their >>>>>> "stablehash". But from StableName documentation: >>>>>> >>>>>> The reverse is not necessarily true: if two stable names are not >>>>>>> equal, then the objects they name may still be equal. >>>>>> >>>>>> >>>>>> The `eq` you implemented means this, I reckon: if `eq` returns True >>>>>> then the 2 functions are equal, if `eq` returns False then you can't >>>>>> tell! >>>>>> >>>>>> Does it make sense? >>>>>> L. >>>>>> >>>>> >>>>> Yes it does make sense, and I'm wondering why the hash are equal in >>>>> one case but are not equal on the other case (i.e. using let/where vs not >>>>> using it) because I'd like it to behave the same in both situations >>>>> >>>>> Thanks again >>>>> >>>>> >>>>>> >>>>>> >>>>>> On Tue, Jun 26, 2012 at 1:54 PM, Ismael Figueroa Palet < >>>>>> ifiguer...@gmail.com> wrote: >>>>>> >>>>>>> Thanks Lorenzo, I'm cc'ing the list with your response also: >>>>>>> >>>>>>> As you point out, when you do some kind of "let-binding", using the >>>>>>> where clause, or explicit let as in: >>>>>>> >>>>>>> main :: IO () >>>>>>> main = do >>>>>>> let f1 = (successor :: Int -> State Int Int) >>>>>>> let f2 = (successor :: Int -> Maybe Int) >>>>>>> b2 <- eq f2 f2 >>>>>>> b1 <- eq f1 f1 >>>>>>> print (show b1 ++ " " ++ show b2) >>>>>>> >>>>>>> The behavior is as expected. I guess the binding triggers some >>>>>>> internal optimization or gives more information to the type checker; but >>>>>>> I'm still not clear why it is required to be done this way -- having to >>>>>>> let-bind every function is kind of awkward. >>>>>>> >>>>>>> I know the details of StableNames are probably >>>>>>> implementation-dependent, but I'm still wondering about how to detect / >>>>>>> restrict this situation. >>>>>>> >>>>>>> Thanks >>>>>>> >>>>>>> >>>>>>> 2012/6/26 Lorenzo Bolla <lbo...@gmail.com> >>>>>>> >>>>>>>> From StableName docs: >>>>>>>> >>>>>>>>> The reverse is not necessarily true: if two stable names are not >>>>>>>>> equal, then the objects they name may still be equal. >>>>>>>> >>>>>>>> >>>>>>>> This version works as expected: >>>>>>>> >>>>>>>> import System.Mem.StableName >>>>>>>> import Control.Monad.State >>>>>>>> >>>>>>>> eq :: a -> b -> IO Bool >>>>>>>> eq a b = do >>>>>>>> pa <- makeStableName a >>>>>>>> pb <- makeStableName b >>>>>>>> return (hashStableName pa == hashStableName pb) >>>>>>>> >>>>>>>> successor :: (Num a, Monad m) => a -> m a >>>>>>>> successor n = return (n+1) >>>>>>>> >>>>>>>> -- main :: IO () >>>>>>>> -- main = do >>>>>>>> -- b2 <- eq (successor :: Int -> State Int Int) (successor >>>>>>>> :: Int -> State Int Int) >>>>>>>> -- b1 <- eq (successor :: Int -> Maybe Int) (successor :: >>>>>>>> Int -> Maybe Int) >>>>>>>> -- print (show b1 ++ " " ++ show b2) >>>>>>>> >>>>>>>> main :: IO () >>>>>>>> main = do >>>>>>>> b2 <- eq f2 f2 >>>>>>>> b1 <- eq f1 f1 >>>>>>>> print (show b1 ++ " " ++ show b2) >>>>>>>> where f1 = (successor :: Int -> Maybe Int) >>>>>>>> f2 = (successor :: Int -> State Int Int) >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> hth, >>>>>>>> L. >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> On Tue, Jun 26, 2012 at 1:15 PM, Ismael Figueroa Palet < >>>>>>>> ifiguer...@gmail.com> wrote: >>>>>>>> >>>>>>>>> I'm using StableNames to have a notion of function equality, and >>>>>>>>> I'm running into problems when using monadic functions. >>>>>>>>> >>>>>>>>> Consider the code below, file Test.hs >>>>>>>>> >>>>>>>>> import System.Mem.StableName >>>>>>>>> import Control.Monad.State >>>>>>>>> >>>>>>>>> eq :: a -> b -> IO Bool >>>>>>>>> eq a b = do >>>>>>>>> pa <- makeStableName a >>>>>>>>> pb <- makeStableName b >>>>>>>>> return (hashStableName pa == hashStableName pb) >>>>>>>>> >>>>>>>>> successor :: (Num a, Monad m) => a -> m a >>>>>>>>> successor n = return (n+1) >>>>>>>>> >>>>>>>>> main :: IO () >>>>>>>>> main = do >>>>>>>>> b1 <- eq (successor :: Int -> Maybe Int) (successor :: Int >>>>>>>>> -> Maybe Int) >>>>>>>>> b2 <- eq (successor :: Int -> State Int Int) (successor :: >>>>>>>>> Int -> State Int Int) >>>>>>>>> print (show b1 ++ " " ++ show b2) >>>>>>>>> >>>>>>>>> Running the code into ghci the result is "False False". There is >>>>>>>>> some old post saying that this is due to the dictionary-passing style >>>>>>>>> for >>>>>>>>> typeclasses, and compiling with optimizations improves the situation. >>>>>>>>> >>>>>>>>> Compiling with ghc --make -O Tests.hs and running the program, the >>>>>>>>> result is "True True", which is what I expect. >>>>>>>>> However, if I change main to be like the following: >>>>>>>>> >>>>>>>>> main :: IO () >>>>>>>>> main = do >>>>>>>>> b2 <- eq (successor :: Int -> State Int Int) (successor :: >>>>>>>>> Int -> State Int Int) >>>>>>>>> b1 <- eq (successor :: Int -> Maybe Int) (successor :: Int >>>>>>>>> -> Maybe Int) >>>>>>>>> print (show b1 ++ " " ++ show b2) >>>>>>>>> >>>>>>>>> i.e. just changing the sequential order, and then compiling again >>>>>>>>> with the same command, I get "True False", which is very confusing >>>>>>>>> for me. >>>>>>>>> Similar situations happens when using the state monad transformer, >>>>>>>>> and manually built variations of it. >>>>>>>>> >>>>>>>>> It sounds the problem is with hidden closures created somewhere >>>>>>>>> that do not point to the same memory locations, so StableNames yields >>>>>>>>> false >>>>>>>>> for that cases, but it is not clear to me under what circumstances >>>>>>>>> this >>>>>>>>> situation happens. Is there other way to get some approximation of >>>>>>>>> function >>>>>>>>> equality? or a way to "configure" the behavior of StableNames in >>>>>>>>> presence >>>>>>>>> of class constraints? >>>>>>>>> >>>>>>>>> I'm using the latests Haskell Platform on OS X Lion, btw. >>>>>>>>> >>>>>>>>> Thanks >>>>>>>>> >>>>>>>>> -- >>>>>>>>> Ismael >>>>>>>>> >>>>>>>>> >>>>>>>>> _______________________________________________ >>>>>>>>> Haskell-Cafe mailing list >>>>>>>>> Haskell-Cafe@haskell.org >>>>>>>>> http://www.haskell.org/mailman/listinfo/haskell-cafe >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> Ismael >>>>>>> >>>>>>> >>>>>> >>>>> >>>>> >>>>> -- >>>>> Ismael >>>>> >>>>> >>>> >>> >> >> >> -- >> Ismael >> >> > -- Ismael
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe