Defining a containing function on polymorphic list

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Defining a containing function on polymorphic list

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
[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

Andrew Wagner
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 <[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®. 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

Denis Bueno
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

Andrew Wagner
Yes, of course, sorry for the typo.

On Mon, Dec 22, 2008 at 9:17 AM, Denis Bueno <[hidden email]> 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

Thomas Davie

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 <[hidden email]> 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

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.


Bob

_______________________________________________
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

raeck@msn.com
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 <[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®. 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

Andrew Wagner
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 <[hidden email]> 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 <[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®. 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

MigMit
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

Luke Palmer-2
In reply to this post by raeck@msn.com
2008/12/22 Raeck Zhao <[hidden email]>
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

_______________________________________________
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

Henning Thielemann-4
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

Gwern Branwen
-----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

Ryan Ingram
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

frantisek kocun
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