Re: [Haskell-cafe] General function to count list elements?

Well, this definition, although correct, contradicts the OP's claim that \x->x /= \y->if 1==1 then y else undefined :) I'm leading the OP to the thought that necessity Eq constraint and lack of an Eq instance for functions (and thus non-existence of a universally polymorphic 'count' function) is something dictated by the nature of the world, not by the nature of Haskell. 2009/4/18 John A. De Goes :

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

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

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