Не угадал автора по заголовку.

Racket

Толсто.

По теме — классическая дилемма, что важнее — время программиста или время выполнения. Ответ — когда как.

Толсто

Я перебрал те функциональные языки, что были под рукой (SBCL, Racket). Не на Си++ же проверять.

На Haskell не проверял, так как не умею там функцию многократно выполнить (ленивость, чистота и всё такое).

Непонятно, что такое твой этот compose и почему в варианте на рэкете ты его вызываешь каждый раз в функции.

время программиста или время выполнения. Ответ — когда как.

ФВП не уменьшает время программиста. Только делает более красивый/удобный интерфейс.

Более того, если брать лиспы, то всё сводится к тому, что compose должен быть не функцией, а макросом, преобразующим

(alexandria:compose
            (lambda (x) (+ x 1))
            (lambda (x) (+ x 2))
            (lambda (x) (+ x 1)))

(lambda (x) (+ (+ (+ x 1) 2 1))))

Технически вполне реализуемо...

В GHC можно настрогать rewrite rules/SPECIALIZE для особых случаев.

что такое твой этот compose

По смыслу

(define (compose f . fs)  
  (cond 
    [(null? fs) f]
    [else 
     (define rest-f (apply compose fs))
     (lambda (x) (f (rest-f x)))]))

почему в варианте на рэкете ты его вызываешь каждый раз в функции

Не каждый раз. Он вызывается один раз и возвращает f-comp

The First Rule of Program Optimization: Don't do it.

The Second Rule of Program Optimization – For experts only: Don't do it yet.

rewrite rules/SPECIALIZE для особых случаев

Ух ты!!! DEFINE-COMPILER-MACRO в Haskell! Спасибо, не знал.

Ожидаемо же что косвенный вызов хуже прямого. Другое дело, что оптимизатор мог бы такие лямбды инлайнить, афаик в C++ такое делается.

The First Rule of Program Optimization: Don't do it

Так родилась Java. А потом всё-таки пришлось почти всё оптимизировать.

Вот эта жаба сейчас повсюду, когда как твой лисп никому не нужен.

ФВП не уменьшает время программиста. Только делает более красивый/удобный интерфейс.

Было бы point-free вместо всяких

(lambda (x) (+ x 1))

тогда можно было бы поговорить о красивом/удобном интерфейсе. В clojure же есть ->.

Было бы point-free вместо всяких

Можно и

(define f-comp
  (compose
   (curry + 1)
   (curry + 2)
   (curry + 1)))

Только тогда скорость становится уже в 10 раз, а не 1.5:

cpu time: 728 real time: 730 gc time: 0
cpu time: 6056 real time: 6046 gc time: 132

лiл

import timeit

hof_start = '''
def cmps(*args):
	def inner(x):
		for f in args[::-1]:
			x = f(x)
		return x
	return inner

f = cmps(lambda x: x+1, lambda x: x+2, lambda x: x+1)
'''

simple_start = '''
def f(x):
	return x + 1 + 2 + 1
'''

print timeit.timeit('f(10000)', setup=hof_start)
print timeit.timeit('f(10000)', setup=simple_start)

$ python hof.py 
2.32397389412
0.566710948944

Ну было бы глупо ожидать, что выдроченная сишная арифметика будет на одном уровне с пердолингом в пистонообъекты.

Получается, функции высшего порядка лучше не использовать?

Весь ФП лучше не использовать, если нужна производительность

Почему? ФП это сахар над обычной императивщиной которая в разы эффективнее гоняется на цпу.

Весь ФП лучше не использовать

А в Haskell?

P.S. протестировал на C++14 в G++. Скорость для ФВП и напрямую одинакова.

Вот мне интересно - ну выиграл вот так ты 0.1 сек, повыкидывав 1000000*4 вызовов ФПВ. Что ты там делаешь, если тебе нужна такая оптимизация?

Как насчет тестов не на арифметике, а на чем-нибудь адекватном? Сразу будет видно, что стоимостью композиции можно пренебречь?

Теперь это бессмысленных микробенчмарков тред

public static void main(String[] argv) {
        Function<Integer, Integer> f1 = (i) -> i+1;
        Function<Integer, Integer> f2 = (i) -> i+2;
        Function<Integer, Integer> f3 = (i) -> i+1;
        int iter = 10000000;
        // simple
        long startTime1 = System.currentTimeMillis();
        for(int i = 0; i < iter; i++) {
            f(i);
        }
        long endTime1 = System.currentTimeMillis();
        // hof
        long startTime2 = System.currentTimeMillis();
        for(int i = 0; i < iter; i++) {
            f1.compose(f2).compose(f3).apply(i);
        }
        long endTime2 = System.currentTimeMillis();
        System.out.format("Time elapsed simple: %d ms%n", endTime1 - startTime1);
        System.out.format("Time elapsed hof: %d ms%n", endTime2 - startTime2);
    }

    static int f(int x) {
        return x + 1 + 2 + 1;
    }

Time elapsed simple: 4 ms
Time elapsed hof: 183 ms

