[Haskell-cafe] General function to count list elements?
John A. De Goes
john at n-brain.net
Sat Apr 18 12:02:51 EDT 2009
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
John A. De Goes
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
>> The first argument is the identity function.
>> The second argument is a list of a different form of the identity
>> 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.
>> --- 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>
>> Cc: haskell-cafe at 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))
>> 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)
>>> with this error upon loading
>>> [michael at 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 )
>>> 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.
>>> Not sure what it's trying to tell me other than I need an (Eq a)
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>> Eugene Kirpichov
>> Web IR developer, market.yandex.ru
> Eugene Kirpichov
> Web IR developer, market.yandex.ru
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe