私は問題が本当に好きrepminです：
を書き留め
repmin :: Tree Int -> Tree Intます。これにより、ツリー内のすべての数値が 1 回のパスで最小値に置き換えられます。
私がPythonでこのようなものを書いていたら、参照によって値を渡すことに行きます（数字の代わりに1要素のリストで十分だとしましょう）：
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
内のパターンマッチングと同じ程度の怠惰を与えるloopため、 for(->)の作業に似ていると思います。sndlet
したがって、repminツリーをトラバースすると、次のようになります。
- ペアの 2 番目の要素として返されるツリーの最小値を構築します。
snd $ copyRose (tree, m)すべてのノードに葉が残ります。
したがって、トラバーサルが終了すると、プログラムは の値snd $ copyRose (tree, m)(つまり、ツリー内の最小値) を認識し、ツリーのノードが計算されるたびにそれを表示できます。
repminHaskellで正しく理解できていますか?