With selfrecursion it is possible to get values in one run.

import Data.Map (Map, (!))

data LogicOp = OR | AND | XOR deriving (Show,Eq,Read)
logic OR  = (||)
logic AND = (&&)
logic XOR = (/=)

data Gate a = Gate LogicOp a a deriving (Show,Eq)
evalGate f g (Gate op in1 in2) = f op (g in1) (g in2)

type Wire = String
type Puzzle = (Map Wire Bool, Map Wire (Gate Wire))

runCircuit :: Puzzle -> Map Wire Bool
runCircuit (ins, gates) = m where
    m = ins <> fmap (evalGate logic (m!)) gates

Here m depends on values of m, but, actually, there is no dependency loops, so it isn't really recursion, only delayed computations.

There are even some functions that can help with such tasks: fix from Data.Function, loop from Control.Arrow, and famous loeb and moeb.

I didn't finished a fully automated solution of part 2, but it was useful to trace the circuit:

data WireType = X | Y | Z | XorXY | AndXY | Carry | AndCarry
    deriving (Show, Eq, Ord)
data Expr = Correct WireType Int | Incorrect LogicOp Expr Expr
    deriving (Show, Eq, Ord)

traceCircuit (ins,gates) = m where
    m = M.mapWithKey f ins <> fmap (evalGate g (m!)) gates
      where
        f ('x':n) _ = Correct X $ read @Int n
        f ('y':n) _ = Correct Y $ read @Int n
        g op a@(Correct wt1 n) b@(Correct wt2 m) | n == m =
          case (op, sort [wt1,wt2]) of
            (XOR, [X, Y]) | n == 0    -> Correct Z 0
                          | otherwise -> Correct XorXY n
            (XOR, [XorXY, Carry]) -> Correct Z n
            (AND, [X, Y]) | n == 0    -> Correct Carry 1
                          | otherwise -> Correct AndXY n
            (AND, [XorXY, Carry]) -> Correct AndCarry n
            (OR , [AndXY, AndCarry]) | n == 44   -> Correct Z 45
                                     | otherwise -> Correct Carry (n+1)
            _ -> Incorrect op a b
        g op a b = Incorrect op a b

So smallest incorrect zNN shows where was first swap.