How does repmin place values in the tree in Haskell?

Question

I really like the repmin problem:

Write down repmin :: Tree Int -> Tree Int, which replaces all the numbers in the tree by their minimum in a single pass.

If I were writing something like this in python, I would go for passing values by their reference (let's say one-element lists instead of numbers is good enough):

def repmin(tree, wrapped_min_link=None):
    x, subforest = tree
    
    if wrapped_min_link is None: 
        wrapped_min_link = [x]
    else:
        [m] = wrapped_min_link
        wrapped_min_link = [min(m, x)]
        
    n = len(subforest)
    
    subforest_min = [None] * n
    for i in range(n):
        if subforest[i]:
            subforest_min[i] = repmin(subforest[i], wrapped_min_link)
    
    return (wrapped_min_link, subforest_min)

It seems to me like a fitting way to wrap one's head around the knot-tying solution in Haskell (I wrote this one for rose trees from Data.Tree):

copyRose :: Tree Int -> Int -> (Tree Int, Int)
copyRose (Node x []) m = (Node m [], x)
copyRose (Node x fo) m = 
 let
    unzipIdMinimum = 
     foldr (\ ~(a, b) ~(as, bmin) -> (a:as, b `min` bmin)) ([], maxBound :: Int)

    (fo', y)       = unzipIdMinimum . map (flip copyRose m) $ fo
 in (Node m fo', x `min` y)

repmin :: Tree Int -> Tree Int
repmin = (loop . uncurry) copyRose

Yet, I reckon the solutions to work very differently. Here is my understanding of the latter one:

Let us rewrite loop for (->) a bit:

loop f b = let cd = f (b, snd cd) in fst cd

I reckon it to be loop for (->)'s workalike as snd gives the same degree of laziness as pattern-matching within let.

So, when repmin traverses through the tree, it is:

• Building up the minimum in the tree to be returned as the second element of the pair.
• Leaves snd $ copyRose (tree, m) behind in every node.

Thus, when the traversal comes to an end, the programme knows the value of snd $ copyRose (tree, m) (that is, the minimum in the tree) and is able to show it whenever some node of the tree is being computed.

Do I understand repmin in Haskell correctly?

Answer 1

This is more an extended comment than an answer, but I don't really think of your implementation as single-pass. It looks like it traverses the tree once, producing a new, lazily-generated, tree and the global minimum, but it actually produces a lazily generated tree and an enormous tree of thunks that will eventually calculate the minimum. To avoid this, you can get closer to the Python code by generating the tree eagerly, keeping track of the minimum as you go.

You'll note that I've generalized the type from Int to an arbitrary Ord type. You'll also note that I've used to different type variables to refer to the type of elements in the given tree and the type of the minimum passed in to generate a new tree—this lets the type system tell me if I mix them up.

repmin :: Tree a -> Tree a
repmin = (loop . uncurry) copyRose

copyRose :: Ord a => Tree a -> b -> (Tree b, a)
copyRose (Node x ts) final_min
  | (ts', m) <- copyForest x ts final_min
  = (Node final_min ts', m)

copyForest :: Ord a => a -> [Tree a] -> b -> ([Tree b], a)
copyForest !m [] _final_min = ([], m)
copyForest !m (t : ts) final_min
  | (t', m') <- copyTree m t final_min
  , (ts', m'') <- copyForest m' ts final_min
  = (t' : ts', m'')

copyTree :: Ord a => a -> Tree a -> b -> (Tree b, a)
copyTree !m (Node x ts) final_min
  | (ts', m') <- copyForest (min m x) ts final_min
 = (Node final_min ts', m')

Exercise: rewrite this in monadic style using ReaderT to pass the global minimum and State to keep track of the minimum so far.