Une séquence fonctionnelle est une séquence avec une interface fonctionnelle, où par conséquent, les opérations d'insertion et de suppression ne doivent pas modifier la séquence, mais plutôt renvoyer une nouvelle séquence.
La façon courante d'y arriver est d'implémenter la séquence sous la forme de liste chaînée, et de copier le préfixe de la liste pour les opérations d'insertion et de suppression.