Scheme. Некоторые заметки о ФП

Автор: Мират Каденов

Познакомился я тут с языком Scheme, правда, не по своей воле. Ну что я могу сказать? Мой «зачерствевший императивно-декларативный разум» конечно, был сильно удивлен этим новым обстоятельством. Особенно больно было в первое время. Чувствуешь, как шестерни в голове, уже отвыкшие от вращения, заржавевшие за многие годы, начинают со страшным скрипом и хрустом проворачиваться. Но, забавно. Давайте похрустим вместе…

Постановка задачи

Ну вот, к примеру, такая простая задачка: на вход дано два множества (списка) без одинаковых элементов, надо найти их «симметрическую» разность (во как закрутил). «Симметрическая» разность множеств A и B – это множество, состоящее из элементов, встречающихся только либо в A, либо в B. То есть, другими словами, надо найти все элементы, которые встречаются только в одном из исходных множеств.

Поиск элемента

Как ее решать? Начнем с того, что полезно бы иметь функцию, принимающую элемент и множество, которая выдает true или false в зависимости от того, есть этот элемент в этом множестве или нет.

Такую функцию в Scheme можно объявить так:

 
  (define (search elem list)
    (if (null? list)
        #f
        (if (equal? elem (car list))
            #t
            (search elem (cdr list) )
            )
        )
    )

Как видим, циклов в Scheme нет*, переменных тоже. Все, что есть – рекурсия. Благодаря этому даже такие тривиальные действия как поиск элемента в списке иногда решаются очень непривычно, но, в то же время, красиво и элегантно.

* Комментарий редакции.

Не совсем верно, зависит от диалекта.

Пересечение множеств

Дальше – больше. Итак, вопрос: «Как найти пересечение двух множеств A и B?». То есть такое множество, каждый элемент которого содержится и в A и B одновременно. Естественно возникает желание сделать два вложенных цикла, внешний проходит по элементам первого множества, а второй ищет эти элементы во втором.

Еще один прикол – в Scheme нельзя передавать в функцию параметры по ссылке. Да и затруднительно найти способ этим воспользоваться, язык не позволит. И вообще переменных в обычном смысле слова в Scheme нет. Есть императивные (звучит, чуть ли не как империалистические) хаки, но использовать мы их не будем. Тогда, как и где функция поиска пересечения будет накапливать элементы искомого множества? Правильно, она будет передавать себе же множество, а возвращать это же множество плюс найденные элементы. А самая верхняя функция вызывается с пустым аргументом.

Ну, а так как теперь рекурсия правит балом, искать ответ надо примерно так:

  • отщепляем от первого множества один элемент, а если оно пустое, возвращаем ответ;
  • ищем его во втором множестве (у нас уже есть функция Search() );
  • если он есть, добавляем его к ответу;
  • если нет, то применяем эти же шаги к остатку первого множества (то есть этому же множеству без первого элемента).

Вот мой вариант (наверное, можно сделать оптимальнее, но пока пойдет):

 
  (define (_intersection l p accum)
    (if (null? l)
        accum
        (if (search (car l) p)
            (cons (car l) (_intersection (cdr l) p accum) )
            (_intersection (cdr l) p accum)
            )
        )
    )

Где: l и p – множества, пересечение которых надо искать, accum – тот самый аккумулятор, в новых реинкарнациях которого и копится ответ. Все-таки стек – великая вещь. Если вы писали интерпретатор, то понимаете, что реализация фреймов и стека при вызове функций – это не просто удобство, без этого невозможно сделать рекурсию.

