Circular programming - replaces list items with a minimum value

Question

I just read this article on circular programming . It seems so alien to me. Although I can imagine the feedback as a lazily priced tone, which will later be judged by the desired result, just can't wrap your head around it. Therefore, I decided to write a function that replaces each element of the list with a minimum value.

 trace :: (a -> c -> (b,c)) -> a -> b trace fa = b where (b,c) = fac 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 am) 

But repminList [1,2,3] is equal to [2,3,3] . What will be the correct version?

Answer 1

Your problem is that you have two different variables m and one shadow above the other, so you are not using the actual circular variable at all. Here is a 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 last, smallest element of the list that you get as a circular parameter. The return value m' returned from the repIIminList call of repIIminList is the smallest value received so far, so it is important to add the final smallest value (i.e. m ) to the list of results, and then update the current smallest value, returning min a m' .

Answer 2

This is a pretty cool technique! Here's a work program that inspired you (I really didn’t read the article, except to look at the picture, so this may not be exactly what the author intended, but it works):

 looper :: (inputT -> feedfwdT -> feedbackT -> (feedbackT, outputT)) -> inputT -> feedfwdT -> outputT looper f input primer = output where (feedback, output) = f input primer feedback min_feedback :: (Ord a) => [a] -> Maybe a -> a -> (a, [a]) min_feedback [] (Just p) _ = (p, []) min_feedback (x:xs) partial_min minimum = (feedback, minimum:output) where new_partial_min = case partial_min of Nothing -> Just x Just p -> Just $ min xp (feedback, output) = min_feedback xs new_partial_min minimum min_looped :: (Ord a) => [a] -> [a] min_looped input = looper min_feedback input Nothing main = print $ min_looped [1,4,6,2,6,3,-1,6,3,6,10] 

The key point here is that you need more than a feedback channel, you also need a direct channel to determine the minimum value on the first pass through the loop. My ASCII art skills are not up to the standard set in the article, so you just need to do this with this picture: A look-ahead value is the minimum value that is still displayed in the list. The primer launches a direct connection channel. The feedback channel returns the result value from the direct access channel up to the beginning of the list. Finally, the feedback value becomes the minimum value that is used to populate the output list.

Answer 3

I'm too tired to parse your code, use your intention and error. However, I will be happy to show you how I avoid thinking about it when I bind to the main node.

This is the state of Monad, yes! My use of the state monad (see below) is just a small plumbing that tracks one current value in a way that allows me to evaluate and update the value.

• repMin starts the calculation, taking into account the empty list, and then starts the state monad.
• Our working action f is provided with an input list and a minimal element in the list (currently thunk, don't rate!)
• f traverses a list that computes a minimum on the path, and replacing each element with a minimum value of m , which may be known but not yet estimated.

Code:

 import Control.Monad.State repMin :: [Int] -> [Int] repMin [] = [] repMin xs@ (x:_) = let (v,m) = runState (fm xs) x in v f :: Int -> [Int] -> State Int [Int] fm xs = mapM (λx -> checkMin x >> return m) xs where checkMin :: Int -> State Int () checkMin x = modify (min x) 

Notice that lazyness flows here and we get the image.

Answer 4

it

 repIIminList (x:[]) m' = ([m'], x) repIIminList (x:xs) m' = (m' : xs', min xm) where (xs', m) = repIIminList xs m' 

m is the current minimum, m' is the final minimum, xs is the current list, xs' is the final list. That is, repIIminList gets a list and a number and recursively replaces each element in the list with that number. repIIminList also calculates the minimum list. trace applies repIIminList to the minimum calculated by repIIminList itself.

Using the state monad, you can rewrite this in a rather explicit way:

 repminList :: [Int] -> [Int] repminList [] = [] repminList (x:xs) = evalState (go xs) x where go [] = get >>= return . (:[]) go (x:xs) = modify (min x) >> flip (:) <$> go xs <*> get 

Or directly using the CPS style:

 repminList :: [Int] -> [Int] repminList [] = [] repminList (x:xs) = foldr (\xr -> (\(x:xs) -> x:x:xs) . r . min x) (:[]) xs x