Type signature question

newer
Why does this list comprehension...

older
Syntactic sugar to insert into a...

Louis-Guillaume Gagnon

23 Jul 2013 23 Jul '13

10:33 a.m.

Hello beginners, I'm working on the second set of exercises in ch.03 of Real World Haskell I wrote a palindromize function (:: [a] -> [a]) which transforms a list in a palindrome (eg. [1,2,3] -> [1,2,3,3,2,1]) . I wrote a isPalindrome function which checks whether a given list is such a palindrome. it reads: isPalindrome xs | odd (length xs) = False | firstHalf == secondHalf =True | otherwise = False where half = div (length xs) 2 firstHalf = take half xs secondHalf = reverse (drop half xs) I would expect the type signature to be: isPalindrome :: [a] -> Bool but ghci gives me is Eq a => [a] -> Bool and I don't undestand why the "Eq a =>" shows up. many thanks, glg

Show replies by date

Matthew Lefavor

23 Jul 23 Jul

10:44 a.m.

On Tue, Jul 23, 2013 at 10:33 AM, Louis-Guillaume Gagnon < louis.guillaume.gagnon@gmail.com> wrote:

...

isPalindrome xs | odd (length xs) = False | firstHalf == secondHalf =True | otherwise = False where half = div (length xs) 2 firstHalf = take half xs secondHalf = reverse (drop half xs)

I would expect the type signature to be: isPalindrome :: [a] -> Bool

but ghci gives me is Eq a => [a] -> Bool

and I don't undestand why the "Eq a =>" shows up

"Eq a" is the "Type class" of "a". It means that "a" is a type that supports the checking of equality. Other type classes include: "Show" (types that are printable), and "Ord" (types that are orderable). Cheers, MCL

Brandon Allbery

10:46 a.m.

On Tue, Jul 23, 2013 at 10:33 AM, Louis-Guillaume Gagnon < louis.guillaume.gagnon@gmail.com> wrote:

...

I wrote a isPalindrome function which checks whether a given list is such a palindrome. it reads: isPalindrome xs | odd (length xs) = False | firstHalf == secondHalf =True | otherwise = False where half = div (length xs) 2 firstHalf = take half xs secondHalf = reverse (drop half xs)

I would expect the type signature to be: isPalindrome :: [a] -> Bool

but ghci gives me is Eq a => [a] -> Bool

and I don't undestand why the "Eq a =>" shows up.

It shows up because of `firstHalf == secondHalf`; you used (==), this requires an Eq constraint so that the type-appropriate implementation of (==) is available. -- brandon s allbery kf8nh sine nomine associates allbery.b@gmail.com ballbery@sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net

Denis Kasak

10:48 a.m.

On 23 July 2013 16:33, Louis-Guillaume Gagnon wrote:

...

and I don't undestand why the "Eq a =>" shows up.

Prelude> :type (==) (==) :: Eq a => a -> a -> Bool The (==) operator is a member of the typeclass Eq. This enables many different types to use the (==) operator by implementing their own instance of Eq (i.e. their own version of the (==) function). Since you're using the (==) operator in your code, the only types that can typecheck are those that have an instance of the Eq typeclass. ghci detects this and automatically adds the "Eq a =>" which is called a /class constraint/. It restricts the type variable 'a' to only those types that have an Eq instance defined. -- Denis Kasak

Gesh hseG

11:05 a.m.

On Tue, Jul 23, 2013 at 5:48 PM, Denis Kasak wrote:

...

On 23 July 2013 16:33, Louis-Guillaume Gagnon wrote:

...
and I don't undestand why the "Eq a =>" shows up.

The inference works somewhat like this: GHC sees the definitions of firstHalf, secondHalf and infers they have the same type as xs, and that all three of them must be some lists for them to be passed to and be returned by take and drop. GHC sees firstHalf == secondHalf. Since (==) has type Eq a => a -> a -> Bool, firstHalf (and secondHalf and xs) must have types which are instances of the typeclass Eq. Looking at the instance declarations for Eq, we find that for all types t which are instances of Eq, the type [t] (lists of values of type t) is also an instance of Eq. In other words, instance Eq a => Eq [a] where ... Thus, we have that firstHalf, secondHalf, xs :: Eq t => [t] and cannot infer a more specific type for these three names, leaving us with the signature Eq t => [t] -> Bool for isPalindrome. Intuitively, since you're checking whether the first half of the list is equal to the second half, you need to be able to check that the first element is equal to the last, second to the before-last, etc. Also, notice that you could just have written isPalindrome xs = xs == reverse xs or even isPalindrome = (==) <$> id <*> reverse but this last way is too obfuscated for most sane people. HTH, Gesh

Louis-Guillaume Gagnon

11:21 a.m.

2013/7/23 Gesh hseG :

...

