Рекурсия в Haskell

есть ли она там вообще?

Нет, нету. Только goto.

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

Можете объяснить по какому принципу работает рекурсия в Haskell, и есть ли она там вообще?

В принципе, всё можно свести к волшебной функции fix :: (a -> a) -> a. Как-то так, например:

> import Data.Function (fix)
> fact = fix $ \f n -> if n == 0 then 1 else n * f (pred n)
> fact 5
120

Есть ли с стек в Haskell? Пока это основное, что меня интересует.

Но ведь для знакомства с языком это совершенно не важно.

Нет, нету. Только goto.

А больше и не нужно.

Спасибо всем, кто откликнулся, и объяснил.

всё можно свести к волшебной функции fix :: (a -> a) -> a.

Молодец, свёл всё к Y-комбинатору. Вот так всегда с вами функциональщиками.

хвостовая рекурсия оптимизируется компилятором в обычный цикл

А древовидная?

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

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

По теме.

Итого. Рекурсия есть. Стек тоже есть. Еще есть _настоящая_ оптимизация хвостового вызова (Tail Call Optimisation - TCO). До кучи еще есть и ленивая стратегия вычисления благодаря тому, что язык ссылочно-прозрачный.

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

Язык лучше изучать не в интернете, а читая книги. Не так давно для начинающих вышла отличная книга «Get Programming with Haskell», которая переведена на русский одним очень уважаемым хаскелистом и преподавателем (а не переводчиком, далеким от программирования).

Если вкратце. В Haskell есть такая крутая штука как недоопределённые значения. То есть: как значение в целом, так и любая часть его может быть undefined. Например, пара (Int, String) может быть undefined, может быть (undefined, undefined), может быть (undefined, «foo») или (42, undefined) — и это всё разные, допустимые значения. При этом ты можешь, скажем, вычислить fst (42, undefined) — оно вернёт 42, а не ошибку.

Теперь про рекурсию. Если у тебя есть рекурсивно заданная переменная, вроде let x = f x, то компилятор вычислит некоторое значение, для которого это равенство (x = f x) выполняется. В принципе, компилятор должен бы вычислять наименее определённое значение, но в целях оптимизации ему разрешено вычислять немного больше, если от этого гарантированно не меняется семантика (в частности, не кидаются исключения).

В теории это делается так: сначала вместо x подставляется undefined, потом последовательно вычисляется f undefined, f (f undefined), f (f (f undefined)) и так далее. Наименьшее подходящее значение — это предел этой последовательности. На самом деле, конечно, вычисления гораздо более эффективны.

Например, если ты напишешь

let (a, b) = (b+1, 1)

то пара (a, b) вычисляется как undefined => (undefined, undefined) => (undefined, 1) => (2, 1). Готово.

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

f 0 = 1
f n = n * f (n-1)

то функция f вычисляется так: undefined => {_ -> undefined} => {0 -> 1, _ -> undefined} => {0 -> 1, 1 -> 1, _ -> undefined} => {0 -> 1, 1 -> 1, 2 -> 2, _ -> undefined} => {0 -> 1, 1 -> 1, 2 -> 2, 3 -> 6, _ -> undefined} и так далее. Процесс никогда не заканчивается, но на практике это и не нужно: компилятор вычислит ровно столько, сколько нужно, и если ты запросишь f 3, то дальше вычисления не пойдут.

Ты смешал в одну кучу bottom и thunk.

Нет.

Я более-менее пересказал теорему Клини о неподвижной точке.

пара (a, b) вычисляется как undefined => (undefined, undefined) => (undefined, 1) => (2, 1). Готово.

А это что?

Это теорема Клини.

А зачем?) Человек явно не подготовлен для этого. И спрашивал он совсем другое, самые основы программирования.

Ничего, вредно не будет. Возможно, задумается, что, кроме операционной семантики, есть что-то ещё. А то стеки всякие…

Я к тому, что undefined в хацкелле имеет весьма конкретное значение: bottom. Так ты только запутаешь человека, который полезет это гуглить.

Проходил мимо, увидел вопиющее вранье, врываюсь.

Например, в Scala нет полноценной оптимизации хвостовой рекурсии, и, скорее всего, никогда там не будет.

В джаву завозят lightweight threads, поэтому все будет обмазано cps, поэтому вменяемую поддержку можно ждать в ближайшем будущем, которое обещает быть непременно светлым. Вот так! :)

Я к тому, что undefined в хацкелле имеет весьма конкретное значение: bottom.

Ну, строго говоря, это не совсем так, но я решил, что undefined будет понятнее, чем bottom. И да, именно это я и имел в виду. fix f — это именно что предел (верхний) последовательности bottom, f(bottom), f(f(bottom)), f(f(f(bottom))) etc.

