Дана задача: в массиве чисел (допустим 1 2 3 4 5 6 7 8 9) реверсировать числа на
нечетных позициях (тут это 1,3,5,7,9, должно получится 9 2 7 4 5 6 3 8 1).
Все это сделать с помощью функционального программирования:
Запрещено использовать циклы, условные операторы, операторы присваивания, операторы
контроля (return можно). Все делать с помощью рекурсий и вызовов других функций.
Вот что я набросал:
local function main()
array = {};
modArray = {};
--Finding count of nums
file = io.open("nums.txt", "r");
numsArrayString = file:read();
stofSpaces = string.gsub(numsArrayString, "%d", "")
ctofNums = string.len(stofSpaces);
file:close();
--Filling array
file = io.open("nums.txt", "r");
fillArray(array, 0);
file:close();
--1st part
irEnd(array, modArray, 0);
end
function fillArray(array, i)
array[i] = file:read("*n");
pos = endOfArray(ctofNums, i) and fillArray(array, i+1);
end
function endOfArray(a, b)
return a >= b;
end
function irEnd(array, modArray, i)
pos = irEndChecker(i+1) and irEnd(array, modArray, i+2);
modArray[i] = array[i];
print(modArray[i]);
end
function irEndChecker(a)
return a < ctofNums;
end
main();
print(modArray[i]); выводит все в нужном мне порядке (9,7,5,3,1, и четные между ними),
только вот мне не выводить нужно а присваивать (получается 1,3,5,7,9 в нужном массиве).
Что мне сделать с рекурсивной функцией не только для корректного вывода, но и для конкретного
присваивания?
Ответы
Ответ 1
Для начала, приведу полный код решения задачи. Сможете убедиться, что эта мешанина
скобок даёт нужный результат.
Если после прочтения кода он останется непонятым, если явные отсылки к SICP останутся
незамеченными, то прошу листать ниже -- там я попытаюсь объяснить, как работает этот
оголтелый псевдолисп.
-- Создание пары
function cons(_x, _y)
return function(m) return (m == 0 and _x) or _y end
end
-- Получаем "голову" списка (первый элемент)
function head(list)
return (list ~= nil and list(0))
or nil
end
-- Получаем "хвост" списка (всё кроме первого элемента)
function tail(list)
return (list ~= nil and list(1))
or nil
end
-- Собираем список в строку
function list2str(list)
return (tail(list) ~= nil and head(list) .. ', ' .. list2str(tail(list)))
or head(list)
end
-- Собираем список из параметров функции
function make_list(head, ...)
return (... ~= nil and cons(head,make_list(...)))
or cons(head, nil)
end
-- Переворачиваем список
function reverse_list(list)
return reverse_acc( list, nil )
end
-- Сервисная функция с аккумулятором для переворота списка
function reverse_acc(list, acc)
return (tail(list) ~= nil and
reverse_acc( tail(list), cons( head(list), acc ) ) )
or cons( head(list), acc )
end
-- Получаем каждый второй элемент списка. От index зависит,
-- будут ли это чётные или нечётные элементы
function get_sublist(list, index)
return (tail(list) ~= nil and
(index == 1 and
cons( head(list), get_sublist( tail(list), 0))
or
get_sublist( tail(list), 1) ) )
or (index == 1 and
cons(head(list), nil) )
or nil
end
-- Получаем нечётные елементы списка
function get_odd(list)
return get_sublist(list, 1)
end
-- Получаем чётные елементы списка
function get_even(list)
return get_sublist(list, 0)
end
-- Собираем в один два списка {a1, a2, ...} и {b1, b2, ...}
-- по принципу: {a1, b1, a2, b2, ...}
function megre_lists(list1, list2)
return (tail(list1) ~= nil and
cons( head(list1), cons( head(list2), megre_lists( tail(list1), tail(list2) ))))
or
cons( head(list1), head(list2) ~= nil and
cons( head(list2),nil)
or
nil)
end
function main_task(list)
-- Печать первоначального списка
print( list2str(list) )
-- Тестирование функции переворачивания списка
print( list2str(reverse_list(list)) )
-- Тестирование получения нечётных элементов
print( list2str(get_odd(list)) )
-- Тестирование получения чётных элементов
print( list2str(get_even(list)) )
-- Получаем список нечётных элементов, переворачиваем его и сливаем со списком
-- чётных элементов
print ( list2str(
megre_lists(
reverse_list( get_odd(list) ),
get_even(list) ) ) )
end
main_task( make_list(unpack( {1, 2, 3, 4, 5, 6, 7, 8, 9} )) )
Начинаем разбираться с принципами функционального программирования.
В первую очередь, нам нужен истинно функциональный тип данных. То есть, данные мы
будем хранить прямо в функции. И да, этот тип данных -- неизменяемый.
function cons(_x, _y)
return function(m) return (m == 0 and _x) or _y end
end
Функция возвращает функциональный тип данных, который будем называть «пара». Этот
тип данных содержит два значения. Чтобы эти значения мы могли получать, нам нужно ввести
ещё две функции:
function head(list)
return (list ~= nil and list(0))
or nil
end
function tail(list)
return (list ~= nil and list(1))
or nil
end
Функция head (голова) позволяет получить первый элемент из пары, а функция tail (хвост)
– второй элемент. Почему у функций названия «голова» и «хвост» станет понятно далее.
Кстати, уже видно как мы будем обходиться без условного оператора. На самом деле,
условный оператор нам нужен. Без него из рекурсии не выйти. Поэтому пользуемся удобным
синтаксисом lua и совершенно не меняя логику работы вместо
if condition then
code1
else
code2
end
пишем так:
condition and code1
or code2
С условным оператором разобрались. Продолжаем делать функциональные типы данных.
Нам нужны списки для привычной функциональной парадигмы работы с данными. Для этого
мы используем функциональную пару. В первый элемент пары мы записываем первый элемент
списка, а во второй – вторую пару. Во второй паре у нас опять значение находится в
первом элементе, а во втором – следующая пара. Получается своеобразная цепь из пар.
Во втором элементе последней пары в цепи будем устанавливать nil. Это будет признаком
конца списка. Функция make_list формирует список из своих аргументов. Вот теперь появляется
смысл у названий функций head и tail. Первая функция возвращает первый элемент списка,
а вторая – весь остальной список. Как голова удава, и его хвост. Если вы не знакомы
с функциональным программированием, то просто поверьте на слово – трёх функций cons,
head, tail вполне достаточно для любых работ с функциональными списками.
А дальше мы решаем все задачи при помощи функций с рекурсиями. Это как нарисовать
сову. Это как на лекции по математике лектор говорит: "отсюда легко видеть". Всё скучно
и логично. Скучно для тех, кто знаком с базовыми алгоритмами функционального программирования.
Остальных я отсылаю к SICP или любой другой книге по функциональному программированию.
