2

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

Improve this question
6
  • 1
    You could define a second helper function go' that mimics go, so that you can call go i s [] = go' i s [0], but I think that would get more complicated than what you have now. What you have now looks fine. Commented Apr 18, 2018 at 1:24
  • @chepner having a part in a function that adds a whole extra walk through of the list seems painful (doubling the number of passes just for one extra step) Commented Apr 18, 2018 at 1:50
  • 1
    It's not an extra walk; ++ is lazy, so each time you try to get an element from the list, h:hs just gets matched against x : xs ++ [0] instead of x:xs. ++ is only bad if you try to build up a list by appending to it one item at a time; here, you are only appending one single item. Commented Apr 18, 2018 at 2:40
  • @chepner I actually totally forgot about the lazy evaluation... thanks Commented Apr 18, 2018 at 11:05
  • 1
    @chepner It is an extra walk. Each time you try to get an element from the list, h:hs gets matched against xs ++ [0]; to evaluate xs ++ [0], the y:ys pattern in the implementation of ++ gets matched against xs. This is one extra match compared to not having called ++ -- in other words, over the course of touching the whole list, you have done one extra walk. Commented Apr 18, 2018 at 12:13

1 Answer 1

Reset to default
3

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
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Is this really equivalent? The original code, on [0] could recurse as [0] or [], depending on 0<tH. Here we always recurse as [], which however is handled as [0]. It's not completely obvious to me.
@chi I will answer in two ways: with an argument that it's correct, and with evidence. 1. It is correct: this code, when encountering [] (which really represents [0]) also dispatches on 0<tH. In one case it recurses like the original; in the other it doesn't, but if you look carefully at the original code you'll see that the "recursive" step it would do in that case always returns [], so recursion isn't actually needed. 2. QuickCheck does not find any examples where these two functions differ, even if you take the call to maximum out of both to make it easier to find counterexamples.
the code duplication was something I was hoping to avoid. I guess my implementation of the the algorithm is the problem. Do you have any suggestions of what I should i have done in the first place to avoid this problem?
@matthias Could you describe what you're trying to compute a bit more? I don't really understand your description or your code -- I arrived at this answer through purely mechanical transformations of your code, without being guided by intuition or insight.
Its a solution to finding the biggest rectangle in a histogram. (this problem geeksforgeeks.org/largest-rectangle-under-histogram). The algorithm is described there. It would be too much to write as a comment but basically "We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar".

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.