# Defining a containing function on polymorphic list

 Classic List Threaded
13 messages
Reply | Threaded
Open this post in threaded view
|

## 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. Get your account now. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

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
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 2008/12/22 Andrew Wagner <[hidden email]>: > 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 Yes, of course, sorry for the typo.On Mon, Dec 22, 2008 at 9:17 AM, Denis Bueno wrote: 2008/12/22 Andrew Wagner <[hidden email]>: > 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 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 wrote: 2008/12/22 Andrew Wagner <[hidden email]>: > 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                              DenisOf 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+BoolBob_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## RE: Defining a containing function on polymorphic list

In reply to this post by Andrew Wagner
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: [hidden email]
To: [hidden email]
Subject: Re: [Haskell-cafe] Defining a containing function on polymorphic list
CC: [hidden email]; [hidden email]

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
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Life on your PC is safer, easier, and more enjoyable with Windows Vista®. See how
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

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 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: [hidden email]
To: [hidden email]
Subject: Re: [Haskell-cafe] Defining a containing function on polymorphic list
CC: [hidden email]; [hidden email]

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
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Life on your PC is safer, easier, and more enjoyable with Windows Vista®. See how

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 In reply to this post by raeck@msn.com 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. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 In reply to this post by raeck@msn.com 2008/12/22 Raeck Zhao 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 | Circlewhen 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 == SquareSimilarly, 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 In reply to this post by Andrew Wagner 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'" ? _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 -----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----- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 In reply to this post by raeck@msn.com 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 <[hidden email]>: > 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 > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe> > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

## Re: Defining a containing function on polymorphic list

 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 _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe