Racket Scheme. Разделить каждый элемент первого списка на каждый элемент второго списка.

man map

map

Ему не поэлементно надо, а все перестановки. Каждый поделить на каждый. Хотя map внутри map вероятно поможет.

Получился такой код.

(define pa/pb
  (lambda (lst1 lst2)
    (if (null? lst1)
        lst2
        (if (null? lst2)
            lst1
            (cons (/ (car lst1) (car lst2))
                  (pa/pb (cdr lst1) (cdr lst2))
                  )
            )
        )
    )
  )

Теперь возник новый вопрос, как сделать так, что в ответе были результаты деления двух списков и они же, но уже со знаком минус. Т.е, если результат деления списка на список (1 2 3 6), то мне надо, чтобы на выходе было как-то так (1 2 3 6 -1 -2 -3 -6).

map и append, вероятно.

Декартово произведение? В рэкете нет cartesian-product?

Гугл говорит, что есть https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._cartesian-product%29%29

Потом каждую пару-список поделить

Американцы «Поехали!»

(define xs '(1 2 3))
(define ys '(3 2 1))

;; divide all the elements of xs by all the elements of ys
(define cartesian-division
  (lambda (xs ys)
    (flatten (map (lambda (x)
                    (map (lambda (y)
                           (/ x y)) ys)) xs))))

;; negate all the elements of xs and append them to xs
(define negate-and-append
  (lambda (xs)
    (let ((negated-xs (map - xs)))
          (append xs negated-xs))))

(negate-and-append (cartesian-division xs ys))

Неужели в наших вузах где-то учат лиспам?

В рэкете нет cartesian-product?

Все там есть.

(define cartesian-division-1
  (lambda (xs ys)
    (map (lambda (pair)
           (apply / pair))
         (cartesian-product xs ys))))

Судя по этой реализации, декартово произведение вообще не нужно, тупо поэлементное деление. Если списки неодинаковой длины, лишние элементы добавляются в результат как есть.

Учитывая, что map в ракете не умеет в списки разной длины, рекурсивное решение выглядит вполне по-царски.

Все там есть.

cartesian-division

Даже есть «декартово деление»! Сам придумал, иль кто подсказал?

Лучше бы написал (define cartesian-product-1 (lambda (product-func xs ys) ... )), где product-func будет собирать «произведение»: умножать, делитьб соединять и тд и тп.

Даже есть «декартово деление»! Сам придумал, иль кто подсказал?

Надо же было как-то функцию назвать %)

Лучше бы написал (define cartesian-product-1

Слушаюсь и повинуюсь, о Волька ибн Алеша.

(define cartesian-product-1
  (lambda (f xs ys)
    (map (lambda (pair)
           (apply f pair))
         (cartesian-product xs ys))))

А для произвольного количества списков?

А для произвольного количества списков?

Трах-тибидох!

(define cartesian-product-2
  (lambda (f xs ys . rest)
    (map (lambda (pair)
           (apply f pair))
         (apply cartesian-product
                (append (list xs ys) rest)))))

(cartesian-product '(1 2) '(3 4) '(5 6))
;; => '((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))

(cartesian-product-2 max '(1 2) '(3 4) '(5 6))
;; => '(5 6 5 6 5 6 5 6)

Теперь пулл-реквест рэкетирам на «правильную» версию декартово произведения.

Теперь пулл-реквест рэкетирам на «правильную» версию декартово произведения.

Я думал, теперь будет «снять ограничение на минимум два списка» %) А то

(cartesian-product)
;; => '(())

Но на сегодня магия иссякла.

Я думал, теперь будет «снять ограничение на минимум два списка»

В ходе обсуждения пул-реквеста договоритесь, что и как должно быть там внутрях.

Учат-учат, сижу, ковыряюсь. Спасибо за Вашу помощь!

Декартово произведение

Не эффективно. И так нужно M*N делений, так зачем ещё память тратить и лишний цикл наворачивать?

Декартово произведение

Не эффективно.

Ты не лиспер. Лиспер не думает про эффективность, он думает по эффектность. Про эффективность пусть «компилятор» думает, чай не только хвостовые рекурсии умеет оптимизировать.

Если всё таки нужна эффективность, я уже предложил написать «правильную» версию декартово произведения.

Лиспер не думает про эффективность, он думает по эффектность

Ты не путай, это хачкелисты. Тру-лисп это хаки уровня Си+ассемблер.

Это третий такой за неделю.

Тру-лисп это хаки уровня Си+ассемблер.

Это макрос/дсл на макросе/дсле макросом/дслем погоняет. ДСЛем вполне может быть эффектная пародия на какой-нибудь хацкерский язык.

Лиспер не думает про эффективность

Лиспер думает про обобщенную эффективность, а не подгон под детали реализации конкретного вычислителя.

обобщенную эффективность

Перевожу с русского на русский - «эффектность».

Нет обощенной эффективности. Есть конкретный результат за определенные потраченные ресурсы. И зависит от того какой результат нужен, и какие есть ресурсы.

Личный вопрос, раз тема уже съехала: ты случаем не «эффективный менеджер»?

Нет обощенной эффективности. Есть конкретный результат за определенные потраченные ресурсы.

Ну как нет. Алгоритм с вычислительной сложностью О(n) в общем случае эффективнее алгоритма со сложностью O(n!), не так ли? Но в каждом конкретном случае могут быть свои нюансы.

ты случаем не «эффективный менеджер»

С какой целью интересуешься?

О(n) в общем случае

О-нотация - это не про общий случай, а про асимтотику, когда n стремится к определенной точке, и не обязательно к бесконечности.

обобщенную эффективность

такого не существует. на gpu эффективно совсем другое чем однопоточная поделка, которую обычно лепят для код гольфа и её нужно будет полностью переделывать

О-нотация - это не про общий случай

Когда я говорю «в общем случае», я имею в виду «для всех алгоритмов с одинаковой сложностью независимо от конкретной реализации (константы, множители и прочее)». Для всех алгоритмов с вычислительной сложностью O(n) затраты времени растут медленнее, чем для О(n!) -> такие алгоритмы в общем случае (для любой выбранной пары конкретных алгоритмов) эффективнее. Эн факториал с ростом n рано или поздно всосет.

Успеет ли этот момент наступить в конкретном юзкейсе (частном случае) — это уже совсем другой вопрос.

на gpu эффективно совсем другое чем однопоточная поделка

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

Это ведь не значит, что О(n!) в конце концов не всосет у О(n) на одном и том же вычислителе — хоть на GPU, хоть на чем, не так ли? %)

Шо, в Scheme не придумали zip?

Когда я говорю «в общем случае», я имею в виду «…»

Подмена цели.

Для всех алгоритмов с вычислительной сложностью O(n)

О-нотация - это всего лишь одно из отображений сложности алгоритма. У тебя еще более частный случай - сложность по времени работы алгоритма.

растут медленнее -> эффективнее

Помена «общей» цели конкретной.

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

А как бы здесь помог zip? Он каждый с каждым не сопоставляет.

Когда я говорю «в общем случае», я имею в виду «для всех алгоритмов с одинаковой сложностью независимо от конкретной реализации (константы, множители и прочее)». Для всех алгоритмов с вычислительной сложностью O(n) затраты времени растут медленнее, чем для О(n!) -> такие алгоритмы в общем случае (для любой выбранной пары конкретных алгоритмов) эффективнее. Эн факториал с ростом n рано или поздно всосет.

Только с математической точки зрения. Вот есть алгоритм Копперсмита—Винограда. Умножает матрицы с вычислительной сложностью O(n^2.3755). Но для всех применяемых случаев умножения матриц он медленнее. «Рано или поздно» для него наступает только когда размеры матриц превышают терабайты.

Если хочешь более математично

Не хочу, я не математик. Меня больше интересуют задачи практические, чем теоретические.

А как бы здесь помог zip? Он каждый с каждым не сопоставляет.

>>> a = [1, 2, 3, 4, 5]
>>> b = [6, 7, 8, 9]
>>> list(map(lambda x: x[0]/x[1], (zip(a,b))))
[0.16666666666666666, 0.2857142857142857, 0.375, 0.4444444444444444]

upd:

Ему не поэлементно надо, а все перестановки

ууу, я тред не читал

upd2:

хорошо, когда есть стандартные библиотеки

>>> from itertools import product
>>> a = [1, 2, 3, 4, 5]
>>> b = [6, 7, 8, 9]
>>> c = list(map(lambda x: x[0]/x[1], (product(a,b))))
>>> len(a)
5
>>> len(b)
4
>>> len(c)
20
>>> c
[0.16666666666666666, 0.14285714285714285, 0.125, 0.1111111111111111, 0.3333333333333333, 0.2857142857142857, 0.25, 0.2222222222222222, 0.5, 0.42857142857142855, 0.375, 0.3333333333333333, 0.6666666666666666, 0.5714285714285714, 0.5, 0.4444444444444444, 0.8333333333333334, 0.7142857142857143, 0.625, 0.5555555555555556]

https://github.com/python/cpython/blob/2b201369b435a4266bda5b895e3b615dbe28ea6e/Modules/itertoolsmodule.c#L2094 прям видно, что ребята старались. Сразу выделяют под весь результат память и фигачат перебором.

list(map(lambda x: x[0]/x[1], (zip(a,b))))

#lang racket
(define a '(1 2 3 4 5))
(define b '(6 7 8 9))
(for/list ([x a] [y b]) (/ x y))
; => '(1/6 2/7 3/8 4/9)

Если очень хочется можно и zip

#lang racket
(require srfi/1)
(define a '(1 2 3 4 5))
(define b '(6 7 8 9))
(map (curry apply /) (zip a b))

Или даже

#lang python
a = [1, 2, 3, 4, 5]
b = [6, 7, 8, 9]

> map(lambda x: x[0]*1.0/x[1], zip(a,b))
[0.16666666666666666, 0.2857142857142857, 0.375, 0.4444444444444444]

Чем дольше я читаю тред, тем меньше понимаю, что хочет ТС :(

Я, конечно, в Racket Scheme ни ногой, но просто интересно понять, из какой серии вопрос - об идее алгоритма, синтаксических конструкциях схемы, библиотечных функциях или о чём-то ещё.

Давайте немного поворошим картезианское логово:

> (define a '(1 2 3 4))
> (define b '(10 100))
> (append-map (lambda (x) (map ((curry *) x) a)) b)
'(10 20 30 40 100 200 300 400)

Шо, в Scheme не придумали zip?

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

xорошо когда нет залитых эпоксидкой «функциональных» библиотек

(define (pa/pb la lb)
  (define (rec r e l)
    (if (null? l)
	r
	(rec (cons (/ e (car l)) r)
	     e
	     (cdr l)
	     )
	)
    )
  (define (rec* r a)
    (if (null? a)
	(reverse r)
       	(rec* (rec r (car a) lb)
	      (cdr a)
	      )
	    )
	)
  (rec* '() la)
  )

> (begin
   (define r (pa/pb '(1 2 3 4 5) '(6 7 8 9)))
   (display (length r)) (newline)
   r)

20
(1/6 1/7 1/8 1/9 1/3 2/7 1/4 2/9 1/2 3/7 3/8 1/3 
2/3 4/7 1/2                                     
     4/9 5/6 5/7 5/8 5/9)

Python вообще классный язык, мне очень «нравится».

Бог с ним с лямбдами, кому нужна эта лапша.

А как расширить стек под рекурсию(?) - очень просто - нужно всего лишь пересобрать интерпретатор.

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

Такие алгоритмы называют галактическими, даже статья в википедии есть, скудная, правда.

расширить стек под рекурсию

Лучше зайти с парадного входа и переписать на циклах.

на циклах вложенные структуры произвольной глубины обходить, да и еще с какой-то логикой - очень весело.

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

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

ну правильно, через явный стек, яж говорю - весело.

А что было придумано специально для компьютеров? Машина Тьюринга, как модель? Рекурсия очевидна как абстракция композиции, и там где диктуется - компилятор все ожидаемо оптимизирует, не дороже цикла в лоб.

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

А что было придумано специально для компьютеров

Вычислительная математика.

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

вычислительная математика

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

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

Очень давно оптимизирует в большинстве компиляторов Common Lisp, хотя циклы там есть. Современный GCC тоже оптимизирует.