CODEWITHSUNDEEP
haskell
matt
matt

Reputation: 2039

Haskell : continuing recursion for extra step

If I have a recursive function that does comparisons on every element on a list; what is the best way to have it do an extra step at then end as if the list had an extra 0 on the end, without actually appending 0 to the list in the first place.

rect xs = maximum $ go 0 [] (xs ++ [0]) where
  go i s                     []     = []
  go i ((_, tH):r@((t,_):_)) (h:hs) | h < tH = tH * (i - t - 1) : go i r (h:hs)
  go i s                     (h:hs) = go (i + 1) ((i,h):s)  hs

I am think that there must be a better way than doing the xs ++ [0] but I can't come up with it.

Note: The function is to find the largest rectangle in a histogram

Upvotes: 2

Views: 103

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152837

Modify your base case and unroll the loop one step. It leads to a bit of code duplication, but it doesn't look too terrible.

rect' xs = maximum $ go 0 [] xs where
  go i ((_, tH):r@((t,_):_)) []     | 0 < tH = tH * (i - t - 1) : go i r []
  go i s                     []     = []
  go i ((_, tH):r@((t,_):_)) (h:hs) | h < tH = tH * (i - t - 1) : go i r (h:hs)
  go i s                     (h:hs) = go (i + 1) ((i,h):s)  hs

Upvotes: 3

Related Questions