MemoTrie icon indicating copy to clipboard operation
MemoTrie copied to clipboard

Add `memoFix2` and `memoFix3`

Open wilcooo opened this issue 3 years ago • 1 comments

memoFix lacks it's multi-parametered cousins; so I wrote memoFix2 and memoFix3. I've also included an example of using these within the code.

A few things to note;

  • maybe memo2Fix and memo3Fix would be better names (because memo2 and memo3 exist)? Or maybe even change to using fixMemo, fixMemo2 and fixMemo3, but that would break backwards compatibility.
  • I have not (yet) bumped the version, as I'm not sure whether this should be 7.0 or 6.11
  • Are there other things f.e. in the cabal file that will need to be updated that I missed?

wilcooo avatar Nov 04 '21 19:11 wilcooo

Btw, for those interested, this is what I'm using memoFix2 for. I'm trying to solve Project Euler #770. It's far from a full solution but don't look if you want the pleasure of solving it yourself.

Spoiler warning
guaranteedF :: (Int -> Int -> Rational) -> (Int -> Int -> Rational)
guaranteedF _ 0 g = 2^g
guaranteedF _ t 0 = 1

guaranteedF f t g = a * (1 - x)
where a = f (t-1) g
      b = f t (g-1)
      x = (a - b) / (a + b)

guaranteed = memoFix2 guaranteedF

wilcooo avatar Nov 04 '21 19:11 wilcooo