Страницы

Поиск по вопросам

воскресенье, 16 февраля 2020 г.

Lua, функциональное программирование

#массивы #алгоритм #функции #lua


Дана задача: в массиве чисел (допустим 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 или любой другой книге по функциональному программированию.

Комментариев нет:

Отправить комментарий