Rewriting logic, and its implementation in the rewriting engine Maude, provides a flexible semantic and logical framework that has been extensively used for the analysis of a wide range of systems, from programming languages to cyber-physical systems. Although pure type systems have been specified in rewriting logic as object logics, and state monads have been shown to be definable in Maude, there is still no full implementation in Maude of higher-order functions that is sufficiently flexible for general users. In this paper, we show how higher-order programming can be made available in Maude through a natural and declarative encoding of higher-order iterators and lambda functions. We present two alternative approaches to achieve this goal, and compare them in terms of expressiveness and efficiency. Our ultimate objective is to give Maude specifiers not only the possibility of writing higher-order functions directly in Maude, but also the infrastructure needed to simplify the specification of rewrite-theory transformations. Such transformations are a common task in verification tasks using Maude and they could substantially benefit from the modules proposed in this paper.