Tutorial: rest, init and membership

Procedure rest(L):
    Found = false
    Result = []
    foreach x in L:
        if Found:
            Result = Result ++ [x]
        else:
            Found = true
    return Result

Procedure init(L):
    Found = false
    Result = []
    foreach x in L:
        if Found:
            Result = Result ++ [Prev]
        else:
            Found = true
        Prev = x
    return Result

rest uses Found to skip exactly the first occurrence. init uses a one-element delay: when the second element arrives, append the remembered first; when the third arrives, append the remembered second. Update Prev AFTER appending it. The final current element is never appended, so the final position is excluded.

Both functions return [] on [] and on a singleton under the tutorial’s definitions. “L minus first(L)” is an informal description of dropping one endpoint, not a set subtraction that deletes every equal value. The functions build new result lists; the caller chooses whether to assign the result back to its working variable.

Procedure member(L, e):
    foreach x in L:
        if e == x:
            return true
    return false

A true result can return early; a false result comes after the loop. The empty list returns false with zero equality tests. Repeated values do not require repeated true results: membership asks only whether at least one occurrence exists. Parameter order is member(list,element), matching the tutorial.

The tutorial’s length and last scan the list; rest and init copy result elements. Repeatedly calling these scanning or copying helpers inside another loop can add work. A short pseudocode expression is not an automatic constant-time guarantee. At this stage, first understand the interface and result; later analyze the chosen implementation’s cost.