From: Jacek Chrzaszcz <chrzaszc@mimuw.edu.pl>
To: William Lovas <wlovas@stwing.upenn.edu>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Memoizing (was: static variables...)
Date: Tue, 18 Jun 2002 11:16:13 +0200 [thread overview]
Message-ID: <20020618111613.A30795@absurd.mimuw.edu.pl> (raw)
In-Reply-To: <20020618084006.GA8596@force.stwing.upenn.edu>; from wlovas@stwing.upenn.edu on Tue, Jun 18, 2002 at 04:40:07AM -0400
>
> Unfortunately, this is not a very general solution. I suspect a
> general solution, like for example Mark-Jason Dominus's Perl module
> Memoize.pm, requires a stateful environment (i think the Perl version
> uses code references). The problem with an elegant O'Caml solution, i
> think, is that the inner recursive calls are part of the definition
> environment of the recursive function (i.e. part of the closure), and
> there's no way to change them without writing a new function (and thus
> creating a new closure).
>
> Does anyone have any thoughts on this? Am i missing something obvious?
>
> William
If you write it like this, it works:
let memoize f =
let hash = Hashtbl.create 20 in
let rec f' a =
try Hashtbl.find hash a
with Not_found ->
let b = f f' a in
Hashtbl.add hash a b; b
in
f';;
let recfib recfib = function
| 0 | 1 -> 1
| n -> recfib (n-1) + recfib (n-2);;
let fib = memoize recfib;;
Now fib 30 is instantaneous! The clue is to contruct a new
hash and a new recursive function once for each application of
memoize.
Jacek
PS. In caml you can write anything ;)
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
next prev parent reply other threads:[~2002-06-18 19:05 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-06-14 17:08 [Caml-list] static variables in a function Shannon --jj Behrens
2002-06-14 17:40 ` Stefano Zacchiroli
2002-06-14 17:58 ` Yutaka OIWA
2002-06-14 20:43 ` Shannon --jj Behrens
2002-06-15 4:42 ` Max Kirillov
2002-06-15 6:36 ` John Prevost
2002-06-15 14:51 ` Max Kirillov
2002-06-15 16:14 ` John Prevost
2002-06-15 19:19 ` Max Kirillov
2002-06-15 23:16 ` John Prevost
2002-06-16 23:19 ` Remi VANICAT
2002-06-17 13:56 ` [Caml-list] Memoizing (was: static variables...) Benedikt Rosenau
2002-06-18 8:40 ` William Lovas
2002-06-18 9:16 ` Jacek Chrzaszcz [this message]
2002-06-18 21:52 ` William Lovas
2002-06-18 13:07 ` Christopher Quinn
2002-06-18 14:07 ` Remi VANICAT
2002-06-18 17:52 ` Christopher Quinn
2002-06-19 14:42 ` John Max Skaller
2002-06-23 21:18 ` Pierre Weis
2002-06-19 4:38 ` [Caml-list] static variables in a function Shannon --jj Behrens
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20020618111613.A30795@absurd.mimuw.edu.pl \
--to=chrzaszc@mimuw.edu.pl \
--cc=caml-list@inria.fr \
--cc=wlovas@stwing.upenn.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox