The implementation uses 2-3 finger trees annotated with sizes, as described in the paper Finger Trees: A Simple General-Purpose Data Structure, Ralf Hinze and Ross Paterson, Journal of Functional Programming 16:2 (2006) pp 197-217.
This module is intended to be imported qualified, to avoid name clashes. For example:
import Data.Sequence (Seq) import Data.Sequence as Seq
O(n). Apply a function to every element within a sequence. Note that this function is performed lazily — the actual call is almost instantaneous, regardless of the length of the sequence, because the function is not applied to all elements immediately. The eventual running time (assuming all elements are later requested) is O(n), though.