Haskell solution to BAPC 2013 Problem C

gistfile1.hs

import Control.Monad
import Data.List

type Mapping = [(Char, Char)]

derive_mapping :: String -> [String] -> Mapping
derive_mapping plain encrypted = 
	merge_mappings $ 
	filter is_consistent $ 
	map (extract_mapping plain) $
	filter (\s -> length s == length plain) encrypted

merge_mappings :: [Mapping] -> Mapping
merge_mappings [] = []
merge_mappings xs = foldr1 (intersectBy (\(ac, _) (bc, _) -> ac == bc)) xs

is_consistent :: Mapping -> Bool
is_consistent [] = True
is_consistent ((c, p) : xs) = 
	null (filter (\(nc, _) -> c == nc) xs) && 
	null (filter (\(_, np) -> p == np) xs) &&
	is_consistent xs

extract_mapping :: String -> String -> Mapping
extract_mapping p e = remove_dup_mappings $ flip zip p e

remove_dup_mappings :: Mapping -> Mapping
remove_dup_mappings [] = []
remove_dup_mappings (x : xs) = x : remove_dup_mappings (filter (x /=) xs)

decrypt :: Mapping -> String -> String
decrypt [] _ = "IMPOSSIBLE"
decrypt _ "" = ""
decrypt mapping (c : cs)  = decrypt_char mapping c : decrypt mapping cs 

decrypt_char [] _ = '?'		
decrypt_char ((c, p) : cs) e
	| c == e	= p
	| otherwise	= decrypt_char cs e

run :: IO ()
run = do
	num_encrypted <- readLn
	encrypted <- replicateM num_encrypted getLine
	decrypted <- getLine
	message <- getLine
	putStrLn $ decrypt (derive_mapping decrypted encrypted) message

main :: IO ()
main = readLn >>= \n -> replicateM_ n run