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