public
Created — forked from ehamberg/firstNonRep.hs

  • Download Gist
firstNonRep.hs
Haskell
1 2 3 4 5 6 7 8 9 10 11 12
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"

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.

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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.