from typing import Callable
from typing import Any
from typing import Sequence


def foldr(fun: Callable[[Any, Any], Any], acc: Any, seq: Sequence[Any]) -> Any:
    """Implementation of foldr in Python3.

    This is an implementation of the right-handed
    fold function from functional programming.

    If the list is empty, we return the accumulator
    value. Otherwise, we recurse by applying the
    function which was passed to the foldr to
    the head of the iterable collection
    and the foldr called with fun, acc, and
    the tail of the iterable collection.

    Below are the implementations of the len
    and sum functions using foldr to
    demonstrate how foldr function works.

    >>> foldr((lambda _, y: y + 1), 0, [0, 1, 2, 3, 4])
    5
    >>> foldr((lambda x, y: x + y), 0, [0, 1, 2, 3, 4])
    10

    foldr takes the second argument and the
    last item of the list and applies the function,
    then it takes the penultimate item from the end
    and the result, and so on.
    """
    return acc if not seq else fun(seq[0], foldr(fun, acc, seq[1:]))