Haskell Data Type Instance as operator

Question

I have recieved a exercice to learn about data types in haskell and I can't figure out how to solve this one.

They got me a data like : data CatLista a = Nil | Unit a| Conc (CatLista a) (CatLista a) deriving Eq and I need to make the data types become: Nil -> [] , Unit x -> [x] , Conc -> same operator as (++)

So if you run Conc (Unit 9)(Conc (Unit 5) (Unit 3)) == Conc (Conc (Unit 9) (Unit 5))(Conc (Unit 3) Nil) should give true and Conc (Unit 9)(Unit 3) == Conc (Unit 3) (Unit 9) should give false.

I already tried instancing the show class like this:

instance Show a => Show (CatLista a) where
    show a = case a of
        Nil -> []
        Unit x -> "[" ++ show x ++ "]"
        Conc Nil dos -> show dos
        Conc uno Nil -> show uno 
        Conc uno dos -> "[" + show uno ++ "," ++ show dos ++ "]"

I'm quite new to haskell so I may not know some basics, because I can't understand why if I run it (beeing Conc uno dos -> show uno ++ show dos) with the same command as bellow Conc (Unit 9)(Conc (Unit 5) (Unit 3)) == Conc (Conc (Unit 9) (Unit 5))(Conc (Unit 3) Nil) it still returns False even tough they both return the same [9][5][3] with my show instance.

EDIT

Thanks to you I made it, it know returns correctly the values like intended with this code:

toLista :: Eq a => CatLista a -> [a]
toLista Nil = []
toLista (Unit x) = [x]
toLista (Conc a b) 
                    | a == Nil = toLista b 
                    | b == Nil = toLista a
                    | otherwise = (++) (toLista a) (toLista b)

instance (Show a,(Eq a)) => Show (CatLista a) where 
    show a= show (toLista a)

But still I dont know why if I try the same comparation it still returns False, even tough I get returned the same [9,5,3].

This is probably due to my lack of knowledge in Haskell, sorry about that.

Two lists having the same string presentation does not mean the two objects are equivalent. You will need to define your own instance of Eq for the CatLista. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Dec 8, 2021 at 17:42
Define toList :: CatLista a -> [a] first, then the Show instance is a trivial composition of toList and show for lists. — chepner
– chepner, Commented Dec 8, 2021 at 18:25
Your definition assumes that the string representation of a Conc value is the concatenation of the string representations of the two halves, rather than just the elements of the two halves. — chepner
– chepner, Commented Dec 8, 2021 at 18:28

pedrofurla · Accepted Answer · 2021-12-08 20:49:31Z

4

Two values are not equivalent if these produce the same String when calling show on these. The (==) :: Eq a => a -> a -> Bool function is implemented by the Eq typeclass. You thus need to implement the instance of Eq for your CatLista yourself.

The default implementation for Eq, if you use deriving Eq is that two values are the same if they have the same data constructor, and the parameters are elementwise equivalent by calling (==) on these.

You thus can implement the instance for Eq yourself with:

data CatLista a = Nil | Unit a| Conc (CatLista a) (CatLista a) -- ← no deriving Eq

instance Eq a => Eq (CatLista a) where
    ca == cb = toLista ca == toLista cb

edited Dec 8, 2021 at 20:49

pedrofurla

12.8k1 gold badge41 silver badges49 bronze badges

answered Dec 8, 2021 at 19:29

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ander Carrera Over a year ago

Thank you for the answer. One little question about your answer with you could help me: When you do ca == cb = toLista ca == toLista cb you are meaning that, two random CatLista (ca and cb) are equal when their representation are equal (toLista ca == toLista cb) ? Thanks again

willeM_ Van Onsem Over a year ago

@AnderCarrera: toLista ca converts a CataLista to a list, so the two are equivalent if these are equivalent as list. This function thus not says that two CataListas are equivalent if they have the same show, although since you both define it in terms of toLista that will be the case here.

Ben · Accepted Answer · 2021-12-08 21:08:34Z

Because you include deriving Eq in the data declaration, you're telling the compiler to generate a default equality method. The compiler cannot read your mind and know that you intend to represent lists via concatenation of sublists.

You know you intend Conc [1, 2] [3] to represent the same list as Conc [1] [2, 3]¹; either should be regarded as representing [1, 2, 3]. The compiler does not know this. The generated equality method sees that in one case we have [1, 2] in the first field of the Conc constructor, and in the other case we have [1]. Those two things aren't equal, so the default equality method says that the whole structure is not equal either.

To avoid that, stop messing around with the Show instance. Show is for converting a CatList to a String of code that would build it. It has nothing to do with testing equality. There's no possible way you can change the outcome of == by defining a Show instance.

You need to remove deriving Eq from the data declaration. That will mean the compiler doesn't generate a default equality method, so you can write your own one that does something different (compares whether two CatLists represent the same list rather than comparing whether they have the same structure).

¹ I am abusing notation here to write the sublists using bracket syntax; this is not valid code, I'm just trying to make the difference in sub-structure more easily visible.

Collectives™ on Stack Overflow

Haskell Data Type Instance as operator

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related