Two functions are equal iff they have the same domain and range and the same outputs for the same inputs. Simple to state, but extremely difficult to implement in a useful way, and impossible to implement in a perfect way. If you had a compiler or algorithm capable of determining function equality, you could use it to prove or disprove arbitrary theorems in mathematics. Regards, John A. De Goes N-BRAIN, Inc. The Evolution of Collaboration http://www.n-brain.net | 877-376-2724 x 101 On Apr 18, 2009, at 9:39 AM, Eugene Kirpichov wrote:

Could you then provide an example of two functions that *are* equal, or, even better, a definition of equality for arbitrary functions? Since Haskell may be compiled into C, this must be a definition that is implementable in C.

2009/4/18 michael rice :

...

Though I haven't tried it out, it's trying to use my function to count functions.

The first argument is the identity function.

The second argument is a list of a different form of the identity function.

Though the two identity functions, given the same input, would produce the same output, I doubt they would be equal.

So my guess at an answer would be zero.

Michael

--- On Sat, 4/18/09, Eugene Kirpichov wrote:

From: Eugene Kirpichov Subject: Re: [Haskell-cafe] General function to count list elements? To: "michael rice" Cc: haskell-cafe@haskell.org Date: Saturday, April 18, 2009, 11:03 AM

What should

count (\x -> x) (replicate 10 (\y -> if 1==1 then y else undefined))

return?

2009/4/18 michael rice :

...

Is there a general function to count list elements. I'm trying this

count :: a -> [a] -> Int count x ys = length (filter (== x) ys)

with this error upon loading

=============

[michael@localhost ~]$ ghci count GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( count.hs, interpreted )

count.hs:2:29: Could not deduce (Eq a) from the context () arising from a use of `==' at count.hs:2:29-32 Possible fix: add (Eq a) to the context of the type signature for `count' In the first argument of `filter', namely `(== x)' In the first argument of `length', namely `(filter (== x) ys)' In the expression: length (filter (== x) ys) Failed, modules loaded: none. Prelude>

=============

Not sure what it's trying to tell me other than I need an (Eq a) somewhere.

Michael

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

-- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Sometimes I do miss the pragmatic C solution:- two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;) - two function pointers that are different, might or might not represent that same functions. But this weak equality can sometimes be handy. For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess... On Sat, Apr 18, 2009 at 6:02 PM, John A. De Goes wrote:

Two functions are equal iff they have the same domain and range and the same outputs for the same inputs. Simple to state, but extremely difficult to implement in a useful way, and impossible to implement in a perfect way.

If you had a compiler or algorithm capable of determining function equality, you could use it to prove or disprove arbitrary theorems in mathematics.

And when the need gets big enough you pull out StablePtr and use that. :) On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen wrote:

Sometimes I do miss the pragmatic C solution: - two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;) - two function pointers that are different, might or might not represent that same functions. But this weak equality can sometimes be handy. For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess... On Sat, Apr 18, 2009 at 6:02 PM, John A. De Goes wrote:

...

Two functions are equal iff they have the same domain and range and the same outputs for the same inputs. Simple to state, but extremely difficult to implement in a useful way, and impossible to implement in a perfect way.

If you had a compiler or algorithm capable of determining function equality, you could use it to prove or disprove arbitrary theorems in mathematics.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Sorry, I meant StableName. On Mon, Apr 20, 2009 at 1:00 AM, Peter Verswyvelen wrote:

Or a StableName? I guess StablePtr prevents the GC to move the Haskell object, so for just doing ugly comparing StableName would be better?

On Mon, Apr 20, 2009 at 12:45 AM, Lennart Augustsson wrote:

...

And when the need gets big enough you pull out StablePtr and use that. :)

On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen wrote:

...

Sometimes I do miss the pragmatic C solution: - two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;) - two function pointers that are different, might or might not represent that same functions. But this weak equality can sometimes be handy. For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess... On Sat, Apr 18, 2009 at 6:02 PM, John A. De Goes wrote:

...

Two functions are equal iff they have the same domain and range and the same outputs for the same inputs. Simple to state, but extremely difficult to implement in a useful way, and impossible to implement in a perfect way.

If you had a compiler or algorithm capable of determining function equality, you could use it to prove or disprove arbitrary theorems in mathematics.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

A solution with enums would severely suffer from the expression problem... One would need to extent the enums every time one needs to support a new function. Maybe could be solved with type classes, don't know. On Mon, Apr 20, 2009 at 3:57 PM, Achim Schneider wrote:

Lennart Augustsson wrote:

...

On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen wrote:

...

For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess...

And when the need gets big enough you pull out StablePtr and use that. :)

Waaagh! Don't give him ideas, he's going to do it... Make yourself an enum, generate your list, nub it, then transform it to a list of functions. Always do everything with the least information sanely feasible, and a function is more information than a value, even if you can't get at it, anymore.

-- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe