iterator fold_until

[TanklesXL]

I noticed that while list has a fold_until function, there isn't one for iterator.

I would be happy to contribute one, but I had a couple questions about the implementation details with regards to type ContinueOrStop found in list:

pub type ContinueOrStop(a) {
  Continue(a)
  Stop(a)
}

Ideally it would be nice to use the same ContinueOrStop type for both the list and iterator fold_until functions, so that the functions passed could be compatible with both. In which case here are my 2 quesions:

1. would it be better kept in the list module or extracted to some other module?

2. the iterator.Action type has the same variant names

type Action(element) {
  Stop
  Continue(element, fn() -> Action(element))
}

but it seems to serve a different purpose, would it be useful to rename the variants of iterator.Action to avoid collisions/make the different purposes clearer? (not sure what names would be good though)

For reference, I've got a preliminary implementation of fold_until that just uses the list.ContinueOrStop with a unit test here: TanklesXL@477cd4e

[lpil]

Using the one from the list module sounds good. I think it's probably OK to keep the Action type with the same names. It could be renamed later if we wish, it's a private internal type so it's not a problem to keep refining it.

Your patch there looks good!

[TanklesXL]

Cool! I'll fix up the comments/examples and submit the PR in the next day or so! 😃

[TanklesXL]

@lpil while I'm at it, would you like me to add a map.fold_until?

[lpil]

I'm a little less sure about that one as maps are not ordered. Can you think of a use case?

[TanklesXL]

Not really 😅 I just thought of it because I was already adding fold_until to things

[TanklesXL]

Hmmm, now that I'm thinking about it, what about adding a list/iterator fold_until_error which would use a function that returns a Result instead of a ContinueOrStop, or a fold_until_none which would use a function that returns an Option?

[lpil]

Swapping the ContinueOrStop for Option sounds good to me

[TanklesXL]

@lpil is there a plan to put Option in the prelude? As the stdlib currently sits, a list.fold_until_none is not possible because the option module already imports list and it would create an import cycle & therefore not compile.

It's not currently a blocker for iterator because option does not import iterator

[lpil]

No plans to move it into the prelude until it gains something that cannot be implemented in userland. We could possibly remove the use of the list module from option

[TanklesXL]

so i've been noodling around with possible implementations for a list and iterator fold_until_error and i'm starting to think it might not be worth it 🤔

for example, the basic implementations of each would look something like this:

• list:

pub fn fold_until_error(
  over collection: List(a),
  from accumulator: acc,
  with fun: fn(acc, a) -> Result(acc, err),
) -> acc {
  case collection {
    [] -> accumulator
    [first, ..rest] ->
      case fun(accumulator, first) {
        Ok(next_accumulator) -> fold_until_error(rest, next_accumulator, fun)
        Error(_) -> accumulator
      }
  }
}

• iterator:

fn do_fold_until_error(
  continuation: fn() -> Action(e),
  f: fn(acc, e) -> Result(acc, err),
  accumulator: acc,
) -> acc {
  case continuation() {
    Stop -> accumulator
    Continue(elem, next) ->
      case f(accumulator, elem) {
        Ok(accumulator) -> do_fold_until_error(next, f, accumulator)
        Error(_) -> accumulator
      }
  }
}

pub fn fold_until_error(
  over iterator: Iterator(e),
  from initial: acc,
  with f: fn(acc, e) -> Result(acc, err),
) -> acc {
  iterator.continuation
  |> do_fold_until_error(f, initial)
}

But what i noticed is that these can be boiled down to

• list:

pub fn fold_until_error(
  over collection: List(a),
  from accumulator: acc,
  with f: fn(acc, a) -> Result(acc, err),
) -> acc {
  let f = fn(acc, e) -> ContinueOrStop(acc) {
    case f(acc, e) {
      Ok(acc) -> Continue(acc)
      Error(_) -> Stop(acc)
    }
  }

  fold_until(collection, accumulator, f)
}

• iterator:

pub fn fold_until_error(
  over iterator: Iterator(e),
  from initial: acc,
  with f: fn(acc, e) -> Result(acc, err),
) -> acc {
  let f = fn(acc, e) -> list.ContinueOrStop(acc) {
    case f(acc, e) {
      Ok(acc) -> list.Continue(acc)
      Error(_) -> list.Stop(acc)
    }
  }

  fold_until(iterator, initial, f)
}

Note: the common bit

  let f = fn(acc, e) -> ContinueOrStop(acc) {
    case f(acc, e) {
      Ok(acc) -> Continue(acc)
      Error(_) -> Stop(acc)
    }

It seems almost trivial and I don't know if i really consider something like that worth having in the stdlib? if anything maybe just exposing something like the flollowing (but I personally don't think it's worth it):

pub fn continue_or_stop_from_result(
  f: fn(acc, e) -> Result(a,_),
) -> fn(acc,e) -> ContinueOrStop(acc) {
  fn(acc, e) {
    case f(acc, e) {
      Ok(acc) -> Continue(acc)
      Error(_) -> Stop(acc)
    }
  }
}

[lpil]

Yeah I think it's probably not worth it. No harm in a small bit of duplication.

[TanklesXL]

Closing this for now as there isn't really anything to be done here