Tests whether two strings are anagrams in O(n) time.

anagram.hs

import Data.Map (Map)
import qualified Data.Map as Map
import Data.Foldable

isAnagram :: [Char] -> [Char] -> Bool
isAnagram xs ys = f xs ys Map.empty 
  where
    f :: [Char] -> [Char] -> Map Char Int -> Bool

    f (x:xs) ys m = if x `Map.member` m 
                      then f xs ys (Map.update (Just . (+1)) x m)
                      else f xs ys (Map.insert x 1 m)

    f [] (y:ys) m = if y `Map.member` m
                       then f [] ys (Map.update (Just . (+(-1))) y m)
                       else False

    f [] [] m = foldMap (All . (== 0)) m