ПРОГРЕТЬ ЖИД не забыл?

А в Haskell?

идиоматичный хаскель не такой быстрый если сравнивать с C/C++

протестировал на C++14 в G++. Скорость для ФВП и напрямую одинакова.

Тут такое дело, там миллион оптимизаций.

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

Хорошо это или плохо - решать тебе.

Основные тормоза от compose, а не от ФВП. В Racket, насколько я видел, это уже оптимизировано давно.

#lang racket

(define (f x)
  (+ (+ (+ x 1) 2) 1))

(define f-comp
  (compose
   (lambda (x) (+ x 1))
   (lambda (x) (+ x 2))
   (lambda (x) (+ x 1))))

(define f-comp1
  (compose
   (lambda (x) (+ x 1))
   (lambda (x) (+ x 2))
   (lambda (x) (+ x 1))))

(define-syntax my-compose1
  (syntax-rules ()
    [(_)
     (lambda (x) x)]
    [(_ p0 p ...)
     (lambda (x)
       (p0 ((my-compose1 p ...) x)))]))  

(define my-comp1
  (my-compose1
   (lambda (x) (+ x 1))
   (lambda (x) (+ x 2))
   (lambda (x) (+ x 1))))

(define iter 10000000)

(define-syntax-rule (Test caption proc-id)
  (begin
    (displayln caption)
    (collect-garbage)
    (collect-garbage)
    (collect-garbage)
    (time 
     (for ([i (in-range iter)])
         (proc-id i)))))  

(Test "w/o compose" f)

(Test "using compose" f-comp)

(Test "using compose1" f-comp1)
 
(Test "using my-compose1" my-comp1)

w/o compose
cpu time: 78 real time: 89 gc time: 0
using compose
cpu time: 297 real time: 293 gc time: 0
using compose1
cpu time: 266 real time: 271 gc time: 0
using my-compose1
cpu time: 94 real time: 94 gc time: 0

