Cleveref and Algorithm2e: typesetting procedure name

Question

I am making use of the procedure environment of algorithm2e, but I am unable to get it to work with cleveref. I would like to have a different reference for procedures and algorithms, but they seem to be always treated in the same way. I thought it depended on the counter used, so I tried this approach by egreg, but the only outcome was on the counter.

If I do not add the procnumbered option to algorithm2e, \Cref outputs "Algorithm -".
I could customize the format with \crefformat to something like Procedure \ref{proclabel}, but in the first place cleveref cannot distinguish a procedure from an algorithm, and secondarily I cannot understand what I should override (\labelcrefformat? The documentation does not go into much detail).

If I add procnumbered, at least I get a number but then the reference name is always "Algorithm".

What's the best way to get either "Procedure N" in the procnumbered case, or "Procedure ProcName"?

I looked at this answer which suggests to create a new float but I'm not convinced it's necessary to go that far, and this answer which seems to work with hyperref directly, but I'm a bit wary of touching hyperref in this case. There is this other answer which also recommends a new float but it's for algorithmicx.

\documentclass{article}
\usepackage[ruled,procnumbered]{algorithm2e}
\usepackage{cleveref}

\newcounter{procedure}
\makeatletter
% https://tex.stackexchange.com/a/212030/26355
\AtBeginEnvironment{procedure}{\let\c@algocf\c@procedure}
\makeatother
\crefname{proccf}{proc.}{procs.}
\Crefname{proccf}{Procedure}{Procedures}

\begin{document}
  \begin{algorithm}
    \caption{My algorithm.}
    \label{algo:my_algo}
    Call \Cref{proc:my_proc}\;
  \end{algorithm}

  \begin{procedure}
    \caption{MyProc()}
    \label{proc:my_proc}
    \Return{$\emptyset$}\;
  \end{procedure}

  \Cref{algo:my_algo} calls \Cref{proc:my_proc}.
\end{document}

Answer 1

You can do \crefalias besides changing the counter.

\documentclass{article}
\usepackage[ruled,procnumbered]{algorithm2e}
\usepackage{cleveref}

\newcounter{procedure}
\makeatletter
% https://tex.stackexchange.com/a/212030/26355
\AtBeginEnvironment{procedure}{\let\c@algocf\c@procedure\crefalias{algocf}{procedure}}
\makeatother
\crefname{procedure}{proc.}{procs.}
\Crefname{procedure}{Procedure}{Procedures}

\begin{document}
  \begin{algorithm}
    \caption{My algorithm.}
    \label{algo:my_algo}
    Call \Cref{proc:my_proc}\;
  \end{algorithm}

  \begin{procedure}
    \caption{MyProc()}
    \label{proc:my_proc}
    \Return{$\emptyset$}\;
  \end{procedure}

  \Cref{algo:my_algo} calls \Cref{proc:my_proc}.
\end{document}