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

EDIT My original post also prevented GCC from actually doing tail call eliminations. I’ve added some additional trickiness below that fools GCC into doing tail call elimination anyways

Ну ты понял. Может оптимизирует, а может ты немного поменяешь логику и получишь переполнение стека. И ради чего это? Просто чтобы цикл не использовать?

Может оптимизирует, а может ты немного поменяешь логику и получишь переполнение стека.

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

И ради чего это? Просто чтобы цикл не использовать?

Для некоторых алгоритмов (например, обход дерева) рекурсивный алгоритм намного проще и красивее реализации через цикл.

                )
	    )
	)

Зашто.

за читаемость, я в курсе что «надо» лепить батарею скобок, но по личному-субъективному я за си-стайл.

читаемость

Ни хрена же не помогает, только вертикальное пространство жрет и бесит %)

По отступам все прекрасно видно, а еще бывают разноцветные скобочки в нормальных редакторах.

Так это не фп языки, в sbcl tco не по стандарту и включается тоже что-то вроде с (safety 0). В каком-нибудь с++ если и используется рекурсия, то глубиной не больше пары десятков, и это нормально, больше и ненужно, хвостовой вызов не нужен, и скорее всего по логике не получится. В фп же рекурсия диктуется семантикой, а конструкции циклов выглядели бы как нелепый синтактический сахар.

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

Цветные скобки типа rainbow-delimiters это просто разноцветная клоунада. Фjрма скобок может помочь, но не сильно. И вообще я склонен к написанию лёгких на скобки макросов. Например let/let*-формs - это же тихий ужас. Не удивительно, что люди не любят лисповый синтаксис, операция объявления, ‘присваивания’ одна из самых частых, а тут тебя заствляют писать минимум две пары скобок и с отступом!.

Для некоторых алгоритмов […] рекурсивный алгоритм намного проще и красивее реализации через цикл

ну да, математика это очень красиво. Но в программах-то память не бесконечная. А если вспомнить, что tco не включится, если не закодировать эту рекурсию определённым образом? Как ты сам сказал, кто-то добавит деструктор и в совершенно другом месте программы твоя рекурсия превратиться в переполнение стека.

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

Форма скобок может помочь

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

В каком-нибудь с++ если и используется рекурсия, то глубиной не больше пары десятков

А потом мамкин какер исследователь безопасности даст тебе на вход несбалансирвоанное дерево с 300k уровней.

больше и ненужно по логике не получится

рекурсия это когда глубина стека вызовов зависит не от логики, а от размера входных данных (с поправкой на tco). А «пара десятков по логике» это как раз без рекурсии и бывает.

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

кто-то добавит деструктор и в совершенно другом месте программы твоя рекурсия превратиться в переполнение стека

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

Ну да, если кто-то не в здравом уме подсунет вырожденное дерево, а потом императивщики и пишут, что рекурсия это такая академическая забава. А ещё жалуются что в их императивных языках tco может «случайно сломаться», и опять пишут что рекурсия это академическая забава. В фп же рекурсия это альфа и омега, и гарантия компилятора на оптимизацию - это ГАРАНТИЯ компилятора.

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

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

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

В фп же рекурсия это альфа и омега, и гарантия компилятора на оптимизацию - это ГАРАНТИЯ компилятора.

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

fib(n):
  if n==0: 0
  else if n==1: 1
  else: fib(n-1) + fib(n-2)

Какие ГАРАНТИИ даёт сферический в вакууме компилятор для оптимизации этой функции?

Гарантии оптимизации хвостового вызова, естественно. И фибоначи можо и нужно записать через хвостовой вызов.

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

Посыл за рекурсию(хвостовую в том числе) был в том что, через неё реально проще и лаконичнее писать соответствующие алгоритмы, в том числе в императивных языках(естественно с предсказуемой глубиной, и пониманием того что память не бесконечна). Конкретно циклы, даже через tco в императивных языках писать конечно же не надо.

Я согласен, что именно в питоне tco бы ничего не дало, язык слишком медленный, и не фп в реализации

Есть реализация питона на Racket.

#lang python

def fib(n):
  def fibr(k,r1,r2):
    r = r1+r2
    if k==n:
      return r
    else:
      return fibr(k+1,r,r1)
  if n==0: return 0
  elif n==1: return 1
  else: return fibr(2,1,0)

даёт гарантированную хвостовую оптимизацию.

Я согласен, что именно в питоне tco бы ничего не дало, язык слишком медленный, и не фп в реализации.

В смысле, не ФП? Всё, что требуется для реализации функционального программирования, там есть: функции высшего порядка, замыкания, сборка мусора, модуль functools.

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

Haskell (куда уж дальше в ФП?). Вот цикл:

forM [1..10] $ \i -> do
  putStrLn $ show $ i+k

Также есть whileM и untilM

И так нужно M*N делений

