data types in haskell programming

Question

It is a haskell code to find the first duplicate element in the list. if you have 2 lists like this:L1 = {1,2,3,4} L2 = {1,2,3,1}then result for 1st would be No duplicate found and result for second should be integer 1.if one list has L3={1,2,1,3,3} answer should still be 1.

I tried doing it but stuck with the condition checking: We will use union datatype.

data Res a = DuplicateFound a | NoDuplicateFound 
              deriving (Show,Eq)

findDuplicate [] = NoDuplicateFound
findDuplicate (x:xs) = if (condition???)
      where 
      aux x [] = NoDuplicateFound
      aux x (y:ys) = if x == y then DuplicateFound x
                               else aux x ys
                     else NoDuplicateFound

I know its a pathetic code..please help me to improve it.

Except I commend this author for attempting a solution and posting it instead of just relaying his homework onto the site. +1 — luqui
– luqui, Commented Mar 27, 2011 at 4:18
I would not write the list L1 = {1,2,3,4} but L1 = [1,2,3,4]. Makes for less confusion since the square bracket is usually denoting lists and curly brackets...well do they denote anything in Haskell? In Erlang for instance they are tuples. — Magnus Kronqvist
– Magnus Kronqvist, Commented Mar 28, 2011 at 21:24

Ketil · Accepted Answer · 2011-03-29 08:40:01Z

4

The key is, as so often, recursion.

A list contains a duplicate if either:

the first element has a duplicate in the rest of the list, or
the rest of the list contains a duplicate

Add to this that an empty list contains no duplicates, and there's your program.

(I'd make hasElement just return a Bool, and use Maybe a for the return value.)

answered Mar 29, 2011 at 8:40

Ketil

1562 silver badges8 bronze badges

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

Comments

luqui · Accepted Answer · 2011-03-27 06:57:57Z

2

This code is a good start. The aux function you have already written searches to see if an element is in a list. Now you just need to check the first element against the rest of the list, and if that fails, then the second element against all elements after it, etc.

I'll just rename aux to hasElement (never underestimate the clarifying power of a good name):

hasElement x [] = NoDuplicateFound
hasElement x (y:ys) = if x == y then DuplicateFound x
                                else hasElement x ys

Then:

findDuplicate [] = NoDuplicateFound
findDuplicate (x:xs) = 
    case hasElement x xs of
        DuplicateFound dup -> ...
        NoDuplicateFound   -> ...

I will leave you to fill in the ...s. Good luck, and thank you for attempting a solution before coming here for help. It makes me more willing to put effort into my answer.

edited Mar 27, 2011 at 6:57

answered Mar 27, 2011 at 4:24

luqui

60.7k12 gold badges153 silver badges210 bronze badges

2 Comments

cuddle Over a year ago

Thanks but still i am not clear...the case x==y will check if the first element is equal to the head of the rest of the elements.but i didnt get how we can check for second element..data Res a = DuplicateFound a | NoDuplicateFound deriving (Show,Eq) aux x [] = NoDuplicateFound aux x (y:ys) = if x == y then DuplicateFound x else aux x ys findDuplicate [] = Nothing findDuplicate (x:xs) = case aux x xs of DuplicateFound x` -> "First duplicate: " ++ (show x) NoDuplicateFound -> "No duplicates"

luqui Over a year ago

@cuddle, try having findDuplicate call itself recursively. I would suggest returning a Res, this wasn't supposed to be I/O code yet.

lbolla · Accepted Answer · 2011-12-17 14:35:44Z

0

You can easily (but not very efficiently), get a list of all the duplicates using nub and (\\).

I presume this is a homework: this suggestion should give you a good starting point.

answered Dec 17, 2011 at 14:35

lbolla

5,4311 gold badge26 silver badges35 bronze badges

Collectives™ on Stack Overflow

data types in haskell programming

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related