Re: [Haskell-cafe] General function to count list elements?
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@gmail.com> wrote: From: Eugene Kirpichov <ekirpichov@gmail.com> Subject: Re: [Haskell-cafe] General function to count list elements? To: "michael rice" <nowgate@yahoo.com> 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 <nowgate@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@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
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@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@gmail.com> wrote:
From: Eugene Kirpichov <ekirpichov@gmail.com> Subject: Re: [Haskell-cafe] General function to count list elements? To: "michael rice" <nowgate@yahoo.com> 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 <nowgate@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@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
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@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@gmail.com> wrote:
From: Eugene Kirpichov <ekirpichov@gmail.com> Subject: Re: [Haskell-cafe] General function to count list elements? To: "michael rice" <nowgate@yahoo.com> 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 <nowgate@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@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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@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@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@gmail.com> wrote:
From: Eugene Kirpichov <ekirpichov@gmail.com> Subject: Re: [Haskell-cafe] General function to count list elements? To: "michael rice" <nowgate@yahoo.com> 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 <nowgate@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@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Eugene Kirpichov Web IR developer, market.yandex.ru
Sometimes I do miss the pragmatic C solution:- two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;) - two function pointers that are different, might or might not represent that same functions. But this weak equality can sometimes be handy. For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess... On Sat, Apr 18, 2009 at 6:02 PM, John A. De Goes <john@n-brain.net> wrote:
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.
Peter Verswyvelen <bugfact@gmail.com> wrote:
Sometimes I do miss the pragmatic C solution:- two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;)
In haskell, they would, but C doesn't give you the same guarantee: int evil = 0; int wicked( int i_dare_you ) { return i_dare_you + (++evil); } Clearly, wicked and wicked are the same function, but they surely aren't indistinguishable, at least if you happen to call them. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.
And when the need gets big enough you pull out StablePtr and use that. :) On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen <bugfact@gmail.com> wrote:
Sometimes I do miss the pragmatic C solution: - two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;) - two function pointers that are different, might or might not represent that same functions. But this weak equality can sometimes be handy. For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess... On Sat, Apr 18, 2009 at 6:02 PM, John A. De Goes <john@n-brain.net> wrote:
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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Or a StableName? I guess StablePtr prevents the GC to move the Haskell object, so for just doing ugly comparing StableName would be better? On Mon, Apr 20, 2009 at 12:45 AM, Lennart Augustsson <lennart@augustsson.net
wrote:
And when the need gets big enough you pull out StablePtr and use that. :)
On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen <bugfact@gmail.com> wrote:
Sometimes I do miss the pragmatic C solution: - two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;) - two function pointers that are different, might or might not represent that same functions. But this weak equality can sometimes be handy. For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess... On Sat, Apr 18, 2009 at 6:02 PM, John A. De Goes <john@n-brain.net> wrote:
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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Sorry, I meant StableName. On Mon, Apr 20, 2009 at 1:00 AM, Peter Verswyvelen <bugfact@gmail.com> wrote:
Or a StableName? I guess StablePtr prevents the GC to move the Haskell object, so for just doing ugly comparing StableName would be better?
On Mon, Apr 20, 2009 at 12:45 AM, Lennart Augustsson <lennart@augustsson.net> wrote:
And when the need gets big enough you pull out StablePtr and use that. :)
On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen <bugfact@gmail.com> wrote:
Sometimes I do miss the pragmatic C solution: - two function pointers that are equal surely represent the same functions (although in C nothing is really sure ;) - two function pointers that are different, might or might not represent that same functions. But this weak equality can sometimes be handy. For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess... On Sat, Apr 18, 2009 at 6:02 PM, John A. De Goes <john@n-brain.net> wrote:
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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Lennart Augustsson <lennart@augustsson.net> wrote:
On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen <bugfact@gmail.com> wrote:
For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess...
And when the need gets big enough you pull out StablePtr and use that. :)
Waaagh! Don't give him ideas, he's going to do it... Make yourself an enum, generate your list, nub it, then transform it to a list of functions. Always do everything with the least information sanely feasible, and a function is more information than a value, even if you can't get at it, anymore. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.
A solution with enums would severely suffer from the expression problem... One would need to extent the enums every time one needs to support a new function. Maybe could be solved with type classes, don't know. On Mon, Apr 20, 2009 at 3:57 PM, Achim Schneider <barsoap@web.de> wrote:
Lennart Augustsson <lennart@augustsson.net> wrote:
On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen <bugfact@gmail.com> wrote:
For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess...
And when the need gets big enough you pull out StablePtr and use that. :)
Waaagh! Don't give him ideas, he's going to do it... Make yourself an enum, generate your list, nub it, then transform it to a list of functions. Always do everything with the least information sanely feasible, and a function is more information than a value, even if you can't get at it, anymore.
-- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or quoting of this signature prohibited.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Mon, Apr 20, 2009 at 7:57 AM, Achim Schneider <barsoap@web.de> wrote:
Lennart Augustsson <lennart@augustsson.net> wrote:
On Sun, Apr 19, 2009 at 10:43 PM, Peter Verswyvelen <bugfact@gmail.com> wrote:
For example, suppose you have a predicate a -> Bool, and a list of these predicates [a -> Bool], but you want to remove all functions that are obviously equal in the C way from the list for optimization... Okay big hack, and one could do this already with reallyUnsafePtrEquality# I guess...
And when the need gets big enough you pull out StablePtr and use that. :)
Waaagh! Don't give him ideas, he's going to do it...
Nah, I don't think so. I think, even after all this mess, we've been relatively clear that Eq is how you do it. Luke
participants (7)
-
Achim Schneider -
Eugene Kirpichov -
John A. De Goes -
Lennart Augustsson -
Luke Palmer -
michael rice -
Peter Verswyvelen