Мемоизация рекурсивных функций

 
0
 
Functional languages
ava
Lazin | 27.11.2009, 13:22
я использовал вот такой код, для мемоизации функций

let memoize (f : 'a -> 'b) =
    let dict = new System.Collections.Generic.Dictionary<'a, 'b>() 
    let memFn (n : 'a) =
        match dict.ContainsKey(n) with
        | true, x -> x
        | false, _ -> 
            let res = f n
            dict.Add(n, res) 
            res
    memFn

это отлично работает с обычными, чистыми ф-ями и рекурсивными фнкциями (tail recursive), но возникла проблема
у меня есть функция, которая не является tail recursive, которую можно свести к ХР форме используя аккумулятор, что-то вроде:


let func x =
    let rec innerFunc acc x =
        match x whit
        | 0 -> acc
        | _ -> nextSeqElem (acc + 1) x
    innerFunc 0 x


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

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

код пишу по памяти, так-что могу ошибаться где-нибудь, но не сильно =)
Comments (1)
ava
Lazin | 27.11.2009, 21:51 #
I believe, λ man will save me!!
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  Lazin
advanced
Submit