Create a gist now

Instantly share code, notes, and snippets.

Embed
import qualified Data.Map as M
import Data.List (find)
import Data.Maybe (fromMaybe)
firstNonRep :: String -> Maybe Char
firstNonRep xs = let m = M.fromListWith (+) . map (\c -> (c,1)) $ xs
lookup = flip (M.findWithDefault 0) m
in find ((== 1) . lookup) xs
main = print $ case firstNonRep "faabcbcdee" of
Nothing -> "no character was found just once"
Just c -> c : " was the first character found just once"
@md2perpe

This comment has been minimized.

Show comment
Hide comment
@md2perpe

md2perpe Aug 19, 2011

Another solution (straightforward, but not very efficient for long strings):

import Data.Maybe(listToMaybe)

firstNonRep :: String -> Maybe Char
firstNonRep cs = listToMaybe $ filter nonrep cs
    where
        nonrep :: Char -> Bool
        nonrep c = count c cs == 1

        count :: Eq a => a -> [a] -> Int
        count c [] = 0
        count c (c':cs') | c == c'    = 1 + count c cs'
                         | otherwise  = count c cs'

The count function should be made tailrecursive to be a bit more efficient (at least regarding stack size). The big problem, however, is nonrep which loops through all the string to count occurrences of the character.

Another solution (straightforward, but not very efficient for long strings):

import Data.Maybe(listToMaybe)

firstNonRep :: String -> Maybe Char
firstNonRep cs = listToMaybe $ filter nonrep cs
    where
        nonrep :: Char -> Bool
        nonrep c = count c cs == 1

        count :: Eq a => a -> [a] -> Int
        count c [] = 0
        count c (c':cs') | c == c'    = 1 + count c cs'
                         | otherwise  = count c cs'

The count function should be made tailrecursive to be a bit more efficient (at least regarding stack size). The big problem, however, is nonrep which loops through all the string to count occurrences of the character.

@md2perpe

This comment has been minimized.

Show comment
Hide comment
@md2perpe

md2perpe Aug 19, 2011

A more efficient solution, using the same idea as your solution:

firstNonRep :: String -> Maybe Char
firstNonRep cs = fmap fst $ find (\(c, n) -> n == 1) $ foldl count [] cs
    where 
        count []               c             = [(c, 1)]
        count (p@(c', n) : ps) c | c == c'   = (c', n+1) : ps
                                 | otherwise = p : count ps c

A more efficient solution, using the same idea as your solution:

firstNonRep :: String -> Maybe Char
firstNonRep cs = fmap fst $ find (\(c, n) -> n == 1) $ foldl count [] cs
    where 
        count []               c             = [(c, 1)]
        count (p@(c', n) : ps) c | c == c'   = (c', n+1) : ps
                                 | otherwise = p : count ps c
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment