Scheme + functional programming

1. замени cond хэшем или упорядоченным списком.

2. возвращай не список, а массив (или вектор - не помню как там в схеме называется), тогда временная сложность поиска элемента по индексу будет O(1) вместо O(N).

> Изучаю сейчас сабж, и у меня возникли некоторые затруднения. 
Предположим, передо мной стоит простая задача: реализовать операции 
добавления числа и умножения на число некой последовательности чисел. 
Как это грамотно сделать с точки зрения функционального 
программирования? 

(define (add-list x list)
  (map (lambda (y) (+ x y)) list))

(define (mul-list x list)
  (map (lambda (y) (* x y)) list))

или 

(define (op-list func) 
  (lambda (x list)
    (map (lambda (y) (func x y)) list)))

(define add-list (op-list +))
(define mul-list (op-list *))

Это функциональный подход. Как потом ты эти функции будешь 
использовать - напрямую или завернешь в какой-то обобщенный API
- зависит от требований конкретной программы.

> 1. замени cond хэшем или упорядоченным списком.

Тоже имхо какая-то полумера :) Зачем мне рыться в хеше, если я точно знаю какое замыкание я хочу вызвать.

> 2. возвращай не список, а массив (или вектор - не помню как там в схеме называется), тогда временная сложность поиска элемента по индексу будет O(1) вместо O(N).

Это вариант, кстати, я уже думал над ним :) Но все действия над вектором деструктивные, так что это уже не функциональное программирование получается :(

> (define (op-list func) (lambda (x list) (map (lambda (y) (func x y)) list)))

С этим тоже понятно, но тут нет замыкания для параметров. А если, кроме последовательности, мне надо будет передавать еще какую-нибудь ее длину, и плюс еще пять параметров, то внутреняя лябмда станет некрасивой -- (lambda (x list length param0 param1 ...) :(

> (define (op-list func) (lambda (x list) (map (lambda (y) (func x y)) list)))

Кстати, этот вариант не будет в схеме работать, потому что там одно пространство имен для функций и переменных, а list -- это функция :)

А это тоже не будет:

(let ((foo (lambda (x) (+ x 1)))
  (let ((foo (foo 2)))
    foo))

?

> Тоже имхо какая-то полумера :) Зачем мне рыться в хеше, если я точно знаю какое замыкание я хочу вызвать.

Все зависит от требований к объектной модели. Этот подход используется, например, в Objective-C (а также ЕМНИП Python, Ruby). Он позволяет добавлять методы к существующим классам, ну и на тему MOP можно извратиться :-)

> Это вариант, кстати, я уже думал над ним :) Но все действия над вектором деструктивные, так что это уже не функциональное программирование получается :(

Все? vector-set! только!

> С этим тоже понятно, но тут нет замыкания для параметров. А если, кроме последовательности, мне надо будет передавать еще какую-нибудь ее длину, и плюс еще пять параметров, то внутреняя лябмда станет некрасивой -- (lambda (x list length param0 param1 ...) :(

А вот это уже abstract data types :-) Напиши для начала макры для структур. Поверх них - определи наследование структур. Ну и в конце добавь виртуальные методы (через массив).

ЕМНИП в guile есть аналог CLOS, причем практически полностью сделанный на макрах. Можно еще посмотреть на реализацию CLOS.

Вот еще: ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-1014.pdf ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-602.pdf

> А это тоже не будет:

> (let ((foo (lambda (x) (+ x 1))) (let ((foo (foo 2))) foo))

Черт, был не совсем прав :) И то и то работать будет, но в первом случае переопределится list, и использовать его как функцию внутри лямбды уже не получится.

> Все зависит от требований к объектной модели. Этот подход используется, например, в Objective-C (а также ЕМНИП Python, Ruby). Он позволяет добавлять методы к существующим классам, ну и на тему MOP можно извратиться :-)

Да, но ведь это неминуемо влечет за собой снижение производительности :( Конкретно мне ооп, получается, нужен совсем в минимуме, все остальное достаточно удобно решается самой схемой

> А вот это уже abstract data types :-) Напиши для начала макры для структур. Поверх них - определи наследование структур...

Большое спасибо за ссылки, сейчас сделал что-то подобное Soft Objects на макрах :) Очень удобно, хотя главной моей проблемы это не решило -- как сделать замыкание глобально видимым, чтобы можно было быстро до него добраться. Пока реализовал это через вектор, но буду еще думать :)

