Circular programming - replace list elements by minimum value

Question

I've just read this article about circular programming. It seems so alien to me. Although I can imagine the feedback as lazily evaluated thunk that will be evaluated to desired result later, just can't wrap my head around it. So I decided to write function that replaces every element of a list with it's minimum value.

trace :: (a -> c -> (b,c)) -> a -> b
trace f a = b
    where (b,c) = f a c

repminList :: (Num a, Ord a) => [a] -> [a]
repminList = trace repIIminList 

repIIminList [x] m = ([m], x)
repIIminList (a:as) m = let (replaced, m) = repIIminList as m 
                        in (m : replaced, min a m)

But repminList [1,2,3] equals to [2,3,3]. What would be the correct version?

Answer 1

Your problem is that you have two different m variables and one shadows over the other so you don't end up using the actual circular variable at all. Here's the fixed version of your repIIminList:

repIIminList [x] m = ([m], x)
repIIminList (a:as) m = let (replaced, m') = repIIminList as m
                        in (m : replaced, min a m')

Here m is the final, smallest element of the list that you receive as circular parameter. The m' returned from the recursive call to repIIminList is the smallest value seen so far, so it's important that you append the final smallest value (i.e. m) to the result list and then update the current smallest value by returning min a m'.