def append(list1, list2):
    return (list2 if is_none(list1)
            else pair(head(list1), append(tail(list1), list2)))
def map(fun, items):
    return (None if is_none(items)
            else pair(fun(head(items)),
                      map(fun, tail(items))))
def length(items):
    return (0 if is_none(items)
            else 1 + length(tail(items)))
def subsets(s):
    if is_none(s):
        return llist(None)
    else:
        rest = subsets(tail(s))
        return append(rest, map(lambda x: pair(head(s), x), rest))

print(length(subsets(llist(1, 2))))

# expected: 4
