Equivalent in Haskell of generator with stopping condition-CodePudding

Suppose I want to build a list iterate step x0 in Haskell, but with an inclusive termination condition. So in Python this would be list(my_gen) where e.g.

def my_gen():
    x = x0
    while not done(x):
        x = step(x)
        yield x

One way would be to write my own takeWhileInclusive and say

takeWhileInclusive (not . done) . iterate step x0

Is this the Haskell-y way (or a Haskell-y way) to accomplish this? It seems unnatural to try to tack on some sentinel value for step x when done x is true and then use takeWhile.

In particular I'm thinking of the container with most water problem on LeetCode, and solving it with something like

maxWith volume . smartSteps (0, n)
 where smartSteps = takeWhileInclusive (\(i,j) -> j - i > 1) . iterate step

and step increases i or decreases j (or both), according to which index has the higher line.

Of course here it would be easy to just use takeWhile j > i, but I wanted to think how I would approach situations where there isn't a natural "you went too far" condition, just a "you are done" condition.

CodePudding user response：

You can use unfoldr to generate the sequence:

unfoldr (\x -> if done x then Nothing else Just (x, step x)) x0

For example,

> import Data.List
> step = ( 1)
> done = (> 10)
> x0 = 0
> unfoldr (\x -> if done x then Nothing else Just (x, step x)) x0
[0,1,2,3,4,5,6,7,8,9,10]

unfoldr calls its function on x0 to start. When the function returns Nothing, unfoldr stops. When the function returns Just (x, y), it appends x to the result and calls the function again on y.

Compare your generator to a Python implementation of unfoldr:

def unfoldr(f, x):
    while True:
        if (y := f(x)) is None:
            return
        else:
            yield y[0]
            x = y[1]

list(unfoldr(lambda x: None if done(x) else (x, step(x)), x0))

CodePudding user response：

Yes, that is a Haskell-y way.

Another Haskell-y way (or a Haskell-y way to implement takeWhileInclusive) is to zip up the iterated values with one step later.

myGen done step = map snd . takeWhile (not . done . fst) . ap zip tail . iterate step

N.B. unlike iterate (but like my_gen) this does not emit the initial x value as one of the steps.