Если я правильно понял, что хочет ТС, то достаточно N делений + M умножение. Мы же каждый элемент 1-го списка делим всегда на одни и теже числа. Поэтому достаточно один раз перемножить все элементы 2-го списка, а потом на полученный результат делить элементы из 1.

Поэтому достаточно один раз перемножить все элементы 2-го списка, а потом на полученный результат делить элементы из 1

Я так понял, что ему нужно поделить каждый на каждый, а не каждый на все.

В смысле, не ФП? Всё, что требуется для реализации функционального программирования, там есть: функции высшего порядка, замыкания, сборка мусора, модуль functools.

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

Haskell (куда уж дальше в ФП?). Вот цикл:

forM [1..10] $ \i -> do
  putStrLn $ show $ i+k

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

Также есть whileM и untilM

я кстати как увидел(понял что нужно использовать mapM), совсем отвратился от хаскеля. Я думаю проблема монад в хаскеле, это то что они ведь по сути под капотом, ими просто предлагают пользоваться, но как они реализованы не прочувствуешь. Понятно что «монада» во многом это лишь сахар, никто руками их в коде писать не будет, и всякие fooM тупо похожи на костыль. А вот ситуация объяснения монад(1001 гайд по манадам в хаскеле) явно усугубляется системой типов. Почти все гуру монад пытаются приплести систему типов при объяснении монад. И по сути «на пальцах» обясняют лишь специфику монад в хаскеле и то как ими пользоваться, забывая напрочь что монады это прежде всего о композиции, и только потом каки-то там гарантии типизации.

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

Ничего не понял. Рекурсия и цикл друга в друга превращаются макросами. set! я могу сделать хоть в цикле, хоть в рекурсии.

(define i 0)
(for ([n 10])
  (set! i (+ i n)))

и

(define i 0)
(let loop ([n 1])
  (set! i (+ i n))
  (when (< n 10) (loop n)))

чем принципиально отличаются?

любой цикл как форма не имеет просто смысла. Всеравно имеем выражение(которое что-то возращает).

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

функция fold как раз является самым общим примером цикла.

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

Циклы от рекурсии отличаются

Сперва надо дать определение цикла и рекурсии, потом искать различие.

Так я это и хотел написать. Мы сейчас в общемто забрели в разговоры ни очём. Изначально мой посыл был в том, что синтактические конструкции циклов в фп языках выглядят нелепо, хотябы потому что их можно представить кучей способов, и естественно в нормальном фп языке в основе реализации(тс семантической) будет лежать рекурсия, а как оно реализовано в рантайме - вообще никого не должно волновать, потому что оно может быть реализовано эффективно при должном внимании и стараниях(chez scheme, ocaml, mlton).

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

Исходники всех монад кроме IO доступны. Там ничего сложного. Например, для списка:

instance Applicative [] where
    pure x    = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
    liftA2 f xs ys = [f x y | x <- xs, y <- ys]
    xs *> ys  = [y | _ <- xs, y <- ys]

instance Monad []  where
    xs >>= f             = [y | x <- xs, y <- f x]
    (>>) = (*>)

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

???

Монада — это любая фигня, для которой определены операции >>= и return и выполняются три закона:

