The use of spec or code environments in subfigures breaks labeling.

Subfloats.lhs

\documentclass{article}
\usepackage{subcaption}
%include polycode.fmt

%if False
\begin{code}
module Main where
\end{code}
%endif
\begin{document}
  
  The following example works, it has correct labels:
  
  \begin{figure}[ht]
    \centering

    \begin{subfigure}[b]{.45\textwidth}
      a
      \caption{Non-incremental computation}
      \label{1code:insert-item-inlist-non-incremental}
    \end{subfigure}
    \begin{subfigure}[b]{.45\textwidth}
      b
      \caption{Incrementalized computation}
      \label{2code:insert-item-inlist-incremental}
    \end{subfigure}
    \caption{Inserting an item in a list}\label{3code:inserting-item-in-list}
  \end{figure}
  
  However, using a \emph{spec} or \emph{code} environment breaks the labeling:

    \begin{figure}[ht]
      \centering

      \begin{subfigure}[b]{.45\textwidth}
        \begin{spec}
g =  let  xs   = [1..5]
          ys   = map (*2) xs
          xs'  = insert 3 10 xs
          ys'  = map (*2) xs'
     in   ys'
        \end{spec}
        \caption{Non-incremental computation}
        \label{code:insert-item-inlist-non-incremental}
      \end{subfigure}
      \begin{subfigure}[b]{.45\textwidth}
        \begin{spec}
g' =  let  xs   = [1..5]
           ys   = map (*2) xs
           xs'  = insert 3 10 xs
           ys'  = insert 3 (10*2) ys
      in   ys'
        \end{spec}
        \caption{Incrementalized computation}
        \label{code:insert-item-inlist-incremental}
      \end{subfigure}
      \caption{Inserting an item in a list}\label{code:inserting-item-in-list}
    \end{figure}
    


\end{document}

Interesting. I can reproduce the problem. Investigating ...