Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Функциональный подход  (Прочитано 11389 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« : 18-07-2009 19:21 » 

Читая блог Вада, заметил, что его в последнее время тянет на функциональный подход и Haskell. Возможно потому, что этот подход ближе к чистой математике, нежели к жутким реалиями разных сырых SDK. Так сказать, горний мир и пища духовная для программиста и прикладного математика Улыбаюсь

Посему ставлю вопрос ребром.

В лямбда-исчислении Чёрча любая функция от N аргументов разлагается на композицию функционалов. Т.е., например, f(x, y) = (g(x))(y), где g - не функция, а функционал - т.е. такое особое выражение, результатом вычисления которого является функция или другой функционал (как, например, неопределённые римановы интегралы в математике).

В связи с этим возникают широкие возможности для организации ленивых вычислений. Общая суть подхода сводится к тому, чтобы в некоторой точке древовидного вычислительного процесса наметить ответвление, но не углубляться в эту ветвь до тех пор, пока не потребуется результат её исполнения. Чем-то это похоже на шаблоны C++ и generic-типы в других языках, только они обрабатываются компилятором, а в функциональных языках такие подстановки происходят прямо во время исполнения.

Возьмём простую задачу поиска минимума в списке чисел.

Алгоритмический подход в лоб известен, думаю, всем (а те, кому он не известен, уже закрыли эту тему, придя в полное уныние от предыдущих абзацев) - это перебор списка с запоминанием лучшего решения из уже перебранной части.
Код: (Pascal)
const N = 100;
type
   ArrayRangeType = 1..N;
   ArrayItemType = Real;
   ArrayType = array [ArrayRangeType] of ArrayItemType;
function Min(a: ArrayType): ArrayItemType;
var
   i: Integer;
   result: ArrayItemType;
begin
   result := High(ArrayItemType);
   for i := Low(ArrayRangeType) to High(ArrayRangeType) do
      if a[i] < result then
         result := a[i];
   Min := result;
end;

Другой подход (кстати, будто бы упомивашийся у кого-то из классиков - то ли Кнута, то ли Дейкстры) связан с богатством средств языка. Т.е. если в языке есть встроенная сортировка, то гораздо компактнее (но зато хуже по объёму вычислений) использовать её:
Код: (Javascript)
function min(array)
{
   if(array instanceof Array && array.length > 0)
      return array.sort()[0];
   else
      return NaN;
}

Второй вариант более близок к идеям функционального подхода, но нет предела совершенству.

Без сортировки просто найти минимум достаточно просто через рекурсию:
Код: (Text) Common Lisp
(defun mmin(l) (if l ((lambda(h t) (if t ((lambda(x y) (if (< x y) x y)) head (mmin t)) h)) (car l) (cdr l)) nil))
(Чёрт, совсем забыл, как можно внятно форматировать код на Lisp Улыбаюсь.)

Вопрос: можно ли тот же алгоритм быстрой сортировки Хоара таким образом представить в виде композции функционалов и функций, чтобы избавиться от последовательности операций: сортировка списка, взятия i-го элемента. Т.е. составить такую функцию от двух аргументов: списка и номера элемента в списке f(a, i), которая бы обеспечивала возврат i-го в порядке возрастания элемента списка, при этом рассматривая сортировку не как операцию над всем списком, а как операцию доступа к элементу списка, возможно, выполняясь частично - лишь по мере необходимости доступа к i-му элементу?
« Последнее редактирование: 18-07-2009 19:26 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 19-07-2009 05:33 » 

а даже если это и возможно, это ведь приведёт к снижению быстродействия, зачем к этому стремиться ?

а ещё две мысли по этому поводу

1) в сортировке Хоара (если не путаю,  это сортировка с разбиением списка на две части, сортировки их по отдельности рекурсивно, затем слияние ? )  нужный элемент может оказаться в самом последнем "кусочке" разбиваемого списка. Так же, как и этот факт неизвестен, пока до последнего кусочка не добрались (а вдруг , всё таки, минимальный элемент был где то в середине, но мы же этого не узнаем, если до конца не добрались). Короче, вся сортировка всё равно будет произведена полностью... Или я ошибаюсь ? ))

2) отсортировать список нужно один раз, потом добавлять элементы "порядочно"  (хотя, это тоже не всегдм возможно, но когда список часто обновляется полностью, его так и так придётся заново сортировать, так что возвращаемся к пункту 1 )
« Последнее редактирование: 19-07-2009 05:40 от Алексей1153++ » Записан

Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 19-07-2009 08:02 » 

Не знаю, как насчёт быстродействия. Зависит от подхода к задаче (не говорю "алгоритма" - это ж функциональный подход Улыбаюсь ).

1) Основной недостаток алгоритмов квадратичной сложности - это сравнение каждого элемента с каждым или близко к тому. Медленно. Основное преимущество более быстрых сортировок заключается в выделении упорядоченных подсписков - тогда количество сравнений уменьшается до логарифмической сложности.

