Programming Praxis – First Non-Repeating Character

In today’s Programming Praxis exercise, our goal is to find the first character in a string that does not occur anywhere else in the string. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.Map as M

To find the first non-repeated element, we mark each element as unique and insert them into a map. When a duplicate element is found, we remove its unique status. Afterwards, we search the list for the first unique element.

firstUnique :: Ord a => [a] -> Maybe a
firstUnique xs = find (M.fromListWith (\_ _ -> False)
                           (zip xs $ repeat True) M.!) xs

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ firstUnique "aabcbcdeef"   == Just 'd'
          print $ firstUnique "aabcbcfeed"   == Just 'f'
          print $ firstUnique "aabcbcdeefdf" == Nothing
About these ads

Tags: , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: