Вот еще один вариант решения.
Ввод с клавиатуры и вывод на экран оставил на десерт.
Дальнейшая оптимизация - использовать в качестве "екселя" не список, а более подходящую структуру (массив?).

Этот ексель можно обобщить - в качестве результата использовать не конкретную монаду Error, а "обобщенную" монаду m.

import System.IO
import Monad
import Control.Monad.Error
import Control.Monad.State

-- Вычисляемое выражение:
-- либо целое число, ссылка на другую ячейку (берем ее значение),
-- либо сумма результатов двух других вычисляемых выражений
data Expr = Cons Int | Ref String | Add Expr Expr deriving Show

-- Формула - либо текстовая строка, либо вычисляемое выражение
data Formula = Str String | Expr Expr deriving Show

-- Вычесленный результат в ячейке - либо вычесленное целое число, либо строка
data Val = ValInt Int | ValStr String deriving Show

{-
Ячейка содержит:
1. Формулу (строка или вычислимое выражение) (formula)
2. Значение ячейки (res):
   а) Nothing - значение еще не было вычеслено
   б) Just Right Val - значение было вычисленно, при вычеселнии ошибок не возникло
      (результат - или строка, или целое число)
   в) Just Left String - в результате вычисления возникла ошибка
3. Признак блокировки (locked): если locked = True,
   значит ячейка "была взята" для вычесления значения в другой ячейки
   (и идет процесс вычисления значения с использованием значения этой ячейки)
-}
data Cell = Cell {formula::Formula, res::Maybe (Either String Val), locked::Bool} deriving Show

-- Ексель - это ассоциативный массив ячеек. Ключ - название ячейки
type ExelState = State [(String, Cell)]

-- Текстовое представление Екселя
showExel :: [(String, Cell)] -> String
showExel e = unlines $ map show e

-- Блокируем ячейку, возвращаем ее (если она найдена)
-- Если ячейка уже была блокирована ранее, то это
-- означает, что эта ячейка входит в цикл
-- возвратим соответствующую ошибку
-- Эта ошибка попадет в ячейку, которая непосредственно сослалась на
-- ячейку x, а так же на все "предыдущие ячейки" цикла,
-- и, в конце концов, этот результат "дойдет" до самой ячейки x.
lockCell :: String -> ExelState (Maybe Cell)
lockCell x = do
    s <- get
    let c = lookup x s
    case c of
      Just c' -> if (locked c') then return $ Just c' {res=Just $ Left "#CYCLE"}
                                else do
                                  put $ (x, c' {locked=True}) : (filter ((/= x) . fst) s)
                                  return c
      _ -> return Nothing

-- Разблокируем ячейку, при этом помещаем в нее переданное значение
-- Если указанной ячейки в екселе нет - авария
-- (если такая ситуация возникла, значит ошибка в алгоритме)
unlockCell :: String -> (Either String Val) -> ExelState ()
unlockCell x r = do
  s <- get
  let c = lookup x s
  case c of
    Just c' -> put $ (x, c' {res=Just r, locked=False}) : (filter ((/= x) . fst) s)
    _ -> error "#SYS"

-- Посчитать ячейку и выдать ее значение
-- Если ячейка уже была посчитана, то сразу возвращаем ее значение
-- Если она не была посчитана, то считаем формулу при помощи evalFormula
-- Если ячейки не оказалось - в качестве результата возвращаем Left
calculateCell :: String -> ExelState (Either String Val)
calculateCell s = do
  cell <- lockCell s
  case cell of
    Just Cell {formula=_, res=Just r} -> do {unlockCell s r; return r}
    Just Cell {formula=f, res=Nothing} -> do { val <- evalFormula f; unlockCell s val; return val}
    Nothing -> return $ Left "#REF"

-- тут все понятно
evalFormula :: Formula -> ExelState (Either String Val)
evalFormula (Str s) = return $ Right $ ValStr s
evalFormula (Expr e) = evalExpr e

-- Тоже все понятно (задействуем монаду Error)
evalExpr :: Expr -> ExelState (Either String Val)
evalExpr (Cons x) = return $ Right $ ValInt x
evalExpr (Ref s) = calculateCell s
evalExpr (Add e1 e2) = do
  r1 <- evalExpr e1
  r2 <- evalExpr e2
  case r1 of
    Right (ValInt i1) -> case r2 of
        Right (ValInt i2) -> return $ Right $ ValInt $ (i1 + i2)
        Right (ValStr _) -> return $ Left "#VAL"
        _ -> return r2
    Right (ValStr _) -> return $ Left "#VAL"
    _ -> return r1

-- Вычислить екслель - значит вычислить последовательно каждую ячейку в екселе
calculateExel :: [(String, Cell)] -> ExelState [(String, Cell)]
calculateExel cells =  do { (sequence_ $ map (calculateCell.fst) cells); get  }

main:: IO ()
main = do
        let cells = [
                 ("1", Cell {formula=Str "Head", res=Nothing, locked=False}),
                 ("2", Cell {formula=(Expr (Ref "3")), res=Nothing, locked=False}),
                 ("3", Cell {formula=(Expr (Cons 3)), res=Nothing, locked=False}),
                 ("4", Cell {formula=(Expr (Ref "44")), res=Nothing, locked=False}),
                 ("5", Cell {formula=(Expr (Ref "4")), res=Nothing, locked=False}),
                 ("6", Cell {formula=(Expr (Cons 11)), res=Nothing, locked=False}),
                 ("7", Cell {formula=(Expr (Add (Ref "3") (Ref "6"))), res=Nothing, locked=False}),
                 ("8", Cell {formula=(Expr (Add (Ref "3") (Cons 9))), res=Nothing, locked=False}),
                 ("9", Cell {formula=(Expr (Add (Ref "3") (Ref "1"))), res=Nothing, locked=False}),
                 ("10", Cell {formula=(Expr (Add (Ref "3") (Ref "4"))), res=Nothing, locked=False}),
                 ("11", Cell {formula=(Expr (Ref "12")), res=Nothing, locked=False}),
                 ("12", Cell {formula=(Expr (Ref "13")), res=Nothing, locked=False}),
                 ("13", Cell {formula=(Expr (Add (Ref "11") (Cons 5))), res=Nothing, locked=False}),
                 ("14", Cell {formula=(Expr (Add (Ref "12") (Cons 5))), res=Nothing, locked=False}),
                 ("15", Cell {formula=(Expr (Ref "1")), res=Nothing, locked=False})
                ]
        putStr $ (showExel $ snd $ (calculateExel cells) `runState` cells) ++ "\n"