I was very much unhappy because my previous implementation took 1 second to execute and trashed through 2GB RAM in the process of doing so, I sat down again with some inspiration about the sorting approach.
I am very much happy now, the profiler tells me that most of time is spend in the parsing functions now.

I am also grateful for everyone else doing haskell, this way I learned about Arrays, Bifunctors and Arrows which (I think) improved my code a lot.

Haskell

import Control.Arrow hiding (first, second)

import Data.Map (Map)
import Data.Set (Set)
import Data.Bifunctor

import qualified Data.Maybe as Maybe
import qualified Data.List as List
import qualified Data.Map as Map
import qualified Data.Set as Set
import qualified Data.Ord as Ord


parseRule :: String -> (Int, Int)
parseRule s = (read . take 2 &&& read . drop 3) s

replace t r c = if t == c then r else c

parse :: String -> (Map Int (Set Int), [[Int]])
parse s = (map parseRule >>> buildRuleMap $ rules, map (map read . words) updates)
        where
                rules = takeWhile (/= "") . lines $ s
                updates = init . map (map (replace ',' ' ')) . drop 1 . dropWhile (/= "") . lines $ s

middleElement :: [a] -> a
middleElement us = (us !!) $ (length us `div` 2)

ruleGroup :: Eq a => (a, b) -> (a, b') -> Bool
ruleGroup = curry (uncurry (==) <<< fst *** fst)

buildRuleMap :: [(Int, Int)] -> Map Int (Set Int)
buildRuleMap rs = List.sortOn fst
        >>> List.groupBy ruleGroup 
        >>> map ((fst . head) &&& map snd) 
        >>> map (second Set.fromList) 
        >>> Map.fromList 
        $ rs

elementSort :: Map Int (Set Int) -> Int -> Int -> Ordering 
elementSort rs a b
        | Maybe.maybe False (Set.member b) (rs Map.!? a) = LT
        | Maybe.maybe False (Set.member a) (rs Map.!? b) = GT
        | otherwise = EQ

isOrdered rs u = (List.sortBy (elementSort rs) u) == u

part1 (rs, us) = filter (isOrdered rs)
        >>> map middleElement
        >>> sum
        $ us
part2 (rs, us) = filter (isOrdered rs >>> not)
        >>> map (List.sortBy (elementSort rs))
        >>> map middleElement
        >>> sum
        $ us

main = getContents >>= print . (part1 &&& part2) . parse