Equivalent in Haskell of generator with stopping condition

user_8755792 0
Viewed 197

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

(Edit: This should have an additional yield x before the loop if I want to include x0.)

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.

Edit: This question has been marked as a duplicate (of a question which I had linked to in my question), but it is not. The question is not how to write takeWhileInclusive, in fact the question explicitly takes takeWhileInclusive as given. It is about how to accomplish a task that may or may not use takeWhileInclusive.

generator functional-programming haskell
3 Answers

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))
user_11268410

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.

user_7916040

You can define

takeUntil done xs = 
  foldr (\x r -> if done x then [x] else x : r) [] xs

and then use it like

takeUntil done $ iterate step x0

e.g. takeUntil (> 9) [1..] == [1..10].

It's easy to specify the final element with foldr (as is seen here), but more cumbersome to do that with unfoldr which encodes an "anamorphism", closing the generated list with an empty list as the sentinel. Specifying the non-empty tail is possible with an "apomorphism", which seems like it would be the fitting tool for this task.

user_8498910
Related