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

Eugene Kirpichov ekirpichov at gmail.com
Sat Apr 18 12:21:20 EDT 2009

```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 <john at n-brain.net>:
>
> 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 <nowgate at yahoo.com>:
>>>
>>> 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 <ekirpichov at gmail.com> wrote:
>>>
>>> From: Eugene Kirpichov <ekirpichov at gmail.com>
>>> Subject: Re: [Haskell-cafe] General function to count list elements?
>>> To: "michael rice" <nowgate at yahoo.com>
>>> 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 <nowgate at yahoo.com>:
>>>>
>>>> Is there a general function to count list elements. I'm trying this
>>>>
>>>> count :: a -> [a] -> Int
>>>> count x ys = length (filter (== x) ys)
>>>>
>>>>
>>>> =============
>>>>
>>>> [michael at localhost ~]\$ ghci count
>>>> GHCi, version 6.10.1: http://www.haskell.org/ghc/  :? for help
>>>> [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)
>>>> Prelude>
>>>>
>>>> =============
>>>>
>>>> Not sure what it's trying to tell me other than I need an (Eq a)
>>>> somewhere.
>>>>
>>>> Michael
>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> Eugene Kirpichov
>>> Web IR developer, market.yandex.ru
>>>
>>>
>>
>>
>>
>> --
>> Eugene Kirpichov
>> Web IR developer, market.yandex.ru
>> _______________________________________________
>>
>
> _______________________________________________