(define-syntax my-compose1

Это уже не ФВП. Это макрос. Я уже писал ФВП и производительность (комментарий)

С макросами проще, но их сложнее комбинировать. Например, (apply my-compose list-of-funs) уже не сделаешь

Только тогда скорость становится уже в 10 раз, а не 1.5:

(def iter 100000000)
(defn f-comp ([x] (-> x (+ 1) (+ 2) (+ 1))))
(defn f ([x] (+ (+ (+ x 1) 2) 1)))
(time (dotimes [i iter] (f i)))
(time (dotimes [i iter] (f-comp i)))

"Elapsed time: 2946.001212 msecs"
"Elapsed time: 2829.189484 msecs"

ЧЯДНТ? Время в 10 раз больше т.к. iter в 10 раз больше.

ЧЯДНТ?

не используешь фвп

Так они ж медленнее, чем синтаксис ->.

(def f-composed (apply comp (list #(+ % 1) #(+ % 2) #(+ % 1))))
(time (dotimes [i iter] (f-composed i)))

"Elapsed time: 5827.191356 msecs"

Можно и честно с partial сделать в point-free, но нафиг? Суть в том, что синтаксис compose нифига не удобен, если у тебя не каррированные функции и этот синтаксис можно получить с той же ->. Каррировать в clojure реально, но быстрее от этого не будет.

Всё таки не думал, что ТС такой дурак

Ну дык про то и тред) ФВП тормозят, макросы, как уже сказано, не вставишь туда, куда мог бы вставить ФВП. Стройная картина в лиспах портится от этого разделения...

Хз, я не настоящий лиспер, но в clojure мне хватает сахара -> в 99% случаев, а если реально нехватает — comp есть из коробки.

Фигня это всё. Мне когда производительность нужна была, и всё дело было именно в цпу, то никакой разницы между циклами и map (точнее, map-into) я не заметил, да и компилятор превращает это дело в циклы. Вот с reduce было чуть хуже, но тоже терпимо. А писать всякие (compose f1 f2) в лиспе будет только дурачок как ТС, которому важна не программа, а какие-то его извращения. Просто в лиспе это дико неудобно

Угу. Программы пишутся для работы на машине Неймана которой уже давно не существует. Железяки пытаются притворяться этой машиной, что бы программы быстро работали.

define императивный код

А главное, почему он быстрее выполняется?

Ну вообще да, мне тоже использовать сам compose как фвп не приходилось.

В очередной раз забаненный anonimous набежал и попытался самоутвердиться.

Ну почему, иногда удобно. И симпатичней выглядит:

(map (compose f3 f2 f1)
     lst)

(map (λ (v) (f3 (f2 (f1 v))))
     lst)

Это как буква-ламбда вместо слова lambda. Лучше просто избежать этого (f1 (f2 (f3 x))) на лиспе. Честно, никогда не приходилось этим пользоваться. Просто подумать, что в твоих функциях не так, что приходится пользоваться таким паровозом.

Есть языки, где специально проходят такие трюки типа «сконструируй новую функцию из уже имеющихся». Что лисп, что хаскель тут рядом не стояли. Лисп — обычная императивщина, ну пусть и с возможностью дать функцию как аргумент другой (хотя это даже в C есть). Поэтому не стоит увлекаться всяким compose и прочим. Если что я пишу (lambda ...) или даже пользуюсь flet для удобочитаемости.

Нет, ты не угадала

Про прогрев уже сказали, но я думаю, тут еще овер дохрена времени уходит на boxing/unboxing из-за того что генерики не поддерживают примитивные типы.

Лучше просто избежать этого (f1 (f2 (f3 x))) на лиспе. Честно, никогда не приходилось этим пользоваться. Просто подумать, что в твоих функциях не так, что приходится пользоваться таким паровозом.

А если функции изкоробочные?

;; Use of `->` (the "thread-first" macro) can help make code
;; more readable by removing nesting. It can be especially
;; useful when using host methods:

;; Arguably a bit cumbersome to read:
user=> (first (.split (.replace (.toUpperCase "a b c d") "A" "X") " "))
"X"

;; Perhaps easier to read:
user=> (-> "a b c d" 
           .toUpperCase 
           (.replace "A" "X") 
           (.split " ") 
           first)
"X"

☝ из мануала по кложуре. compose делает примерно то же, что и ->, но с обратным порядком функций, без автоподстановки аргумента и обычно манипулирует с каррированными функциями (иначе он нафиг не нужен). Ну и абстрактный compose в вакууме может быть функцией, а не макросом.

В очередной раз скажу: compose в языках без автокаррирования практически не нужен в чистом виде.

Это опять же, кожура это поддерживает. А чтобы в CL сделать так же, но чтобы и универсально, и ТС не вопил «ай-ай, у меня тормозаа», надо попотеть. Так что лучше избежать этого.

В этом примере вообще нужна только часть строки до пробела. От этого надо и плясать)

Expert-level

Если еще заменить Function<Int, Int> на IntUnaryOperator, получишь раза в два быстрее. Но зачем?

производительность

haskell, lisp

Time elapsed simple: 8 ms Time elapsed hof: 270 ms Time elapsed optimized hof: 50 ms

А чтобы в CL сделать так же, но чтобы и универсально, и ТС не вопил «ай-ай, у меня тормозаа», надо попотеть. Так что лучше избежать этого.

Я даже больше скажу: у ТС с generic-версией compose оно распухнет больше исходного варианта. Потому, что как минимум там, где было (.replace "A" "X"), будет лямбда, чтобы показать, на каком месте функция .replace ждёт нужный аргумент. То же самое со .split. Избавляться от лямбд — только каррированием.

Почему в кложуре не нужны лямбды? Потому, что -> читерит и подставляет аргумент ровно там, где его ожидает 90% функций: на втором месте в форме вместо того, чтобы каррировать. Если аргумент нужен последним... есть ->>. Всё. Практично, быстро, чистый сахар. А в обычных лиспах это жутко неидиоматичный код.

Можно, конечно, эмулировать именно такое поведение, но это уже не чистый compose, а макро для вполне конкретных задач. В clojure оно называется thread through, по сути — pipe (перевёрнутый compose), в который заодно встроен аргумент. Вытащить аргумент обратно можно примерно таким clojure-сахаром: #(-> % fun1 fun2 fun3) если очень хочется (вроде того примера с map чуть выше), но на практике чаще оно нужно вместе с аргументом.

Вы еще функции каждый раз заново генерируете. Если сделать compose один раз, все еще быстрее получается.

public class AppTest {
	@Test
	public void testCompose() throws Exception {
		long start = System.currentTimeMillis();
		for(Integer i = 0; i < 10000; i++){
			simple(i);
		}
		System.out.format("Simple Time: %s \n", System.currentTimeMillis() - start);

		start = System.currentTimeMillis();
		Function f = hof();
		for(Integer i = 0; i < 10000; i++) {
			f.apply(i);
		}
		System.out.format("HOF Time: %s \n", System.currentTimeMillis() - start);

		start = System.currentTimeMillis();
		IntUnaryOperator o = oHof();
		for(int i = 0; i < 10000; i++) {
			o.applyAsInt(i);
		}
		System.out.format("O HOF Time: %s \n", System.currentTimeMillis() - start);
	}

	private Integer simple(Integer i) {
		return i + 1 + 1 + 1;
	}

	private Function hof() {
		return ((Function<Integer, Integer>)(i) -> i + 1)
			.compose((Function<Integer, Integer>) (i) -> i + 1)
			.compose((Function<Integer, Integer>)(i) -> i + 1);
	}

	private IntUnaryOperator oHof() {
		return ((IntUnaryOperator) i -> i + 1)
			.compose(i -> i + 1)
			.compose(i -> i + 1);
	}
}

Simple Time: 7 
HOF Time: 95 
O HOF Time: 24 

Да, забавный язык

Просто подумать, что в твоих функциях не так, что приходится пользоваться таким паровозом

Я бы сказал наоборот, с ними как раз все так. Программа разделенная на маленькие функции которые потом вот так собираешь. И код-реюз в подарок.

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

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

Теперь еще и жависты налетели со своим боксингом до кучи.