Рекурсивные последовательности в F#
Допустим, я хочу вычислить факториал целого числа. Простой подход к этому в F# был бы:
let rec fact (n: bigint) =
match n with
| x when x = 0I -> 1I
| _ -> n * fact (n-1I)
Но если моя программа нуждается в динамическом программировании, как я могу поддерживать функциональное программирование, используя памятку?
У меня была идея создать последовательность ленивых элементов, но я столкнулся с проблемой. Предположим, что следующий код был приемлемым в F# (это не так):
let rec facts =
seq {
yield 1I
for i in 1I..900I do
yield lazy (i * (facts |> Seq.item ((i-1I) |> int)))
}
Есть ли что-нибудь похожее на эту идею в F#? (Примечание: я понимаю, что могу использовать словарь.NET, но не вызывает императивный стиль метода ".Add()"?)
Кроме того, есть ли способ обобщить это с помощью функции? Например, могу ли я создать последовательность длины функции коллатца, определенной функцией:
let rec collatz n i =
if n = 0 || n = 1 then (i+1)
elif n % 2 = 0 then collatz (n/2) (i+1)
else collatz (3*n+1) (i+1)
2 ответа
Если вы хотите сделать это лениво, это хороший подход:
let factorials =
Seq.initInfinite (fun n -> bigint n + 1I)
|> Seq.scan ((*)) 1I
|> Seq.cache
Seq.cache означает, что вы не будете повторно оценивать элементы, которые вы уже перечислили.
Затем вы можете взять определенное количество факториалов, используя, например, Seq.take nили получить конкретный факториал, используя Seq.item n,
Во-первых, я не вижу в вашем примере, что вы имеете в виду под "динамическим программированием".
Использование запоминания не означает, что что-то не является "функциональным" или нарушает неизменность. Важным моментом является не то, как что-то реализовано. Важно то, как он ведет себя. Функция, которая использует изменяемую памятку, по-прежнему считается чистой, если она ведет себя как чистая функция / неизменяемая функция. Таким образом, использование изменяемых переменных в ограниченной области, невидимой для вызывающей стороны, все еще считается чистым. Если реализация будет важна, мы также можем рассматривать хвостовую рекурсию как не чистую, так как компилятор преобразует ее в цикл с изменяемыми переменными под капотом. Также существует некоторая функция List.xyz, которая использует мутацию и преобразует вещи в изменяемую переменную только из-за скорости. Эти функции все еще считаются чистыми / неизменяемыми, потому что они все еще ведут себя как чистые функции.
Сама последовательность уже ленива. Он уже вычисляет все свои элементы только тогда, когда вы запрашиваете эти элементы. Поэтому для меня не имеет смысла создавать последовательность, которая возвращает ленивые элементы.
Если вы хотите ускорить вычисления, существует несколько способов, как это сделать. Даже в рекурсивной версии вы можете использовать аккумулятор, который передается при следующем вызове функции. Вместо того, чтобы делать глубокую рекурсию.
let fact n =
let rec loop acc x =
if x = n
then acc * x
else loop (acc*x) (x+1I)
loop 1I 1I
Это в целом так же, как
let fact' n =
let mutable acc = 1I
let mutable x = 1I
while x <= n do
acc <- acc * x
x <- x + 1I
acc
Пока вы изучаете функциональное программирование, хорошей идеей будет привыкнуть к первой версии и научиться понимать, как циклы и рекурсия связаны друг с другом. Но кроме обучения нет причины, по которой вы всегда должны заставлять себя всегда писать первую версию. В конце вы должны использовать то, что считаете более читабельным и более понятным. Не то, использует ли что-то изменчивую переменную как реализацию или нет.
В конце концов, никто не заботится о точной реализации. Мы должны рассматривать функции как черные ящики. Так что пока функция ведет себя как чистая функция, все в порядке.
Выше используется аккумулятор, поэтому вам не нужно повторять вызов функции снова, чтобы получить значение. Так что вам также не нужен внутренний изменяемый кеш. если у вас действительно медленная рекурсивная версия и вы хотите ускорить ее с помощью кэширования, вы можете использовать что-то подобное.
let fact x =
let rec fact x =
match x with
| x when x = 1I -> 1I
| x -> (fact (x-1I)) * x
let cache = System.Collections.Generic.Dictionary<bigint,bigint>()
match cache.TryGetValue x with
| false,_ ->
let value = fact x
cache.Add(x,value)
value
| true,value ->
value
Но это, вероятно, будет медленнее, чем версии с аккумулятором. Если вы хотите кешировать фактические вызовы даже по нескольким фактическим вызовам во всем приложении, вам нужен внешний кэш. Вы можете создать словарь вне фактов и использовать для этого приватную переменную. Но вы также можете использовать функцию с замыканием и сделать весь процесс общим.
let memoize (f:'a -> 'b) =
let cache = System.Collections.Generic.Dictionary<'a,'b>()
fun x ->
match cache.TryGetValue x with
| false,_ ->
let value = f x
cache.Add(x,value)
value
| true,value ->
value
let rec fact x =
match x with
| x when x = 1I -> 1I
| x -> (fact (x-1I)) * x
Так что теперь вы можете использовать что-то подобное.
let fact = memoize fact
printfn "%A" (fact 100I)
printfn "%A" (fact 100I)
и создайте запомненную функцию из любой другой функции, которая принимает 1 параметр
Обратите внимание, что запоминание не ускоряет все автоматически. Если вы используете функцию памятки, на самом деле ничего не ускоряется, она будет даже медленнее, чем без памятки. Вы можете добавить printfn "Cache Hit"к | true,value -> ветвь внутри функции памятки. призвание fact 100I два раза подряд приведет только к одной строке "Cache Hit".
Проблема в том, как работает алгоритм. Он начинается с 100I и снижается до 0I. Таким образом, при подсчете 100I запрашиваю кеш 99I, его нет, поэтому он пытается вычислить 98I и задать кеш. Этого также не существует, поэтому оно снижается до 1I. Он всегда спрашивает кеш, никогда не находит результат и вычисляет необходимое значение. Таким образом, вы никогда не получите "попадание в кэш", и у вас есть дополнительная работа по запросу кеша. Чтобы по-настоящему извлечь выгоду из кэша, вам нужно изменить сам факт, поэтому он начинается с 1I до 100I. Текущая версия даже выдает Stackru для больших входов, даже с функцией memoize.
Только второй звонок извлекает выгоду из кеша, поэтому звонит fact 100I дважды будет печатать "Cache Hit" только один раз.
Это всего лишь пример того, как можно легко ошибиться с кэшированием / запоминанием. В общем, вы должны попытаться написать функцию, чтобы она была рекурсивной и использовала вместо этого аккумуляторы. Не пытайтесь писать функции, которые ожидают, что запоминание будет работать должным образом.
Я бы выбрал решение с аккумулятором. Если вы профилировали свое приложение и обнаружили, что это все еще медленно, и у вас есть узкое место в вашем приложении и кешировании fact поможет, то вы также можете просто кэшировать результаты facts непосредственно. Что-то вроде этого. Вы могли бы использовать dict или карта для этого.
let factCache = [1I..100I] |> List.map (fun x -> x,fact x) |> dict
let factCache = [1I..100I] |> List.map (fun x -> x,fact x) |> Map.ofList