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

Eugene Kirpichov ekirpichov at gmail.com
Sat Apr 18 13:18:25 EDT 2009


2009/4/18 michael rice <nowgate at yahoo.com>:
>> To compare two functions in C, I would compare their machine addresses.
>>
>
> Why would you need that at all?
>
> How would *you* do it?

Do what?

As for comparing functions, I would not do it at all, because
comparing functions makes no sense: one way of comparison (extensional
equality) is not implementable, whereas the other (object identity)
breaks referential transparency and is impossible to reason about and
generally doesn't have a single reason to work correctly at all.
Object identity has no reason to exist in a language without mutable
objects, like Haskell. That's probably the key.


As for implementing the count function, I would implement it in the
way that people already suggested to you: by putting a constraint onto
its type, namely a constraint that makes it polymorphic *over types
whose values can be compared for equality*, t.i. over members of the
Eq class. This is perfectly correct and does not cause any
mathematical unsoundness.




>
> 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, 12:39 PM
>
> 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
>>>
>>
>
> That's not the functions being compared, but the memory addresses of
> the code implementing them. If your goal is comparing functions to
> answer a question "Are these two values indistinguishable?", equal?
> doesn't help you, because it may answer 'false' even if these two
> values are indistinguishable from a mathematical point of view.
>
>>
>> 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.
>>
>
> Again, this is first-class support for memory addresses of code
> representing functions.
>
>> To compare two functions in C, I would compare their machine addresses.
>>
>
> Why would you need that at all?
>
>> 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
>
>



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


More information about the Haskell-Cafe mailing list