2) Для функционального подхода это утверждение имеет мало смысла. В функциональном подходе нет состояний и изменяемых со временем переменных. Поэтому слово "добавить" нужно понимать как вычисление нового списка из двух имеющихся, а слова "обновить" и "заново сортировать" вообще абсурдны.

Чисто алгоритмический подход состоит в перемещении элементов в списке - т.е. операции присваивания значений (записывания их в одни и те же области памяти, которые и называются переменными). В функциональном подходе нет операции присваивания в принципе.

Более близкий к функциональному подход к сортировке состоит, например, в построении бинарного дерева упорядочения элементов на основе списка, а потом извлечения из этого дерева крайнего элемента. Но это построение вспомогательной структуры данных для решения задачи.

Я же предлагаю сконструировать такой (возможно, за счёт рекурсии самогенерируемый) код - структуру кода, которая бы позволила решить задачу. В функциональном подходе за счёт широкого использования функционалов и функций как данных разницы между кодом и данными нет.


Ещё одна провокационная задача: написание рекурсивной лямбда-функции Улыбаюсь Поскольку лямбда-функция по определению анонимна, не имеет идентификатора и идентифицируется сама собой во всей своей полноте, то классический подход к рекурсии как самовызов функции тут не подходит. А вот подход, основанный на самокопировании или самогенерации своей копии или подобия для последующего исполнения, возможно, будет продуктивным. Когда-то давным давно было такое развлечение, как написание программ, умеющих печатать самих себя. Задачка примерно из этой области, только более полезная с точки зрения программирования Улыбаюсь Раскрывает широкие возможности написания программ "на одном дыхании", т.е. вся программа будет представлять собой единое выражение, состоящее только из лямбда функций и исходных данных - как в чистой математике Улыбаюсь
« Последнее редактирование: 19-07-2009 08:12 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 19-07-2009 10:49 » 

уф, как-то много абстракции )) На словах всё красиво, а когда реальное применение начнётся - всё равно придётся углубиться в прозу Улыбаюсь
Записан

Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 19-07-2009 21:20 » 

Цитата
Вопрос: можно ли тот же алгоритм быстрой сортировки Хоара таким образом представить в виде композции функционалов и функций, чтобы избавиться от последовательности операций: сортировка списка, взятия i-го элемента.
А почему нельзя? В статье про быструю сортировку есть чисто функциональный пример на Haskell и Python. Там просто используется хитрый сахар на генераторах:
Код:
qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
    where
        lesser  = [ y | y <- xs, y < p ]
        greater = [ y | y <- xs, y >= p ]

Или что ты имеешь в виду под последовательностью? Так или иначе, последовательность будет - список нужно обрабатывать рекурсивно Улыбаюсь
« Последнее редактирование: 19-07-2009 21:22 от Вад » Записан
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 20-07-2009 09:16 » 

Под последовательностью я подразумеваю то, что в начале исходный список преобразуется в отсортированный, и только потом из отсортированного списка извлекается элемент с определённым номером. Вот хотелось бы эти "сначала" и "потом" ликвидировать - тогде не останется отдельно сортировки и отдельно доступа к элементу, а всё это превратится в одну операцию поиска нужного элемента по определённому сценарию течения вычислительного процесса.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 21-07-2009 19:25 » 

Ещё одна провокационная задача: написание рекурсивной лямбда-функции Улыбаюсь Поскольку лямбда-функция по определению анонимна, не имеет идентификатора и идентифицируется сама собой во всей своей полноте, то классический подход к рекурсии как самовызов функции тут не подходит. А вот подход, основанный на самокопировании или самогенерации своей копии или подобия для последующего исполнения, возможно, будет продуктивным.
Насколько я могу судить, эта задача решается с помощью штуки, называемой Y-комбинатором.
Вот, соорудил на Scheme расчёт факториалов с его помощью Улыбаюсь
Код: (Scheme)
(define factor
  ((lambda (f)
    ((lambda (x)
        (f (lambda (arg)
            ((x x) arg) ) ) )
        (lambda (x)
            (f (lambda (arg)
                ((x x) arg) ) ) ) )
    )
    (lambda (f)
        (lambda (x)
            (if (= x 0)
                1
                (* x (f (- x 1) ) ) ) ) ) ) )
Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 22-07-2009 09:18 » 

Практика функционального программирования
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dimka
Деятель
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 14-11-2013 22:23 » new

Что-то какой-то слишком сложный код для Y-комбинатора - какие-то вложенные лямбды зачем-то... - идея плохо видна.

Код: (Javascript)
(
 function(x, f) // Запускающая лямбда
 {
  return f(x, f)
 }
)( // Вызов запускающей лямбды - с аргументами
 7, // Аргумент (тип значения число): начальное значение для запуска рекурсии
 function(x, f) // Аргумент (тип значения функция): основная лямбда рекурсии
 {
  return x <= 0 ? 1 : x * f(x - 1, f)
 }
)
« Последнее редактирование: 14-11-2013 22:30 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines