CODEWITHSUNDEEP
listhaskellfunctional-programming
Ben Campbell
Ben Campbell

Reputation: 4658

Take From a List While Increasing

I have a list of values that I would like to take from while the value is increasing. I assume it would always take the head of the list and then compare it to the next value. The function will continue to take as long as this continues to increase. Upon reaching an list element that is less than or equal the pervious value the list is returned.

takeIncreasing :: (Ord a) => [a] -> [a]
takeIncreasing [1,2,3,4,3,5,6,7,8] -- Should return [1,2,3,4]

A fold could compare the last element of the accumulation with the next value and append if the condition is met, but would continue to the end of the list. I would like the function to stop taking at the first instance the constraint is not met.

This seems like an application of a monad but cannot determine if an existing monad accomplishes this.

Upvotes: 3

Views: 496

Answers (4)

dvaergiller
dvaergiller

Reputation: 815

Or one that IMO has a bit less code complexity:

takeIncreasing :: Ord x => [x] -> [x]
takeIncreasing (x:x':xs) | x < x'    = x : takeIncreasing (x':xs)
                         | otherwise = [x]
takeIncreasing xs = xs

This one is just a bit less clever than previous suggestions. I like un-clever code.

Upvotes: 3

chi
chi

Reputation: 116139

A solution without folds:

takeIncreasing :: Ord a => [a] -> [a]
takeIncreasing [] = []
takeIncreasing (x:xs) = (x :) . map snd . takeWhile (uncurry (<)) $ zip (x:xs) xs

Upvotes: 2

dfeuer
dfeuer

Reputation: 48580

Right folds are magical, so you never even have to pattern match on the list.

twi xs = foldr go (const []) xs Nothing where
  go x _ (Just prev)
    | x < prev = []
  go x r _ = x : r (Just x)

Upvotes: 4

behzad.nouri
behzad.nouri

Reputation: 77941

A fold [...] would continue to the end of the list. I would like the function to stop taking at the first instance the constraint is not met.

A right fold can short circuit:

fun :: Ord a => [a] -> [a]
fun []     = []
fun (x:xs) = x: foldr go (const []) xs x
    where go x f i = if i < x then x: f x else []

then, 

\> fun [1,2,3,4,3,undefined]
[1,2,3,4]

or infinite size list:

\> fun $ [1,2,3,4,3] ++ [1..]
[1,2,3,4]

Upvotes: 9

Related Questions