Только нашего пользователя никто не предупреждал, что надо передавать третьим аргументом пустой список на самом верху рекурсии, поэтому определим функцию intersection:

 
  (define (intersection l p)
    (_intersection l p '())
  )

Это так, чтобы не было неожиданностей.

Объединение множеств

Как вы уже поняли, множество представляется просто списком. Теперь стоит задача объединить два списка (множества) в один. Используя стандартные операции над списками cdr (получить остаток списка без первого элемента) и car (получить голову списка) эту задачу можно решить так:

 
  (define (concat l p)
    (if (null? l)
       p

        (if (null? (cdr l))
            (cons (car l) p)
            (cons (car l) (concat (cdr l) p) )
            )
        )
    )

Если первый список пустой, то возвращаем второй. Если его остаток пустой (то есть в нем только один элемент), то приделываем этот оставшийся элемент ко второму и возвращаем. А иначе – приделываем первый элемент первого множества к тому, что вернет эта же функция, вызванная к остатку первого списка и второго. Исторически так сложилось, что эта задача – это было первое, что я решал на Scheme, и у меня осталось много приятных воспоминаний об этом. Мне и сейчас приятно вспоминать о том озарении, которое снизошло на меня, когда я до этого додумался. Эх, хорошо.

Вычитание множеств

Здесь проблем нет, надо найти такое множество, элементы которого содержатся в первом списке, но не содержатся во втором. Решается абсолютно аналогично пересечению множеств, разве что действия под if’ом переставлены местами:

 
  (define (_substraction l p accum)
      (if (null? l)
        accum
        (if (search (car l) p)
            (_substraction (cdr l) p accum)
            (cons (car l) (_substraction (cdr l) p accum) )
            )
        )
    )

  (define (substraction l p)
     (_substraction l p '() )
    )

И, наконец, сама задача

У нас есть много-много множественных операций. А теперь собственно маленькое чудо:

 
  (define (process l p)
  (substraction (concat l p) (intersection l p))
    )

Вот и вся задача. Почему «симметрическая» разность A и B равна разности их объединения и пересечения. Это можно на бумажке нарисовать. Круги Эйлера называются (см. рисунок):

Объединение A и B – это все в пределах обоих кругов. Их пересечение – это то, что закрашено серым цветом. А то, что мы ищем – зеленым. Если от всего, что внутри кругов отнять закрашенное серым – остается как раз зеленое.

Scheme в действии

Свяжем нашу функцию с внешним миром:

 
  (display (process (read) (read)) )
  (display "\n")

И запустим. Я использую в качестве среды DrScheme, входящий в состав PLT Scheme** www.plt-scheme.org. Но рисовать скрины здесь неудобно, так что запустим программу в командной строке:

 
  mirat@mirat-laptop:~/Documents<img class="teximage"
      src="/sites/default/files/tex/5d47e3cd417d8319f8a20411e81dadb3af8b7df4.png" alt="$  
        mzscheme -qUr   example.txt
  (a b c d e f) (r t b c x)
  (a d e f r t x)
  mirat@mirat-laptop:~/Documents $" />

В первой строке – это то, что я сам ввел, на второй – результат. А как интерпретатор Scheme парсит ввод – это просто сказка. Здесь я вспомнил все эти лихие годы: разбор данных на Pascal (readln) потом C++ ( sscanf, std::stringstream) и много других ужасов.

Нет, Scheme мне определенно нравится.

** Комментарий редакции.

На данный момент PLT Scheme эволюционировал в Racket www.racket-lang.org

Scheme: Идем дальше

Дальше – больше. В Scheme есть такие операции над списками (вернее не в самой схеме, а в одной из ее библиотек), как find (поиск первого), filter (поиск всех), map (поэлементная обработка списка) и самая интересная fold (свертка).

Первые три не вызывают когнитивного диссонанса при обработке их в моем императивно-декларативном разуме, они выполняют вполне естественные для своего названия действия***.

*** Комментарий автора.

А вернее сказать, возвращают ожидаемый результат. Императивное слово «действие» надо бы вообще не использовать, когда речь идет о функциональном программировании.

Find

Ну, тут все просто, find принимает функцию и список. Вообще, надо привыкать, что передавать функцию в другую функцию – это норма. find применяет функцию к элементам списка (начинает слева и идет дальше) и возвращает тот элемент, для которого эта функция впервые вернет #t (true). Возможная реализация find:

 
  (define (find func lst)
    (if (null? lst)
      '()
      (if (func (car lst))
        (car lst)
        (find func (cdr lst))
      )
    )
  )

Все просто, если на входе пустой список – возвращаем пустой список. Если нет – применяем функцию к первому элементу входного списка. Если функция вернет #t, возвращаем этот элемент. Если нет – вызываем себя же для остатка списка.

 
  (define (check-not-null lst)
    (not (null? lst))
  )

  (define (find-filled lstlst)
    (find check-not-null lstlst)
  )

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

Вот пример для разрядки ситуации:

 
  (display
    (find-filled '( () () (a b c) (a) () )
    )
  )

Filter

filter работает как find, с той лишь разницей, что он возвращает список из всех элементов, удовлетворяющих условию func, то есть func на этих элементах вернет #t:

 
  (define (_filter func lst accum)
    (if (null? lst)
      accum
      (if (func (car lst))
        (cons (car lst) (_filter func (cdr lst) accum ) )
        (_filter func (cdr lst) accum)
      )
    )
  )

  (define (filter func lst)
    (_filter func lst '() )
  )

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

Map

Принимает список и функцию. Возвращает список – результат применения функции ко всем элементам исходного списка:

 
  (define (_map func lst accum)
    (if (null? lst)
      accum
      (cons (func (car lst)) (_map func (cdr lst) accum ) )
    )
  )

  (define (map func lst)
    (_map func lst '() )
  )

Пример:

 
  (define (plus-one x)
    (+ 1 x)
  )

  (display (map plus-one '(1 2 3 4) ) )

Вообще должно получиться****  (2 3 4 5).

**** Комментарий редакции.

Вообще-то ничего получиться не должно. Display – обладает побочным действием, печатает список на экран и не возвращает значение. Это значит, что результат будет получен только на устройство вывода, для программы он будет не доступен. Что бы что-то получилось в данном случае требуется использовать конструкцию (begin (выражение1) … (выражениеN)), которая всегда возвращает результат последнего выражения (опять же, если он есть).

Fold

У нас есть список lst. Есть функция func от двух аргументов: x – текущий элемент списка lst и accum – текущее значение аккумулятора. func возвращает следующее значение аккумулятора. fold (свертка) принимает функцию func, начальное значение аккумулятора init и список lst, возвращает конечное значение аккумулятора.

Вот псевдокод:

 
  fold(func,init,lst) =
    func ( lst[n],
      func ( lst[n - 1],
        func ( lst[n - 2],
          ...
          func ( lst[1],
            func ( lst[0], init)
          )
          ...
        )
      )
    )

Так работает левая свертка. В вызов func для элемента lst[0] передается, кроме самого элемента lst[0], начальное значение аккумулятора init. Этот вызов вернет следующее значение аккумулятора, которое будет передано в вызов func для элемента lst[1] и т.д. А сам fold вернет то, что вернет func для последнего элемента списка lst:

 
  (define (fold func accum lst)
    (if (null? lst)
      accum
      (fold func (func (car lst) accum) (cdr lst) )
    )
  )

Красивый пример использования fold – это реверсирование списка (получение списка, в котором элементы следуют в обратном порядке):

 
  (define (reverse lst)
    (fold cons '() lst)
  )

Где: cons – функция как раз двух аргументов, элемента и списка. Добавляет элемент в начало списка и возвращает результат. Если проследить вызовы в этом примере, нетрудно увидеть, что результатом вызова reverse будет реверсированный список.

Еще один пример:

 
  (define (summ lst)
    (fold + 0 lst)
  )

lambda

Лямбда-функции в Scheme позволяют не давать функциям имен, т.е. объявлять безымянные функции. Это может показаться абсурдом, как это – не давать имени? А как к ней обращаться? Но вспомним, что в примерах выше все, рассмотренные функции (find, filter, map и fold) в качестве одного из аргументов ожидали функцию. Нам приходилось объявлять ее отдельно с помощью define, давать ей имя и затем передавать, куда нужно по имени, хотя нигде, кроме как этого вызова, она больше не использовалась. Вот здесь и можно сэкономить на придумывании имени, если объявить функцию прямо в том месте, где она нужна. Но это одна из причин, зачем безымянные функции нужны. Вторую рассмотрим чуть позже.

Синтаксис объявления лямбда-функций:

 
(lambda (x1 x2 ... xn)  )

Где: x1, x2 – аргументы, lambda – тело функции.

Не отходя от кассы сразу пример:

 
  (define (_map func lst accum)
    (if (null? lst)
      accum
      (cons (func (car lst)) (_map func (cdr lst) accum ) )
    )
  )

  (define (map func lst)
    (_map func lst '() )
  )

  (display
    (map
      (lambda (x) (+ 1 x) )
      '(1 2 3 4)
    )
  )

Как видим, мы избавились от plus-one.

А может ли лямбда-функция быть рекурсивной? Например, хочется заменить _map на лямбда-функцию (некрасиво подчеркивание выглядит). Тут возникает проблема, что, так как лямбда-функция не имеет имени, она не может внутри себя просто так рекурсивно вызвать себя же (_map – рекурсивная функция). Вообще, может. Но из глубин математического ада, называемого лямбда-исчислением, сразу вылезают на свет комбинаторы, теория вычислимости и прочие ужасы. Так что не будем пока углубляться. Если функция должна быть рекурсивной – дадим ей имя, так уж и быть.

Замыкание

А теперь рассмотрим задачу. Надо сформировать список из всех элементов списка lst, которые больше заданного числа min. Вот одно из возможных решений:

 
  (define (_process lst min accum)
    (if (null? lst)
      accum
      (if (> (car lst) min)
        (cons (car lst) (_process (cdr lst) min accum) )
        (_process (cdr lst) min accum) )
      )
    )
  )

  (define (process lst min)
    (_process lst min '() )
  )

  (display (process '(1 2 3 4) 2) )

В принципе, работает. Но как-то все громоздко и неудобно. Нам надо сформировать подсписок из элементов списка, которые удовлетворяют какому-то условию. Почему бы ни использовать для этого filter?

 
  ; Попытка #2

  (define (check x)
    (> x ???)
  )

  (define (process lst min)
    (filter check lst)
  )

  (display (process '(1 2 3 4) 2) )

Тут мы натыкаемся на препятствие. Как функция check узнает, с чем сравнивать x? В коде это недоразумение отмечено вопросиками. Можно было бы передать это как параметр в check:

 
  ; Попытка #3

  (define (check x min)
    (> x min)
  )

  (define (process lst min)
    (filter check???? lst)
  )

  (display (process '(1 2 3 4) 2) )

А теперь вспомним, что filter принимает функцию только одного параметра и передает в эту функцию только текущий элемент списка. Изменить поведение filter мы не можем, кроме как переписать его, но это «не по фэн-шую». Поэтому функция проверки должна иметь один аргумент*****.

***** Комментарий автора.

Раздается звук отката к попытке номер 2.

Здесь и задумаемся: число min неизвестно в check, но зато оно известно в момент вызова filter. Здесь возникает понятие контекста. Простите меня за нестрогость определения, но под контекстом я понимаю совокупность переменных, видимых в данной точке кода. Внутри check мы видим только переменную x, но в контексте вызове filter есть наш желанный min. А почему бы тогда не определить нашу функцию проверки прямо внутри вызова filter? Да-да, лямбда-функция:

 
  ; Попытка #4 (наконец-то верная)

  (define (process lst min)
    (filter (lambda (x) (> x min) ) lst)
  )

  (display (process '(1 2 3 4) 2) )

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

Давайте рассмотрим другой пример (взят из википедии):

 
  (define (adder b)
    (lambda (x)  (+ x b))
  )

  (display ((adder 7) 4))    ; будет напечатано 11

Что делает функция adder? Она принимает аргумент b и возвращает лямбда-функцию. Так. Остановимся, передохнем и осмыслим.

Важно понять, что при каждом вызове adder, он создает и возвращает новый экземпляр лябмда-функции. Вызывая adder 10 раз с разными параметрами b, мы получим в итоге десять разных функций. Каждая из них будет функцией одного аргумента. И каждая будет возвращать сумму своего аргумента с некоторым числом. С каким? Опять остановимся. Осмыслим.

Если мы вызывали adder с числом 7, то возвращенная функция будет к своему аргументу прибавлять число 7. Ну, вот здесь, наверное, и проявляется основное значение слово «замыкание». Казалось бы, где в объявлении нашей лямбда-функции число 7? Его нет, есть только b. Но значение этого b берется из контекста того места, где мы эту лямбда-функцию родили на свет – внутри вызова функции adder. А b – это формальный параметр. Его значение в свою очередь связано с фактическим параметром функции adder (оно равно 7) из контекста того места, где мы adder вызвали. То есть получается, что значение b внутри лямбда-функции замкнуто на внешнее (по отношению к этой функции) значение фактического параметра******.

****** Комментарий автора.

Да, я думаю, как это написать по-человечески.

Кэрринг (карринг, currying)

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

Было:

 
  (define (func x y)
    (
      ; здесь выражение, содержащее x и y
      ; и x и y - формальные параметры данной функции
    )
  )

Стало:

 
  (define (func x)
    (lambda (y)
       (
         ; здесь то же самое выражение, содержащее x и y
         ; но теперь y - это формальный параметр этой внутренней лямбда-функции,
         ; а x - свободная переменная
       )
    )
  )

Другими словами, функция func двух переменных может быть представлена как функция одной переменной, которая возвращает лямбда-фунцию одной переменной, причем возвращенная лямбда-функция x, будет свободной переменной. Таким образом, x внутри лямбда-функции будет замкнуто на то значение x, с которым мы вызовем внешнюю функцию func:

 
  (define (sum x)
    (lambda (y)
      (+ x y)
    )
  )

  (display ( (sum 10) 1) )

Посткриптум

Кэрринг – очень полезная вещь для теоретических исследований, позволяет вообще не рассматривать функции многих переменных отдельно. Практического применения этого приема в обычном программировании я не вижу. Однако если вы разрабатываете интерпретатор какого-нибудь функционального языка, то кэрринг может быть полезным для «выливания воды из чайника» – сведения одной задачи (обработки функции многих переменных) к другой, уже решенной (обработка функций одной переменной).

Вы можете ответить или разместить запись на вашем сайте.

Ответить

Powered by Procoder