CPS — это способ сделать любую рекурсию хвостовой. К оптимизации хвостовой рекурсии оно имеет слабое отношение. Или ты хочешь сказать, что, раз они делают CPS во все края, то и хвостовую рекурсию будут вынуждены оптимизировать нормально?

Да. cps я зря сказал, не будет явного точно, но delimited continuations завезут, но и это ни при чем тоже, просто в кучу докинул.

We envision tail-call elimination that pops one or perhaps even an arbitrary number of stack frames at explicitly marked call-sites. It is not the intention of this project to implement automatic tail-call optimization.

The implementation of this feature requires cross-cutting changes to the VM, VM specification (bytecode), and possibly the front-end Java compiler (javac). As a result, in order not to delay the completion of continuations and fibers, we will only begin specifying and implementing this feature only when the project is at a more advanced phase.

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

CPS — это способ сделать любую рекурсию хвостовой. К оптимизации хвостовой рекурсии оно имеет слабое отношение.

Связаны. Собственно, TCO и нужен для CPS.

В Scala сейчас этого нет. Отсутствие TCO - главная причина, почему в Scala задеприкейтили плагин «продолжений», который не шмог в банальный бесконечный цикл по while, сжирая весь стек вместо того, чтобы работать ровно, бесконечно долго, но ровно, что было бы в случае TCO. У Одерского статья была на эту тему.

Поживем - увидим (C)

goto не первичен, это расхожее заблуждение. Первичен именно цикл, потому что в первом компьютере в истории доктора Ко́нрада Эрнста О́тто Цу́зе применялась зацикленная перфорированная пленка. Goto обеспечивался односторонней прокруткой цикла инструкций

Y-комбинатор Это мракобесие, y-комбинатор невозможен. Нечто из разряда вытаскивания барона Мюнхгаузена за волосы из болота. Просто мошеннический финт

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

Нечто из разряда вытаскивания барона Мюнхгаузена за волосы из болота

А мат. индукция?

Тот же софизм.

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

А мат. индукция?

Тот же софизм.

Можно показать, где там ошибка/противоречие?

там догма из символа веры. Священная вера в то что дедукция = индукция из того что дедуктивно определяемое милостию божьей объявляется априорным

что дедуктивно индуктивно/fixed

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

Поэтому просто подменяются понятия

Хотя, может быть проблема тут даже не в «точности». Нормальный ход познания: индукция(опыт)->обобщение далее обобщение(универсалия) как источник готового знания служит в применении к частному. Но номиналист не хочет признавать универсалию как реальную сущность. Соответственно ступень от частного к общему он хочет замести под ковер. Если разрешить нормальный принцип познания, означенный выше, придется отказаться от догматического подхода, и вытащить Джордано Бруно из костра инквизиции

там догма из символа веры.

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

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

Предположим, мы хотим понять, являются ли все числа простыми. Берём 1 - простое, берём 2 - простое, берём 3 - простое, ну а дальше по индукции все числа простые…

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

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

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

Да уже надеемся! Хочется уже на каждом углу кричать, что на jvm завезли годноты в кои-то веки. Правда, сложно сказать, как получится так пропатчить VM, чтобы была и поддержка этого, и не поломалась совместимость. Мастодонты с java 6 начнут ворчать :)

О, вот и торсионщики подтянулись.

Но вот на тотализаторе уже не выйдет этот фокус:)

Потому что за тотализатором стоят иллюминаты и сверхъестественные силы природы?

Иногда бытуют клинические случаи. К примеру, математик объявляет импликацию «если X то Y» = True, при любых значениях переменных. Это у него может «вылиться» в «парадокс», типа «если X верно то русалки существуют».

Потому что там все немного сложней, чем может незатейливый мозг игрунчика в моделирование коней в вакууме

А иллюминатов там тоже учитывать надо, между прочим. А что такое «сверхъестественные силы природы»? Что то вроде понятия фикции в современной математизированной квазифизики? Когда например говорят, что наблюдаемой центробежной силы нет, а спекулятивная центростремительная есть? Какая из этих сил сверхъестественна?

Впрочем современная физика наблюдаемые силы вообще отрицает.

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

А зачем?)

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

-- Другие причины есть, конечно. Но эта прямо прет из некоторых.

Затем, что это , на мой взгляд, единственный язык программирования, который вообще не предназначен для зарабатывания денег. Хочется иногда прикоснуться к чему то некорыстному.

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

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

Господи, ну что за чушь.

Haskell - конечно, больше академический язык, и больше для ботанов, чем C++, но поговаривают, что на Haskell тоже зарабатывают деньги. Крипта там всякая, еще что-то. А современная мода на микросервисы вполне позволяет использовать самые разные языки, где найдется место и для Haskell.

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