@Josh
What is the point of using iterators here? If the user wants an iterator to be checked then he can throw that iterator right away because it was exhausted by the function. I think that in most cases the user wants to do some postprocessing on a hairstack after being checked. This is why I restricted the arguments to be sequences.

Keeping that restriction in mind a pure Python implementation could look like this:

def has_subsequence(seq, subseq):
    if not subseq:
        return True
    if len(subseq) > len(seq):
        return False
    start = 0
    while True:
        try:
            start = seq.index(subseq[0], start)
        except ValueError:
            # seq.index() did not match
            return False
        stop = start + len(subseq)
        if seq[stop - 1] == subseq[-1] and seq[start:stop] == subseq:
            return True
        start += 1

Unfortunately, this version potentially creates lots of subseqences for checking equality with the `subseq` argument. I tried to minimise the occurrence of those cases by pre-checking the first and the last element of a candidate. Anyway, this seems to be faster for small needles compared to your `deque`-based suggestion.