Skip to content

Instantly share code, notes, and snippets.

# liesen/firstNonRep.hs forked from ehamberg/firstNonRep.hs Created Aug 19, 2011

 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 commented 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.

### md2perpe commented 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 ``````
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.