The inference works somewhat like this: GHC sees the definitions of firstHalf, secondHalf and infers they have the same type as xs, and that all three of them must be some lists for them to be passed to and be returned by take and drop. GHC sees firstHalf == secondHalf. Since (==) has type Eq a => a -> a -> Bool, firstHalf (and secondHalf and xs) must have types which are instances of the typeclass Eq. Looking at the instance declarations for Eq, we find that for all types t which are instances of Eq, the type [t] (lists of values of type t) is also an instance of Eq. In other words, instance Eq a => Eq [a] where ...

Thus, we have that firstHalf, secondHalf, xs :: Eq t => [t] and cannot infer a more specific type for these three names, leaving us with the signature Eq t => [t] -> Bool for isPalindrome.

Intuitively, since you're checking whether the first half of the list is equal to the second half, you need to be able to check that the first element is equal to the last, second to the before-last, etc.

great post, thanks!

...

Also, notice that you could just have written isPalindrome xs = xs == reverse xs

Why didn't I think of that!? glg

Chaddaï Fouché

1:48 p.m.

Le 23 juil. 2013 17:23, "Louis-Guillaume Gagnon" < louis.guillaume.gagnon@gmail.com> a écrit :

...

...
Also, notice that you could just have written isPalindrome xs = xs == reverse xs

Why didn't I think of that

Probably because your internal definition of palindromes is slightly wrong : note that your function doesn't do the same thing as this one, more precisely it refuse any palindrome of odd length like [1, 2, 3, 2, 1]. Of course you may have your own definition that makes even length a requirement. -- Jedaï

Anindya Mozumdar

10:55 a.m.

...

...
but ghci gives me is Eq a => [a] -> Bool

and I don't undestand why the "Eq a =>" shows up.

You are doing the comparison firstHalf == secondHalf. Two lists are equal only if each element in the same position in the list are equal (and the lists are of equal length). Thus, you require that the elements of the list can be compared for equality. A type can be tested for equality only if it belongs to the Eq typeclass. Thus, automatic type inference in Haskell is putting this class constraint. Regards, Anindya

Erik Price

10:57 a.m.

It's saying that you can't pass parameters to this function unless they are of the Eq type class, because somewhere in the body of the function is code that expects parameters to be of this type class. e On Tue, Jul 23, 2013 at 10:33 AM, Louis-Guillaume Gagnon < louis.guillaume.gagnon@gmail.com> wrote:

...

Hello beginners,

I'm working on the second set of exercises in ch.03 of Real World Haskell

I wrote a palindromize function (:: [a] -> [a]) which transforms a list in a palindrome (eg. [1,2,3] -> [1,2,3,3,2,1]) .

I wrote a isPalindrome function which checks whether a given list is such a palindrome. it reads: isPalindrome xs | odd (length xs) = False | firstHalf == secondHalf =True | otherwise = False where half = div (length xs) 2 firstHalf = take half xs secondHalf = reverse (drop half xs)

I would expect the type signature to be: isPalindrome :: [a] -> Bool

but ghci gives me is Eq a => [a] -> Bool

and I don't undestand why the "Eq a =>" shows up.

many thanks,

glg

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Erik Price

10:59 a.m.

My reply is a bit ambiguous, so to clarify: the parameter doesn't have to be of the Eq type class, because the parameter is a list. But the list's elements have to be of the Eq type class. e On Tue, Jul 23, 2013 at 10:57 AM, Erik Price wrote:

...

It's saying that you can't pass parameters to this function unless they are of the Eq type class, because somewhere in the body of the function is code that expects parameters to be of this type class.

e

On Tue, Jul 23, 2013 at 10:33 AM, Louis-Guillaume Gagnon < louis.guillaume.gagnon@gmail.com> wrote:

...
Hello beginners,

I'm working on the second set of exercises in ch.03 of Real World Haskell

I wrote a palindromize function (:: [a] -> [a]) which transforms a list in a palindrome (eg. [1,2,3] -> [1,2,3,3,2,1]) .

I wrote a isPalindrome function which checks whether a given list is such a palindrome. it reads: isPalindrome xs | odd (length xs) = False | firstHalf == secondHalf =True | otherwise = False where half = div (length xs) 2 firstHalf = take half xs secondHalf = reverse (drop half xs)

I would expect the type signature to be: isPalindrome :: [a] -> Bool

but ghci gives me is Eq a => [a] -> Bool

and I don't undestand why the "Eq a =>" shows up.

many thanks,

glg

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

4318

Age (days ago)

4318

Last active (days ago)

List overview

Download

9 comments

8 participants

participants (8)

Anindya Mozumdar
Brandon Allbery
Chaddaï Fouché
Denis Kasak
Erik Price
Gesh hseG
Louis-Guillaume Gagnon
Matthew Lefavor