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

Eugene Kirpichov ekirpichov at gmail.com
Sat Apr 18 12:48:26 EDT 2009


Also, having such an equality test will  introduce ambiguity and
unsoundness, prevent the compiler from certain optimizations etc.
For example, should "(+5)==(+5)" be true or false? What about "let
f=(+5) in f==f"?
If you are declaring the first equality to be true, then you are
implying that the compiler must implement extensional equality, which
is impossible. Consider let x=5 in (+x)==(+x).
If you are declaring it to be false, then you are breaking referential
transparency: you can't anymore safely substitute "let x=v in E" with
E[x:=v].

C doesn't have these problems because it never declared that it has
any form of referential transparency or mathematical soundness;
neither does it have closures and currying.
Scheme explicitly declares that the result of equal? on functions
can't be relied upon.

Haskell takes the mathematically sound path: it simply outlaws ambiguities.

2009/4/18 michael rice <nowgate at yahoo.com>:
> I know functions can be compared in Scheme
>
> Welcome to DrScheme, version 4.1 [3m].
> Language: Swindle; memory limit: 128 megabytes.
>> (equal? equal? equal?)
> #t
>>
>
>
> but apparently not in Haskell
>
> [michael at localhost ~]$ ghci
> 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.
> Prelude> (==) (==) (==)
>
> <interactive>:1:0:
>     No instance for (Eq (a -> a -> Bool))
>       arising from a use of `==' at <interactive>:1:0-13
>     Possible fix: add an instance declaration for (Eq (a -> a -> Bool))
>     In the expression: (==) (==) (==)
>     In the definition of `it': it = (==) (==) (==)
> Prelude>
>
> though I'm new at Haskell and may not be posing the question properly.
>
> I would think a language with 1st-class support for functions would
> certainly include comparing them.
>
> To compare two functions in C, I would compare their machine addresses.
>
> 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>
> Cc: haskell-cafe at haskell.org
> Date: Saturday, April 18, 2009, 11:39 AM
>
> 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>
>> 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))
>>
>> 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)
>>>
>>> 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 )
>>>
>>> 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 at 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
>
>



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


More information about the Haskell-Cafe mailing list