CODEWITHSUNDEEP
algorithmhaskellfunctional-programming
user318904
user318904

Reputation: 3076

Haskell foldWhile or reduceWhile without list function?

I am looking for a haskell function or pattern that is a sort of "foldWhile" except instead of folding over a list it uses a functions output..some code will probably explain it better.

Simplified and pseudo:

nums :: [Integer]
nums = [1]

cond :: v -> [Integer] -> Bool
cond v ls = elem v ls

func :: x -> ls -> [Integer]
func x ls = x `some_op` ls

And I need a pattern of application like:

(cond 1 num) && func x num -> num'
(cond 1 num') && func x num' -> num''
(cond 1 num'') && func x num'' -> num'''
...

Once cond returns False, yield the last num.

Any help would be appreciated, thanks in advance.

Upvotes: 4

Views: 561

Answers (1)

bheklilr
bheklilr

Reputation: 54068

I think you want a combination of iterate and takeWhile:

iterate :: (a -> a) -> a -> [a]
takeWhile (a -> Bool) -> [a] -> [a]

iterateWhile :: (a -> a) -> (a -> Bool) -> a -> [a]
iterateWhile func cond = takeWhile cond . iterate func

And in your case you'd want to use it as

lastWhere :: (a -> a) -> (a -> Bool) -> a -> a
lastWhere func cond = last . iterateWhile func cond

main = do
    let x = lastWhere (+1) (<10) 1
    print x
    -- prints "9"

You can probably do this with a fold, but why bother when you have this solution already? If evaluating the condition is separate from generating the values, then separate those two concerns, rather than trying to tie them together. This is what iterateWhile does. Since it's lazily evaluated, this only generates values until it finds one that doesn't meet the condition, and it only needs a single loop to do so.

Since iterateWhile produces a list of elements all satisfying that condition, you can then simply take the last element. If you need the first element that fails, I would do

firstWhere :: (a -> a) -> (a -> Bool) -> a -> a
firstWhere func cond = head . dropWhile cond . iterate func

Upvotes: 6

Related Questions