Какие черты ООП тебе нужны? А то не представляя твоей задачи сложно что-либо посоветовать :-)

По поводу ООП и ФП - погугли на тему ООП в Haskell. Вообще ФП более мощная штука, чем ООП и невсегда нужно применять привычные(?) (ООП в смысле) приемы проектирования.

> Вообще ФП более мощная штука, чем ООП и невсегда нужно применять привычные(?) (ООП в смысле) приемы проектирования.

Ага, я и пытаюсь сейчас отойти от привычной мне парадигмы и освоить фп. 

Вот у меня сейчас более конкретная задача -- в процессе осваивания схемы я сделал симулятор back-propagation нейросети. Без деструктивных операций, но совсем без применения привычного ооп у меня не получилось -- например:

(define make-processing-unit
  (lambda (input-weights
           weights-deltas
           activate-func
           learn-filter
           output-value
           error-value)
    (lambda (m)
      (cond ((equal? m 'propagate) ...)
            ((equal? m 'adjust-weights) ...)
            ((equal? m 'set-error) ...) 
  ...))

Я пока не могу взять в толк, как это дело разбить на независимые функции, без необходимости тащить в параметрах каждой input-weights, weights-deltas и прочее :( 
С замыканиями получается удобно, но чтобы вытащить эти замыкания "наружу" из make-processing-unit, нужна либо диспетчеризация, либо список, либо надо использовать деструктивные операции. 
При обучении сети тот же make-processing-unit может многие тысячи раз вызываться, и затраты на диспетчера сообщений уже начинают напрягать :(

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

type processing_unit = { 
   input_weight : float list; 
   weight_deltas  : float list;
   (* и т.д. *)
}

в схеме нужно ввести соглашение о том, что значения processing-unit имеют вид:

#(processing-unit input-weights weights-deltas ... )

далее процедуры оперирующие значениями processing-unit будут иметь вид:

(define (processing-unit-propagate pu)
  (if (not (eq (vector-ref pu 0) 'processing-unit))
    (error "not a processing-unit"))
  (let ((input-weights (vector-ref pu 1))
        (weights-deltas (vector-ref pu 2)
        ;; и т.д.
        )
     ;; тут код...
     ))

Еще можно сделать так:

(define (make-processing-unit input-weights
           weights-deltas
           activate-func
           learn-filter
           output-value
           error-value)
   (lambda (i)
     (case i 
       (0 input-weights)
       (1 weights-deltas)
       ;; и т.д.
     )))

Так лучше скрыта структура, но эффективноть будет ниже.

Вообще есть такая штука SRFI (Scheme Request for Implementation srfi.schemers.org) называется. Реализации схемы поддерживают некоторое подмножество этих спецификаций (из тех, что я использовал в mzscheme реализовано много SRFI). Кроме того есть и собственные (реализаций) аналоги defstruct из Common Lisp.

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

> Т.к. в схеме типизация динамическая, что там не нужны кортежи - достаточно списков или векторов.

Блин, точно :) Что-то я не додумался до такого элементарного решения, спасибо =)

> Еще можно сделать так:

Я сейчас попроще сделал, макрос define-struct

(define-struct processing-unit (weights activate-func learn-filter output-value error-value))

который раскрывается в

(define make-processing-unit (...

(define processing-unit-weights (lambda (processing-unit) (...

(define processing-unit-activate-func (lambda (processing-unit) (...

...

и тд. Действительно, получается, что вектор спрятан за макросом, а на верхнем уровне я "вроде как" работаю с именованными полями. Класс, походу, именно то, что мне и нужно было :)