Почему являются не рекурсивными функции в Ocaml/F# по умолчанию?

Question

Почему являются не рекурсивными функции в Ocaml/F# по умолчанию?

Я использую Rails 4, и следующее решение сработало для меня, так как я не хочу запускать вручную rake db:session:clear каждый раз, когда запускаю свое приложение.

Внутри /config/initializer/session_store.rb добавьте следующее

ActiveRecord::SessionStore::Session.delete_all

Это то же самое, что и команда rake, но выполняется на уровне инициализатора.

90

f# recursion ocaml

задан nsantorello 23 May 2009 в 00:59

5 ответов

There are two key reasons this is a good idea:

First, if you enable recursive definitions then you can't refer to a previous binding of a value of the same name. This is often a useful idiom when you are doing something like extending an existing module.

Second, recursive values, and especially sets of mutually recursive values, are much harder to reason about then are definitions that proceed in order, each new definition building on top of what has been already defined. It is nice when reading such code to have the guarantee that, except for definitions explicitly marked as recursive, new definitions can only refer to previous definitions.

10

ответ дан 24 November 2019 в 07:04

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

Если у вас есть определение let fx = x , вы ожидаете, что оно будет иметь тип 'a ->' a и будет применяться к различным типам 'a в разных точках. Но в равной степени, если вы напишете let gx = (x + 1) + ... , вы ' d ожидать, что x будет рассматриваться как int в остальной части тела g .

То, как вывод Хиндли-Милнера учитывает это различие осуществляется через явный шаг обобщения . В определенные моменты при обработке вашей программы система типов останавливается и говорит: «Хорошо, типы этих определений будут обобщены на этом этапе, так что когда кто-то их использует, любые переменные свободного типа в их типе будут только что и, следовательно, не будет мешать любому другому использованию этого определения ».

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

Итак, учитывая, что средство проверки типов должно знать, какие наборы определений являются взаимно рекурсивными, что он может сделать? Одна из возможностей - просто провести анализ зависимостей для всех определений в области видимости и переупорядочить их по минимально возможным группам. На самом деле Haskell делает это, но для таких языков, как F # (и OCaml и SML), которые имеют неограниченные побочные эффекты, это плохая идея, потому что это может также изменить порядок побочных эффектов. Поэтому вместо этого он просит пользователя явно отметить, какие определения являются взаимно рекурсивными, и, следовательно, по расширению, где должно произойти обобщение.

учитывая, что средство проверки типов должно знать, какие наборы определений являются взаимно рекурсивными, что он может сделать? Одна из возможностей - просто провести анализ зависимостей для всех определений в области видимости и переупорядочить их по минимально возможным группам. На самом деле Haskell делает это, но для таких языков, как F # (и OCaml и SML), которые имеют неограниченные побочные эффекты, это плохая идея, потому что это может также изменить порядок побочных эффектов. Поэтому вместо этого он просит пользователя явно отметить, какие определения являются взаимно рекурсивными, и, следовательно, по расширению, где должно произойти обобщение.

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

51

ответ дан 24 November 2019 в 07:04

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

Это похоже на предикаты градуированного равенства в Scheme. (т.е. экв? ,

1

ответ дан 24 November 2019 в 07:04

Некоторые предположения:

let используется не только для связывания функций, но и других обычных значений. Большинство форм значений не могут быть рекурсивными. Разрешены определенные формы рекурсивных значений (например, функции, ленивые выражения и т. Д.), Поэтому для обозначения этого требуется явный синтаксис.
Возможно, было бы проще оптимизировать нерекурсивные функции.
Замыкание, созданное при создании рекурсивная функция должна включать запись, которая указывает на саму функцию (чтобы функция могла рекурсивно вызывать себя), что делает рекурсивные замыкания более сложными, чем нерекурсивные замыкания. Так что было бы неплохо иметь возможность создавать более простые нерекурсивные замыкания, когда вам не нужна рекурсия
. Это позволяет вам определять функцию в терминах ранее определенной функции или значения с тем же именем; хотя я считаю это плохой практикой
Дополнительная безопасность? Убедитесь, что вы делаете то, что планировали. например, если вы не хотите, чтобы он был рекурсивным, но вы случайно использовали имя внутри функции с тем же именем, что и сама функция, он, скорее всего, пожалуется (если имя не было определено раньше)
конструкция let аналогична конструкции let в Lisp и Scheme; которые не рекурсивны. В схеме для рекурсивного let

4

ответ дан 24 November 2019 в 07:04

Другие вопросы по тегам:

f# recursion ocaml

Похожие вопросы:

score 82 · Accepted Answer

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

Функции не рекурсивны по умолчанию во французском семействе языков CAML (включая OCaml). Этот выбор упрощает замену определений функций (и переменных) с помощью let на этих языках, поскольку вы можете ссылаться на предыдущее определение внутри тела нового определения. F # унаследовал этот синтаксис от OCaml.

Например, замена функции p при вычислении энтропии Шеннона последовательности в OCaml:

let shannon fold p =
  let p x = p x *. log(p x) /. log 2.0 in
  let p t x = t +. p x in
  -. fold p 0.0

Обратите внимание, как аргумент p к функции Шеннона более высокого порядка заменяется другим p в первой строке тела, а затем еще одним ] p во второй строке тела.

И наоборот, британская ветвь SML семейства языков ML выбрала другой вариант, и связанные функции SML fun по умолчанию рекурсивны. Когда большинству определений функций не требуется доступ к предыдущим привязкам их имени функции, это приводит к упрощению кода. Однако замененные функции используют разные имена ( f1 , f2 и т. Д.), Что загрязняет область видимости и позволяет случайно вызвать неправильную «версию» функции. И теперь существует несоответствие между неявно-рекурсивными fun -связанными функциями и нерекурсивными val -связанными функциями.

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

Обратите внимание, что ответы Ганеша и Эдди - отвлекающий маневр. Они объяснили, почему группы функций нельзя поместить внутрь гиганта let rec ... и ... потому что это влияет на обобщение переменных типа. Это не имеет ничего общего с rec по умолчанию в SML, но не с OCaml.

Это делает образцы игрушек более простыми, но в других местах обходится дорого.

Обратите внимание, что ответы Ганеша и Эдди - отвлекающий маневр. Они объяснили, почему группы функций нельзя поместить внутрь гиганта let rec ... и ... потому что это влияет на обобщение переменных типа. Это не имеет ничего общего с rec по умолчанию в SML, но не с OCaml.

Это делает образцы игрушек более простыми, но в других местах обходится дорого.

Обратите внимание, что ответы Ганеша и Эдди - отвлекающий маневр. Они объяснили, почему группы функций нельзя поместить внутрь гиганта let rec ... и ... потому что это влияет на обобщение переменных типа. Это не имеет ничего общего с rec по умолчанию в SML, но не с OCaml.