#!/usr/bin/env python3

from collections import namedtuple

Nil = namedtuple('Nil', ())
Cons = namedtuple('Cons', ('car', 'cdr'))


def null(lst):
    return Nil() == lst


def fromseq(seq):
    if not seq:
        return Nil()
    return Cons(seq[0], fromseq(seq[1:]))


def head(lst):
    if null(lst):
        raise AttributeError()
    h, _ = lst
    return h


def tail(lst):
    if null(lst):
        raise AttributeError()
    _, t = lst
    return t


def foldr(func, acc, lst):
    if null(lst):
        return acc
    return foldr(func, func(head(lst), acc), tail(lst))


def foldl(func, acc, lst):
    if null(lst):
        return acc
    return foldl(func, func(acc, head(lst)), tail(lst))


def length(lst):
    if null(lst):
        return 0
    return 1 + length(tail(lst))


def tolist(lst):
    if null(lst):
        return []

    return [head(lst)] + tolist(tail(lst))


def map_(func, lst):
    if null(lst):
        return Nil()
    return Cons(func(head(lst)), map_(func, tail(lst)))


def append(lst1, lst2):
    if null(lst1):
        return lst2
    return Cons(head(lst1), append(tail(lst1), lst2))


def filter_(pred, lst):
    if null(lst):
        return Nil()

    if pred(head(lst)):
        return Cons(head(lst), filter_(pred, tail(lst)))
    else:
        return filter_(pred, tail(lst))


def reverse(lst):
    if null(lst):
        return Nil()
    return append(reverse(tail(lst)), Cons(head(lst), Nil()))


def elem(value, lst):
    if null(lst):
        return False
    if head(lst) == value:
        return True
    return elem(value, tail(lst))


if __name__ == '__main__':
    pass