return a >>= f ≡ f a
m >>= return ≡ m
(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

Всё. Что именно подразумевается под >>= и return абсолютно неважно.

и выполняются три закона

И кто следит за исполнением этих 3 законов роботомонадотехники?

return a >>= f ≡ f a
m >>= return ≡ m
(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

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

Монада — это любая фигня, для которой определены операции >>= и return

Сколько ни пытался врубиться в эти ваши монады — без толку. Видимо, я тупой.

даёт гарантированную хвостовую оптимизацию.

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

Если уж ты так любишь рекурсию, то вот так будет работать намного лучше. И красиво, и понятно, и вычислений меньше (ценой памяти, кончено), и сломать оптимизацию куда сложнее, ведь она записана явным образом

from functools import lru_cache

@lru_cache()
def fib3(n):
  if n==0: return 0
  if n==1: return 1
  return fib(n-1) + fib(n-2)

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

Поэтому лучше всего записать вот так:

def fib(n): 
  if n==0: return 0
  [a, b] = [0, 1]
  for _ in range(n-1):
    [a, b] = [b, a+b]
  return b

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

А в более реалистичном варианте, текущее значение зависит от следующих (обход дерева, ага) и такой трюк не прокатит (как и твой).

И дерево можно обойти через хвостовую рекурсию. В чем проблема? Уже написали что рекурсией, хвостовой, проще, намного, чем городить стек с циклом и стоодной проверкой.

и сломать оптимизацию куда сложнее

В нормальном фп интерпретаторе/компиляторе ничего сломать нельзя, там иммутабельность и копирование, указателей нет. И нормальный, не писаный за два дня на коленке рантайм оптимизирует один в один рекурсию, как если бы она была записана подобным образом:

def fib(n): 
  if n==0: return 0
  [a, b] = [0, 1]
  for _ in range(n-1):
    [a, b] = [b, a+b]
  return b

не сложнее чем увидеть хвостовой вызов

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

мистический декоратор

для мемоизации

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

свопы

Уж точно понятнее, чем fibr с тремя агрументами. Ну, а вобще это специфика числовых рядов.

от себя добавлю нередкую необходимость явного копирования

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

В нормальном фп интерпретаторе/компиляторе ничего сломать нельзя нормальный, не писаный за два дня на коленке рантайм оптимизирует

Ну конечно, и проблему остановки он тоже умеет решать. Он же не на коленке писан. Он нормальный. Ну, а если не умеет, то значит не нормальный, ты не про этот говорил.

Ну конечно, и проблему остановки он тоже умеет решать. Он же не на коленке писан. Он нормальный. Ну, а если не умеет, то значит не нормальный, ты не про этот говорил.

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

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

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

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

И кто следит за исполнением этих 3 законов роботомонадотехники?

Тот, кто определяет операции >>= и return.

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

Так в том-то и дело, что монада не совсем свёртка с контекстом. Свёртка с контекстом всего лишь одна из операций — foldM. И для свёртки не требуется, чтобы объект был монадой. Достаточно, чтобы он был Foldable.

Вот возьмём монаду списка. Что в ней контекст, что вычисление?

do { x <- [1,2,3]; y<-[5,6,7]; return $ x+y }

вернёт [6,7,8,7,8,9,8,9,10].

Суть монады — не свёртка, а контейнер. Если это монада списка, в ней список, если Maybe — одно значение или пусто, если IO — действие.

И красиво, и понятно, и вычислений меньше (ценой памяти, кончено)

Больше же. Положить в кэш и достать из кэша явно дороже, чем выполнить одно сложение.

Поэтому лучше всего записать вот так:

Разумеется. Но вот перепиши «вот так»

def dotree(t, f):
  f(t.v)
  dotree(t.left, f)
  dotree(t.right, f)

Хвостовая рекурсия автоматически половину вызовов превратит в хвостовые.

И нормальный, не писаный за два дня на коленке рантайм

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

Вот возьмём монаду списка. Что в ней контекст, что вычисление?

do { x <- [1,2,3]; y<-[5,6,7]; return $ x+y } вернёт [6,7,8,7,8,9,8,9,10].

так я ж написал, не дословно конечно, что свертка это частный случай.

Конкретно в примере с do, что я здесь вижу, не считая прегруженного «+»: я вижу аналог let*, который - цепочка вложенных замыканий(список), и тн присваивание это всего лишь шейдинг переменных, только важная деталь всего этого, то что let* - макрос, те сахар, и все вместе это ведь можно назвать монадой, если это называется монадой в хаскеле. Не нужно законов, специальной терминологии, это и есть более менее объяснение на пальцах

не считая прегруженного «+»

Он не перегружен. Здесь нормальный арифметический.

Можно без плюса

do { x <- [1,2,3]; y<-[5,6,7]; return (x,y) }
==
[(1,5),(1,6),(1,7),(2,5),(2,6),(2,7),(3,5),(3,6),(3,7)]

я вижу аналог let*, который - цепочка вложенных замыканий(список)

Попробуй переписать через let*.

половину вызовов превратит в хвостовые

а вторая половина вызовов сможет привести к переполнению стека?

Сможет, если стек ограничен. В Racket, например, стек ограничен только адресным пространством, то есть переполнение невозможно.

Половина не половина, а высота дерева. А теперь попробуй реализовать обход (бинарного) дерева без стека (магазина).

стек ограничен только адресным пространством

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

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

В Racket, например, стек ограничен только адресным пространством, то есть переполнение невозможно.

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

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

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

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

А теперь попробуй реализовать обход (бинарного) дерева без стека (магазина).

А теперь попробуй ходить без ног.

А смысл? Ну, допустим, в некоторых рантаймах насирание фреймами в стеке будет быстрее, чем создание своего стека в куче. Но если там не сделана защита от переполнения, то такой алгоритм всё равно работать не будет. А если сделана, то работать быстрее будет только на каких-то размерностях задач. Допустим, даже, на наиболее востребованных. Но человек, который это понимал и поддерживал, потом перейдёт в другую компанию, на его место наймут людей, которые уже не будут знать этих нюансов, а размерности возрастут и всё это загнётся под нагрузкой. И другие разработчики начнут переписывать всё с нуля.

Ну, и нет никаких гарантий (кроме «нормальности» и «ненаколенности» компилятора), что ваш рекурсивный алгоритм вообще превратится в цикл за счёт tco, в то время как вы сами могли бы сделать это вручную.

Для Scheme (и его потомков) есть. Собственно, там не tco, а tce (tail-call elimination), так как среда исполнения не «может оптимизировать», а «обязана удалить хвостовой вызов» по семантике языка.

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

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

Сойдёмся мы на таком мнении?