Defining a containing function on polymorphic list
I am trying to define a containing function to see if a value is one of the elements within a list which is polymorphic, but failed with the following codes:
contain :: a -> [a] -> Bool
contain x [] = False
contain x (y:ys) = if x == y then True else contain x ys it seems that the problem is the 'operator' == does not support a polymorphic check? Any way can solve the problem? or any alternative solution to achieve the purpose? Thanks! Raeck
It’s the same Hotmail®. If by “same” you mean up to 70% faster. http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_1...
The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be. There is a nice solution for this, however, and it's very simple: contain :: Eq a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys The "Eq a" in the type signature says that 'a' must be a member of the 'Eq' typeclass. That says, in turn, that 'a' must have == defined for it. Fortunately, most types have, or can easily derive that definition. Here is the definition of the typeclass: class Eq<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Eq.html#t%3AEq>a where(==)<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Eq.html#v%3A%3D%3D>:: a -> a -> Bool<http://haskell.org/ghc/docs/latest/html/libraries/ghc-prim/GHC-Bool.html#t%3ABool> (/=)<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Eq.html#v%3A%2F%3D>:: a -> a -> Bool<http://haskell.org/ghc/docs/latest/html/libraries/ghc-prim/GHC-Bool.html#t%3ABool> That is, for 'a' to be a member of 'Eq', it must have a == operator which can take 2 values of that type and return a Boolean, saying whether or not they're equal, and it must also have a definition for the /= operator, which is "not equal". These two are also defined in terms of each other, so if you define ==, you get /= for free, and vice versa. That's probably more information than you needed to know, but I hope it helps. 2008/12/22 Raeck Zhao <raeck@msn.com>
I am trying to define a containing function to see if a value is one of the elements within a list which is polymorphic, but failed with the following codes:
contain :: a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys it seems that the problem is the 'operator' == does not support a polymorphic check? Any way can solve the problem? or any alternative solution to achieve the purpose? Thanks! Raeck
------------------------------ It's the same Hotmail(R). If by "same" you mean up to 70% faster. Get your account now.<http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_122008>
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
2008/12/22 Andrew Wagner <wagner.andrew@gmail.com>:
The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be.
There is a nice solution for this, however, and it's very simple:
contain :: Eq a -> [a] -> Bool
Please note that the syntax here should be: contain :: Eq a => a -> [a] -> Bool Denis
Yes, of course, sorry for the typo. On Mon, Dec 22, 2008 at 9:17 AM, Denis Bueno <dbueno@gmail.com> wrote:
2008/12/22 Andrew Wagner <wagner.andrew@gmail.com>:
The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be.
There is a nice solution for this, however, and it's very simple:
contain :: Eq a -> [a] -> Bool
Please note that the syntax here should be:
contain :: Eq a => a -> [a] -> Bool
Denis
On 22 Dec 2008, at 15:18, Andrew Wagner wrote:
Yes, of course, sorry for the typo.
On Mon, Dec 22, 2008 at 9:17 AM, Denis Bueno <dbueno@gmail.com> wrote: 2008/12/22 Andrew Wagner <wagner.andrew@gmail.com>:
The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be.
There is a nice solution for this, however, and it's very simple:
contain :: Eq a -> [a] -> Bool
Please note that the syntax here should be:
contain :: Eq a => a -> [a] -> Bool
Denis
Of note, unless this is an exercise, such a function already exists -- it's called elem. How do you find such a function? You search on haskell.org/hoogle. http://haskell.org/hoogle/?hoogle=Eq+a+%3D%3E+a+-%3E+%5Ba%5D+-%3E+Bool Bob
Thank you very much for your reply! It is really helpful! But I just found another 'problem', I just realize that the list does not support the user-defined data type? the list is also depending on the Eq function? For example, data Shape = Square | Triangle | Circle when I type either [Square, Triangle, Circle] or Square == Square there are errors! So there is no way to construct a truly polymorphic List? any way to extend the list to support some user-defined data type? Or... I define the Shape in a wrong way actually? Thanks Raeck Date: Mon, 22 Dec 2008 09:02:53 -0500 From: wagner.andrew@gmail.com To: raeck@msn.com Subject: Re: [Haskell-cafe] Defining a containing function on polymorphic list CC: haskell-cafe@haskell.org; beginners@haskell.org The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be. There is a nice solution for this, however, and it's very simple: contain :: Eq a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys The "Eq a" in the type signature says that 'a' must be a member of the 'Eq' typeclass. That says, in turn, that 'a' must have == defined for it. Fortunately, most types have, or can easily derive that definition. Here is the definition of the typeclass: class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool That is, for 'a' to be a member of 'Eq', it must have a == operator which can take 2 values of that type and return a Boolean, saying whether or not they're equal, and it must also have a definition for the /= operator, which is "not equal". These two are also defined in terms of each other, so if you define ==, you get /= for free, and vice versa. That's probably more information than you needed to know, but I hope it helps. 2008/12/22 Raeck Zhao <raeck@msn.com> I am trying to define a containing function to see if a value is one of the elements within a list which is polymorphic, but failed with the following codes:
contain :: a -> [a] -> Bool
contain x [] = False
contain x (y:ys) = if x == y then True else contain x ys it seems that the problem is the 'operator' == does not support a polymorphic check?
Any way can solve the problem? or any alternative solution to achieve the purpose? Thanks! Raeck It's the same Hotmail®. If by "same" you mean up to 70% faster. Get your account now. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe _________________________________________________________________ Life on your PC is safer, easier, and more enjoyable with Windows Vista®. http://clk.atdmt.com/MRT/go/127032870/direct/01/
There are two ways to fix this. Let me see if I can get my syntax right this time :) 1.) Let GHC work out the Eq instance: data Shape = Square | Triangle | Circle deriving Eq 2.) Tell GHC how to do it explicitly: data Shape = Square | Triangle | Circle instance Eq Shape where Square == Square = True Triangle == Triangle = True Circle == Circle = True _ == _ = False Note that the last line here means that any other comparisons are false. On Mon, Dec 22, 2008 at 9:35 AM, Raeck Zhao <raeck@msn.com> wrote:
Thank you very much for your reply! It is really helpful!
But I just found another 'problem', I just realize that the list does not support the user-defined data type? the list is also depending on the Eq function?
For example,
data Shape = Square | Triangle | Circle
when I type either
[Square, Triangle, Circle]
or
Square == Square
there are errors!
So there is no way to construct a truly polymorphic List? any way to extend the list to support some user-defined data type?
Or... I define the Shape in a wrong way actually?
Thanks
Raeck
------------------------------ Date: Mon, 22 Dec 2008 09:02:53 -0500 From: wagner.andrew@gmail.com To: raeck@msn.com Subject: Re: [Haskell-cafe] Defining a containing function on polymorphic list CC: haskell-cafe@haskell.org; beginners@haskell.org
The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be.
There is a nice solution for this, however, and it's very simple:
contain :: Eq a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys
The "Eq a" in the type signature says that 'a' must be a member of the 'Eq' typeclass. That says, in turn, that 'a' must have == defined for it. Fortunately, most types have, or can easily derive that definition. Here is the definition of the typeclass:
class Eq<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Eq.html#t:Eq>a where (==)<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Eq.html#v:%3D%3D>:: a -> a -> Bool<http://haskell.org/ghc/docs/latest/html/libraries/ghc-prim/GHC-Bool.html#t:Bool> (/=)<http://haskell.org/ghc/docs/latest/html/libraries/base/Data-Eq.html#v:/%3D>:: a -> a -> Bool<http://haskell.org/ghc/docs/latest/html/libraries/ghc-prim/GHC-Bool.html#t:Bool> That is, for 'a' to be a member of 'Eq', it must have a == operator which can take 2 values of that type and return a Boolean, saying whether or not they're equal, and it must also have a definition for the /= operator, which is "not equal". These two are also defined in terms of each other, so if you define ==, you get /= for free, and vice versa.
That's probably more information than you needed to know, but I hope it helps.
2008/12/22 Raeck Zhao <raeck@msn.com>
I am trying to define a containing function to see if a value is one of the elements within a list which is polymorphic, but failed with the following codes:
contain :: a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys it seems that the problem is the 'operator' == does not support a polymorphic check? Any way can solve the problem? or any alternative solution to achieve the purpose? Thanks! Raeck
------------------------------ It's the same Hotmail(R). If by "same" you mean up to 70% faster. Get your account now.<http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_broad1_122008>
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
------------------------------ Life on your PC is safer, easier, and more enjoyable with Windows Vista(R). See how <http://clk.atdmt.com/MRT/go/127032870/direct/01/>
On 22 Dec 2008, at 17:35, Raeck Zhao wrote:
But I just found another 'problem', I just realize that the list does not support the user-defined data type?
Don't worry, it does.
the list is also depending on the Eq function?
No, it doesn't.
data Shape = Square | Triangle | Circle
[Square, Triangle, Circle]
Should work fine.
or
Square == Square
Wouldn't work unless you declare your type "Shape" an instance of class "Eq" - which can be done automatically.
2008/12/22 Raeck Zhao <raeck@msn.com>
Thank you very much for your reply! It is really helpful!
But I just found another 'problem', I just realize that the list does not support the user-defined data type? the list is also depending on the Eq function?
For example,
data Shape = Square | Triangle | Circle
when I type either
[Square, Triangle, Circle]
This is perfectly legal, but GHCi won't be able to print it, because there is no Show instance for Shape. You can declare one: instance Show Shape where show Square = "Square" show Triagle = "Triangle" show Circle = "Circle" This can be generated automatically when you declare the type, by using: data Shape = Square | Triangle | Circle deriving (Show)
or
Square == Square
Similarly, to use (==), you need an Eq instance, which can be defined much in the same way as the Show instance above (deriving also works on Eq -- don't generalize too hastily; not all classes work with deriving). Luke
Andrew Wagner schrieb:
The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be.
There is a nice solution for this, however, and it's very simple:
contain :: Eq a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys
Would HLint jump in here and suggest: contain x (y:ys) = x == y || contain x ys ? Or even "replace 'contain' by 'elem'" ?
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 On Tue, Dec 23, 2008 at 10:48 PM, Henning Thielemann wrote:
Andrew Wagner schrieb:
The problem here is even slightly deeper than you might realize. For example, what if you have a list of functions. How do you compare two functions to each other to see if they're equal? There is no good way really to do it! So, not only is == not completely polymorphic, but it CAN'T be.
There is a nice solution for this, however, and it's very simple:
contain :: Eq a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys
Would HLint jump in here and suggest: contain x (y:ys) = x == y || contain x ys ? Or even "replace 'contain' by 'elem'" ?
I just tried it out. hlint makes no suggestions. Incidentally, your syntax is wrong. Should be: contain :: (Eq a) => a -> [a] -> Bool contain _ [] = False contain x (y:ys) = if x == y then True else contain x ys - -- gwern -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEAREKAAYFAklRtvAACgkQvpDo5Pfl1oKTLQCgixTp95VA8ccRxuWTpIgXVo2k +XkAniyWDU6f1sSCzdUuJIq4pAcgDS0K =Uhkz -----END PGP SIGNATURE-----
Here's a tip: leave off the type signature, and ask ghci what it is. $ ghci Prelude> let contain x [] = False ; contain x (y:ys) = if x == y then True else contain x ys Prelude> :t contain contain :: (Eq a) => a -> [a] -> Bool -- ryan 2008/12/22 Raeck Zhao <raeck@msn.com>:
I am trying to define a containing function to see if a value is one of the elements within a list which is polymorphic, but failed with the following codes:
contain :: a -> [a] -> Bool contain x [] = False contain x (y:ys) = if x == y then True else contain x ys it seems that the problem is the 'operator' == does not support a polymorphic check? Any way can solve the problem? or any alternative solution to achieve the purpose? Thanks! Raeck
________________________________ It's the same Hotmail(R). If by "same" you mean up to 70% faster. Get your account now. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hi Raeck, as I see what types you defined, don't you doing School of Expression? (In summer I made my way to FAL chapter, but I had no time more (school), but I will definitely finish that book:) Fero
participants (10)
-
Andrew Wagner -
Denis Bueno -
frantisek kocun -
Gwern Branwen -
Henning Thielemann -
Luke Palmer -
Miguel Mitrofanov -
Raeck Zhao -
Ryan Ingram -
Thomas Davie