def filter(predicate, sequence):
    return (None if is_none(sequence)
            else pair(head(sequence),
                      filter(predicate, tail(sequence)))
            if predicate(head(sequence))
            else filter(predicate, tail(sequence)))
def remove(item, sequence):
    return filter(lambda x: x != item,
                  sequence)
def map(fun, items):
    return (None if is_none(items)
            else pair(fun(head(items)),
                      map(fun, tail(items))))
def append(list1, list2):
    return (list2 if is_none(list1)
            else pair(head(list1), append(tail(list1), list2)))
def accumulate(op, initial, sequence):
    return (initial if is_none(sequence)
            else op(head(sequence),
                    accumulate(op, initial, tail(sequence))))
def flatmap(f, seq):
    return accumulate(append, None, map(f, seq))
def length(items):
    return (0 if is_none(items)
            else 1 + length(tail(items)))
def permutations(s):
    return (llist(None)       # sequence containing empty set
            if is_none(s)     # empty set?
            else flatmap(lambda x: map(lambda p: pair(x, p),
                                       permutations(remove(x, s))),
                         s))

print(length(permutations(llist(1, 2, 3))))

# expected: 6
