leanprover / leanprover/fp-lean

§8.3.3 Exercises asks me to implement ForM using `for … in` in the wrong monad

Open Beginner friendly
#274 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Lean
Stars
192
Forks
73
PR merge metrics
No merged PRs in 30d

Description

Please quote the text that is incorrect:

Reimplement Array.map, Array.find, and the ForM instance using for ... in ... loops in the identity monad and compare the resulting code.

In what way is this incorrect?

The ForM instance should use the for … in … syntax in the m monad rather than in the identity monad. Trying to do it in the identity monad is weird and AFAICT requires doing something like storing all of the monadic actions in a List and then consuming the list. Also just trying to write a ForM instance using for … in … is a bit weird to begin with, if I don't want to rely on the fact that Array already has one then I have to iterate over indices. So the identity monad version I ended up with the following:

instance [Monad m] : ForM m (Array α) α where
  forM arr f := Id.run do
    let mut xs := []
    for h : i in [0:arr.size] do
      xs := f arr[i] :: xs
    pure (xs.foldr (·*>·) (pure ()))

But if I drop the requirement that this be done in the identity monad then I get this much simpler version (once again still trying to avoid relying on the preexisting ForM impl):

instance [Monad m] : ForM m (Array α) α where
  forM arr f := do
    for h : i in [0:arr.size] do
      f arr[i]

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with §8.3.3 and the quoted exercise text about implementing the ForM instance in the identity monad. Check the exercise against the two Lean examples in the issue, then revise the wording so the ForM example uses the m monad; done means the text no longer directs readers toward the identity-monad approach.

Written by the indexing model from the issue text.

Assessment

Domain
documentation
Issue type
Documentation
Difficulty
1/5
Estimated time
Under an hour
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
78/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.