Loading ...
Sorry, an error occurred while loading the content.

Re: "ocaml_beginners"::[] repetitive function calling

Expand Messages
  • Jon Harrop
    ... Oh, hang on. If you want to memoize the result of an expression then you want to use lazy evaluation and the Lazy module. If you want to memoize the
    Message 1 of 8 , Apr 4 1:53 PM
    View Source
    • 0 Attachment
      On Monday 04 April 2005 15:35, Seth J. Fogarty wrote:
      > I didn't know that lazy memoization could be used to mimic DP
      > memoization... any chance I can get a brief explanation on how that
      > works?

      Oh, hang on. If you want to memoize the result of an expression then you want
      to use lazy evaluation and the Lazy module. If you want to memoize the
      mapping from a function's input values to output values then you'll want to
      use a higher-order "memoize" function.

      This "memoize1" function (from Appendix A) can be used to memoize both
      non-recursive and recursive, one-argument functions:

      # let memoize1 f =
      let cache = Hashtbl.create 1 in
      let rec f' n =
      try Hashtbl.find cache n
      with Not_found -> (fun fn -> Hashtbl.add cache n fn; fn) (f f' n) in
      f';;
      val memoize1 : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

      The function given to memoize1 is expected to accept itself as an argument (to
      account for recursion). For example:

      # let rec fib =
      memoize1 (fun self n -> if n<3 then 1 else self (n - 2) + self (n - 1));;
      val fib : int -> int = <fun>

      The disadvantage of this approach is that it is less automatic. The advantages
      are that you have closer control over the memoization (e.g. you may wish to
      periodically delete all entries which haven't been reused) and you can
      memoize in various different ways depending upon your circumstances (e.g.
      using a hash table will be inappropriate under certain circumstances).

      > Most of the use of laziness that I've seen has just been to
      > 'fix' persistance, and the rest is wierd monad tricks.

      Laziness can be very useful. When I was writing an interpreter, I wanted to
      store a set of the types which appeared in each branch of the AST.
      Implementing this turned out to be hugely costly in terms of performance
      until I made computing these sets lazy, so the values were only computed if
      they were ever explicitly asked for. The performance was then
      indistinguishable from the original implementation. :-)

      --
      Dr Jon D Harrop, Flying Frog Consultancy Ltd.
      Objective CAML for Scientists
      http://www.ffconsultancy.com/products/ocaml_for_scientists
    • Oliver Bandel
      ... [...] Haskell has such a feature, but itr depends on a certain style of how you write the code that it can be used. Have no example in mind, but in
      Message 2 of 8 , Apr 8 1:53 PM
      View Source
      • 0 Attachment
        On Sat, Apr 02, 2005 at 03:29:27PM -0500, Alessandro Gagliardi wrote:
        >
        > An old professor of mine was telling me about a feature in some Lisp
        > compilers where if you call a function more than once with the same
        > arguments, rather than process it all over again, it will remember the
        > value that came back last time and simply return that. Of course,
        [...]

        Haskell has such a feature, but itr depends on a certain style
        of how you write the code that it can be used.

        Have no example in mind, but in "Haskell - The Craft Of Functional Programming",
        which IMHO is a very good introductional book on functional programming
        in general, and specially to Haskell also, this was mentioned.

        But I have the book here, so I can't look for an example.


        Ciao,
        Oliver
      • Oliver Bandel
        ... I think it was how it was indented and which item comes first in that line or so. ... ^ not Ciao, Oliver
        Message 3 of 8 , Apr 9 4:01 AM
        View Source
        • 0 Attachment
          On Fri, Apr 08, 2005 at 10:53:54PM +0200, Oliver Bandel wrote:
          >
          > On Sat, Apr 02, 2005 at 03:29:27PM -0500, Alessandro Gagliardi wrote:
          > >
          > > An old professor of mine was telling me about a feature in some Lisp
          > > compilers where if you call a function more than once with the same
          > > arguments, rather than process it all over again, it will remember the
          > > value that came back last time and simply return that. Of course,
          > [...]
          >
          > Haskell has such a feature, but itr depends on a certain style
          > of how you write the code that it can be used.

          I think it was how it was indented and which item comes first in that line or so.

          >
          > Have no example in mind, but in "Haskell - The Craft Of Functional Programming",
          > which IMHO is a very good introductional book on functional programming
          > in general, and specially to Haskell also, this was mentioned.
          >
          > But I have the book here, so I can't look for an example.
          ^
          \
          not


          Ciao,
          Oliver
        Your message has been successfully submitted and would be delivered to recipients shortly.