Ch8 Add exercise for ST

[milesfrain]

We should add a replacement for this original ST exercise:

(Difficult) The following is a simple way to estimate pi: randomly choose a large number N of points in the unit square, and count the number n which lie in the inscribed circle. An estimate for pi is 4n/N. Use the random and ST effects with the for function to write a function which estimates pi in this way.

Effect.random can no longer be blended with ST, so we can't complete this "Monte Calro Method" exercise.

It is still possible to estimate pi using a grid of points, but it's not as interesting without random, and the grid method could actually be tackled in ch4 like so:

estimatePi :: Int -> Number
estimatePi r =
  let
    bigN = r * r

    n =
      sum do
        x <- 1 .. r
        y <- 1 .. r
        guard $ x * x + y * y < r * r
        pure 1
  in
    (toNumber (4 * n)) / (toNumber bigN)

I'm not sure if adding this to ch4 would be an improvement, since it doesn't test any new language concepts.

It is possible to complete this exercise using Effect.Ref, but that's covered in Ch9. We could move Ref content to Ch8.

---

Some additional information:

ST may eventually be merged with Effect purescript/purescript-st#31

Summary of ways to track mutable state:

• Control.Monad.ST - local mutations
  • Covered in this section of Ch8
• Effect.Ref - global mutations
  • Covered in Ch9
  • Use with forE from Effect
  • "Note: Control.Moad.ST provides a safe alternative to global mutable variables when mutation is restricted to a local scope."
• Control.Monad.State - passing around (technically immutable) state without having to thread parameters through a bunch of functions.
  • Covered in Ch11
  • This section of the original book contrasts this with ST and Ref.
  • Transformer

Previous discussion of this issue in #94

[shaunplee]

Any opinions on an exercise to apply dynamic programming to a previously-encountered exercise that used recursion (e.g., fibonacci from Chapter 4 or binomial or pascal from Chapter 5)?

Or perhaps stick with approximating pi, but remove the randomness by using the Gregory Series?

[milesfrain]

I like all those suggestions. We could include more than one exercise.

If covering fibonacci, we could also highlight Data.Function.Memoize in an aside as yet another DP option (see MemoizeFibonacci in the cookbook).

Also wondering if it would be worth mentioning the helper-functions from Data.Array.ST, which appear to have been introduced after this section of the book was originally written.