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

18 Apr 2009

      2009/4/18 michael rice :
...
...
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  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, 12:39 PM
2009/4/18 michael rice :
...
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@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  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: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 :
...
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
--
Eugene Kirpichov
Web IR developer, market.yandex.ru
-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru