Skip to content

Instantly share code, notes, and snippets.

@liesen
Forked from ehamberg/firstNonRep.hs
Created August 19, 2011 14:11
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save liesen/1156886 to your computer and use it in GitHub Desktop.
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
Copy link

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
Copy link

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