Circular programming in Haskell for an imperative programmer

I’ve been learning up on arrows as a good framework to create my robot control software for Maya. I need the ability to manage a large amount of code and conciseness and modularity is paramount. Arrows seem very natural to model stream/dataflow operations and you can compose actions with any custom vocabulary.
While I was learning, I came across ArrowLoop typeclass, that extends looping in Arrows. This is how it is defined:
class Arrow a => ArrowLoop a whereloop :: a (b, d) (c, d) -> a b c
 Looking at the type signature of loop, it looks like it takes an arrow has inputs (bd) and outputs (c,d). So far so good. The output of this function seems to have no mention of d. The implementation of this function takes d from the output, and feeds it back into the input!
What does it mean to have the output fed back to a function as the input?
Searching for this led me to this page, which does a pretty good job of telling you what it does. Specifically, their example is a good place to start. Its simple and easy to follow:
data Tree a = Branch Tree Tree | Leaf a
trace :: (input -> feedback -> (output, feedback)) -> input -> output
trace f input = let (output, feedback) = f input feedback
in output
repmin :: Ord a => Tree a -> Tree a
repmin = trace repIImin
 
repIImin :: Ord a => Tree a -> a -> (Tree a, a)
repIImin (Leaf minval) rep = (Leaf rep, minval)
repIImin (Branch left right) rep = let
(left', min_left) = repIImin left rep
(right', min_right) = repIImin right rep
in (Branch left' right', min min_left min_right)
repmin takes a value of type Tree as input and outputs a Tree with the same structure as the input, but with the values of the leaves replaced with the min val of the leaves of the input tree. Note that trace is similar to loop(from ArrowLoop), in that the given function f is invoked with a variable from its output (feedback).
There is an explanation given for how repmin works with trace, but for some reason, the explanation left me unsatisfied. It told me how to think of the feedback variable (d), but didn’t explain how the computation actually occurred/how the program was actually executed. Coming from a imperative programming background, it is important to me to know how the program is executed. So here’s my explanation about how the program functions:
The important thing is to notice how a compiler/interpreter of Haskell will run the code in trace. It will notice that the variable in function application of f also appears on the output bindings. Haskell being a lazy language, feedback is a boxed value that will at any point in time either contain either an actual value, or a thunk (piece of code) that will compute the value. At the beginning of program execution,
thunk_feedback = snd thunk_f_app
thunk_f_app = f input thunk_feedback
where thunk_f_app is the thunk for the function application in trace (f input feedback). I left out thunks for input, f, snd for brevity. Now the program makes sense, as what you’re really doing is replacing the values in leaves with the feedback (i.e. they all now share a reference to the feedback thunk) and the top most Branch/Leaf in the input tree sets the value/thunk for feedback. A simple (possibly incorrect) way to think about this in an imperative context is to imagine setting the Leaf value as a pointer to feedback, whose value is being computed while the tree is traversed.
Lets run through a simple example. Here’s a tree with one branch and two leaves:
After we’ve repmin’ed it, here’s how the new tree looks like:
<feedback> is the feedback thunk, which when forced to evaluation, will evaluate to (min a b).
The trick to using trace here is that the code never looks into feedback, it merely uses it as a reference, until its value is actually set, which in repmin is just before the function returns. If we did look into feedback while in repmin, we would end up looping to infinity(non termination). There are cases when we can look into the value, provided we only look at parts that have been already calculated. Constructors can serve as evaluation barricades, letting you only evaluate/see parts you want and ignore others.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload the CAPTCHA.