I can has(kell) moar cheezburgers?
What is the Data.Map doing there?  It looks like you were going to use it, but then changed your mind and used a list of pairs instead.

The stringMapReplace function is doing explicit recursion.  A more advanced Haskeller would recognize this pattern as some kind of fold:


-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs



In this case, the function can be tersely written as

stringMapReplace :: Dictionary -&gt; String -&gt; String
stringMapReplace = flip $ foldr $ uncurry strReplace


Intermediate steps to get there

First, recognize that your dictionary is the thing that is being iterated through.  (That is, your (m:ms) plays the role of the (x:xs) in the fold.)  In Haskell, it is usually more convenient to place the parameter that varies the most at the end.  So, rewrite your original


stringMapReplace (m:ms) s = stringMapReplace ms (strReplace (fst m) (snd m) s)



as

stringMapReplace :: Dictionary -&gt; String -&gt; String
stringMapReplace map s = stringMapReplace' s map
  where
    stringMapReplace' s [] = s
    stringMapReplace' s (m:ms) = stringMapReplace' (strReplace (fst m) (snd m) s) ms


Now, we can see that stringMapReplace' fits the pattern for foldl.  However, foldr is preferable to foldl.  If we perform the substitutions in a different order…

stringMapReplace :: Dictionary -&gt; String -&gt; String
stringMapReplace map s = stringMapReplace' s map
  where
    stringMapReplace' s [] = s
    stringMapReplace' s (m:ms) = strReplace (fst m) (snd m) (stringMapReplace' s ms)


… we can make stringMapReplace' fit the pattern for foldr.

stringMapReplace map s = stringMapReplace' s map
  where
    stringMapReplace' s map = foldr f s map
    f m = strReplace (fst m) (snd m)


Notice that in stringMapReplace' s map = foldr f s map, the s map is repeated on both sides.  We can write that in point-free style as stringMapReplace' = foldr f.

But what is f?  We can simplify it as uncurry strReplace.

stringMapReplace map s = stringMapReplace' s map
  where
    stringMapReplace' = foldr $ uncurry strReplace


What is the relationship between stringMapReplace and stringMapReplace'?  The parameters are flipped.

stringMapReplace = flip $ foldr $ uncurry strReplace


QED.