I am very new to Haskell. I am trying to write code in Haskell that finds the first duplicate element from the list, and if it does not have the duplicate elements gives the message no duplicates. I know i can do it through nub function but i am trying to do it without it.
-
2I suggest going over the haskell documentation and making an effort to write something that works. If you get stuck and don't understand what's wrong, post a code sample with your question to show that you've put some thought into the problem.RMorrisey– RMorrisey2011-03-25 22:07:55 +00:00Commented Mar 25, 2011 at 22:07
-
Check out a list of tutorials at haskell.org/haskellwiki/Tutorials This will be a good resource to consult for learning the language.Ezra– Ezra2011-03-25 22:47:47 +00:00Commented Mar 25, 2011 at 22:47
-
1LYAH is highly recommended for starting out with Haskell. Don't let the silly drawings fool you; it's an excellent introduction to the language.Dan Burton– Dan Burton2011-03-25 23:45:14 +00:00Commented Mar 25, 2011 at 23:45
-
1Also, the next question you ask on stack overflow should have a less generic title than "haskell programming".Robin Green– Robin Green2011-03-26 09:07:13 +00:00Commented Mar 26, 2011 at 9:07
Add a comment
|
3 Answers
This is one way to do it:
import qualified Data.Set as Set
dup :: Ord a => [a] -> Maybe a
dup xs = dup' xs Set.empty
where dup' [] _ = Nothing
dup' (x:xs) s = if Set.member x s
then Just x
else dup' xs (Set.insert x s)
dupString :: (Ord a, Show a) => [a] -> [Char]
dupString x = case dup x of
Just x -> "First duplicate: " ++ (show x)
Nothing -> "No duplicates"
main :: IO ()
main = do
putStrLn $ dupString [1,2,3,4,5]
putStrLn $ dupString [1,2,1,2,3]
putStrLn $ dupString "HELLO WORLD"
Here is how it works:
*Main> main
No duplicates
First duplicate: 1
First duplicate: 'L'
7 Comments
luqui
If you must do the OP's homework for him, at least do the courtesy of explaining your process in coming up with the solution or enlightening the issue beyond the bare code (Which may as well be a foreign language to him). -1
dbyrne
@luqui If the OP has any specific questions, I'd be happy to answer them. Without feedback its hard to know where to begin my explanation. Also, when I answered this question it didn't have the homework tag.
luqui
@dbyrne, yeah I know. I added it after I saw the same question being asked by multiple other users, and obviously I don't expect you to divine in advance whether something is homework. I usually operate on the assumption that it is, especially if someone is asking me to implement something for them. Homework or not, the asker will learn more if you have them put in more effort than copying-and-pasting, and I consider SO an educational site (I realize this is not universal.) I wanted you to give a guiding hand, not a packaged product.
luqui
In particular, a comment saying "what have you tried?" to encourage the poster to put in more effort before giving them an answer is a good way to foster this. As it stands I would not consider this question worthy of an answer.
dbyrne
@luqui someone else had already posted an answer essentially saying "What have you tried? Post some code". This answer has been deleted since then. Its your subjective opinion that its not worthy of an answer. Thats fine, but it was my opinion that it was. Its pretty clear what the OP is asking, making it easy to provide a correct answer. I am a haskell beginner myself, and thought it would be good practice to try. Once I'd come up with a solution, it seemed silly not to post it.
|
This is not the your final answer, because it does unnecessary work when an element is duplicated multiple times instead of returning right away, but it illustrates how you might go about systematically running through all the possibilities (i.e. "does this element of the list have duplicates further down the list?")
dupwonub :: Eq a => [a] -> [a]
dupwonub [] = []
dupwonub (x:xs) = case [ y | y <- xs, y == x ] of
(y:ys) -> [y]
[] -> dupwonub xs
Comments
In case you are still looking into Haskell I thought you might like a faster, but more complicated, solution. This runs in O(n) (I think), but has a slightly harsher restriction on the type of your list, namely has to be of type Ix.
accumArray is an incredibly useful function, really recommend looking into it if you haven't already.
import Data.Array
data Occurances = None | First | Duplicated
deriving Eq
update :: Occurances -> a -> Occurances
update None _ = First
update First _ = Duplicated
update Duplicated _ = Duplicated
firstDup :: (Ix a) => [a] -> a
firstDup xs = fst . first ((== Duplicated).snd) $ (map g xs)
where dupChecker = accumArray update None (minimum xs,maximum xs) (zip xs (repeat ()))
g x = (x, dupChecker ! x)
first :: (a -> Bool) -> [a] -> a
first _ [] = error "No duplicates master"
first f (x:xs) = if f x
then x
else first f xs
Watch out tho, an array of size (minimum xs,maximum xs) could really blow up your space requirements.
