kispython_2.1-2.15

# Создайте тип данных односвязный список с помощью ФВП. При создании списка нельзя использовать классы, готовые списки, кортежи и так далее.


# 2.1. (уровень сложности: высокий)
# Создайте функцию pair(head, tail), которая порождает элемент списка.
# Не используйте ветвления. Создайте также функции head(lst) (возвращает значение головы списка) и tail(lst) (возвращает хвост списка).
def pair(head, tail):
    """Создает элемент списка."""
    return (lambda h: lambda t: lambda f: f(h)(t))(head)(tail)

def head(lst):
    """Возвращает значение головы списка."""
    return lst(lambda h: lambda t: h)

def tail(lst):
    """Возвращает хвост списка."""
    return lst(lambda h: lambda t: t)

# 2.2. (уровень сложности: средний)
# Создайте функцию make_list(*args), которая создает список на основе аргументов.
def make_list(*args):
    """Создает список на основе переданных аргументов."""
    if not args:
        return None
    head, *tail = args
    return pair(head, make_list(*tail))


# 2.3. (уровень сложности: средний)
# Создайте функцию list_to_string(lst), возвращающую строку, содержащую элементы списка.
def list_to_string(lst):
    """Преобразует список в строку."""
    if not lst:
        return ""
    return str(head(lst)) + " " + list_to_string(tail(lst))


# 2.4. (уровень сложности: средний)
# Создайте функцию list_range(low, high), возвращающую список чисел от low до high включительно.
def list_range(low, high):
    """Создает список чисел от low до high включительно."""
    return make_list(*range(low, high + 1))


# 2.5. (уровень сложности: средний)
# Создайте функцию foldl(func, lst, acc), вычисляющую свертку элементов списка, аналогично reduce.
def foldl(func, lst, acc):
    """Вычисляет свертку списка."""
    if not lst:
        return acc
    return foldl(func, tail(lst), func(acc, head(lst)))


# 2.6. (уровень сложности: средний)
# Создайте функцию list_sum(lst) для вычисления суммы элементов списка с помощью foldl.
def list_sum(lst):
    """Вычисляет сумму элементов списка."""
    return foldl(lambda acc, x: acc + x, lst, 0)


# 2.7. (уровень сложности: средний)
# Создайте функцию fact(n) для вычисления факториала с помощью foldl и list_range.
def fact(n):
    """Вычисляет факториал числа n."""
    return foldl(lambda acc, x: acc * x, list_range(1, n), 1)


# 2.8. (уровень сложности: средний)
# Создайте функцию list_to_py(lst) для преобразования списка в обычный список Питона с помощью foldl.
def list_to_py(lst):
    """Преобразует список в обычный список Питона."""
    return foldl(lambda acc, x: acc + [x], lst, [])


# 2.9. (уровень сложности: средний)
# Создайте функцию list_reverse(lst) для разворота списка в обратном направлении с помощью foldl.
def list_reverse(lst):
    """Разворачивает список в обратном направлении."""
    return foldl(lambda acc, x: pair(x, acc), lst, None)


# 2.10. (уровень сложности: средний)
# Создайте функцию foldr(func, lst, acc), вычисляющую свертку справа для элементов списка.
def foldr(func, lst, acc):
    """Вычисляет свертку справа для элементов списка."""
    if lst is None:
        return acc
    return func(head(lst), foldr(func, tail(lst), acc))


# 2.11. (уровень сложности: средний)
# Создайте функцию list_map(func, lst), аналог map, с помощью foldr.
def list_map(func, lst):
    """Применяет функцию func к каждому элементу списка lst."""
    return foldr(lambda x, acc: pair(func(x), acc), lst, None)


# 2.12. (уровень сложности: средний)
# Создайте функцию list_filter(pred, lst), аналог filter, с помощью foldr.
def list_filter(pred, lst):
    """Фильтрует элементы списка lst с помощью предиката pred."""
    return foldr(lambda x, acc: pair(x, acc) if pred(x) else acc, lst, None)


# 2.13. (уровень сложности: средний)
# Создайте функцию sum_odd_squares для вычисления суммы квадратов нечетных чисел списка с помощью list_sum, list_map и list_filter.
def sum_odd_squares(lst):
    """Вычисляет сумму квадратов нечетных чисел списка lst."""
    odd_nums = list_filter(lambda x: x % 2 == 1, lst)
    odd_squares = list_map(lambda x: x**2, odd_nums)
    return list_sum(odd_squares)


# 2.14. (уровень сложности: средний)
# Создайте функцию list_concat(lst1, lst2) для соединения двух списков.
def list_concat(lst1, lst2):
    """Соединяет два списка lst1 и lst2."""
    return foldr(pair, lst1, lst2)


# 2.15. (уровень сложности: средний)
# Создайте функцию list_replace(lst, index, value) для изменения элемента списка по индексу.
def list_replace(lst, index, value):
    """Заменяет элемент списка lst по индексу index на значение value."""
    if lst is None or index < 0:
        return lst
    elif index == 0:
        return pair(value, tail(lst))
    else:
        return pair(head(lst), list_replace(tail(lst), index - 1, value))


if __name__ == '__main__':
    # создание списка
    lst = make_list(1, 2, 3, 4, 5)
    print(f'Созданный список: {list_to_string(lst)}')  # 1 2 3 4 5
    # # получение головы и хвоста
    print(f'Голова: {head(lst)} ; Хвост: {list_to_string(tail(lst))}')  # 1 ; 2 3 4 5
    # # создание списка чисел от low до high
    print(f'Список от low до high: {list_to_string(list_range(6, 10))}')  # 6 7 8 9 10
    # # foldl
    print(f'Свертка списка: {foldl(lambda acc, x: acc - x, lst, 0)}')  # -15
    # # вычисление суммы элементов списка
    print(f'Сумма элементов: {list_sum(lst)}')  # 15
    # # вычисление факториала
    print(f'Факториал 5: {fact(5)}')  # 120
    # # преобразование списка в обычный список Питона
    print(f'Преобразование в список Python: {list_to_py(lst)}') # [1, 2, 3, 4, 5]
    # # разворот списка
    print(f'Разворот списка: {list_to_string(list_reverse(lst))}')
    # # foldr
    print(f'Свертка списка справа: {foldr(lambda acc, x: acc - x, lst, 0)}')  # 3
    # # map
    print(f'Map списка: {list_to_string(list_map(lambda x: x*x, lst))}')
    # # filter
    print(f'Фильтрация списка: {list_to_string(list_filter(lambda x: 1 < x < 5, lst))}')
    # # sum_odd_squares
    print(f'Сумма квадратов нечетных чисел: {sum_odd_squares(lst)}')
    # # list_concat
    print(f'Конкатинация списков: {list_to_string(list_concat(lst, list_range(6, 10)))}')
    # # list_replace
    print(f'Изменение элемента по индексу: {list_to_string(list_replace(lst, 2, 10))}')