1

我真的很喜欢这个repmin问题：

写下repmin :: Tree Int -> Tree Int，它在一次通过中将树中的所有数字替换为它们的最小值。

如果我在 python 中编写这样的东西，我会通过引用传递值（假设单元素列表而不是数字就足够了）：

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)

在我看来，这似乎是一种合适的方式来围绕 Haskell 中的打结解决方案（我从 为玫瑰树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

然而，我认为解决方案的工作方式非常不同。以下是我对后一种的理解：

让我们重写loop一下(->)：

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

我认为它与loopfor(->)的工作相似，因为snd它给出了与let.

因此，当repmin遍历树时，它是：

  • 在树中建立最小值，作为该对的第二个元素返回。
  • snd $ copyRose (tree, m)在每个节点中留下。

因此，当遍历结束时，程序知道snd $ copyRose (tree, m)（即树中的最小值）的值，并且能够在计算树的某个节点时显示它。

我repmin在 Haskell 中理解正确吗？

4

1 回答 1

2

这更像是一个扩展的评论而不是一个答案，但我并不认为你的实现是单程的。看起来它遍历了树一次，产生了一个新的、延迟生成的树和全局最小值，但它实际上产生了一个延迟生成的树和一个巨大的 thunk 树，最终将计算最小值。为避免这种情况，您可以通过急切地生成树来更接近 Python 代码，并随时跟踪最小值。

您会注意到我已经将类型从泛化为Int任意Ord类型。您还会注意到，我已经习惯了不同的类型变量来引用给定树中元素的类型以及传入的最小值以生成新树的类型——这让类型系统告诉我是否混合它们向上。

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')

练习：以单子风格重写此代码，ReaderT以通过全局最小值并State跟踪迄今为止的最小值。

于 2020-09-07T18:01:53.083 回答