Beginner's question: Memo functions in Haskell

Janis Voigtlaender voigt@orchid.inf.tu-dresden.de
Wed, 05 Jun 2002 13:36:15 +0200


Malcolm Wallace wrote:
> 
> You need to call the memoised version in the recursive case.
> 
> > module Fib where
> >
> > import Memo
> >
> > slow 0 = 0
> > slow 1 = 1
> > slow n = slow (n-1) + slow (n-2)
> 
>   slow n = fast (n-1) + fast (n-2)
> 
> > fast n = memo slow n

It would also seem that one needs to write

 fast = memo slow

instead, because otherwise a new memo-version of slow might be created
for every call with some n (subject to let-floating?).
However, the version:

  module Fib where

  import Memo

  slow 0 = 0
  slow 1 = 1
  slow n = fast (n-1) + fast (n-2)

  fast = memo slow

is not particularly fast easier. Quite in contrary... strange.

Janis.

--
Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt@tcs.inf.tu-dresden.de