对称函数的模式

Question

尝试使用这个新的stackoverflow，如建议的:) 这并不是特定于haskell的，但在haskell中最清晰。

这里有一个模式，偶尔会出现：一个函数接受两个参数，并对它们进行对称处理。 mappend经常具有此属性。 一个例子：

-- | Merge sorted lists of ranges.
merge :: (Ord n) => [(n, n)] -> [(n, n)] -> [(n, n)]
merge [] r2 = r2
merge r1 [] = r1
merge r1@((s1, e1) : rest1) r2@((s2, e2) : rest2)
    | e1 < s2 = (s1, e1) : merge rest1 r2
    | e2 < s1 = (s2, e2) : merge r1 rest2
    | s1 >= s2 && e1 <= e2 = merge rest1 r2 -- 1 within 2
    | s2 >= s1 && e2 <= e1 = merge r1 rest2 -- 2 within 1
    | e1 > e2 = merge (merged : rest1) rest2
    | otherwise = merge rest1 (merged : rest2)
    where merged = (min s1 s2, max e1 e2)

请注意，对'r1'和'r2'的处理是对称的。实际上只有4种情况：与null合并产生非null范围，不重叠范围保持不变，一个包含在另一个中的子范围会被舍弃，重叠会产生合并范围并尝试将其与其他范围合并。然而，每个情况都有镜像变体，因此最终有8种情况，即使可以通过机械推导得出这4种情况的镜像。不仅容易犯错，由于对称性，类型检查器也无法捕捉错误。这种模式有没有名称？有没有一种方法来消除这种重复？我想我可以尝试为列表定义它，然后写'mappend a b = mconcat [a, b]'，但是对于我来说，问题的一般形式相当困难（例如，我很难想象应将合并后的间隔放回哪个列表）。定义mappend然后获取mconcat要容易得多。也许有一种更好的方法来考虑列表版本，以避免头部受伤？我觉得我想做的是“聚焦”于一种情况，这样我就可以用“这个”和“那个”来表述。这比在两个同等权限的'r1'和'r2'中思考要容易得多，那->这种情况应该隐含在这个->那个情况中。

- Evan Laforge

---

你的合并函数只有在假定排序的某些属性时才是可交换的。例如，如果 < 总是返回 True，则它不是可交换的。 - augustss

确实如此，尽管我想如果您提供意外的Ord或Eq实例，您可能会使许多函数表现出令人惊讶的行为。 - Evan Laforge

Answer 1

诀窍在于将两个独立的步骤合并。第一步仅是合并列表。第二步是合并区间，使它们不重叠。因此，将这两个步骤分开处理，一切都会变得更简单。

mergeList (x@(s1,_):xs) (y@(s2,_):ys) = case compare s1 s2 of
      LT -> x : merge xs (y:ys)
      GT -> y : merge (x:xs) ys
      EQ -> x : y : merge xs ys
mergeList xs ys = xs ++ ys

mergeRuns (x@(s1,e1):x'@(s2,e2):xs) 
    | e1 < s2   = x : mergeRuns (x':xs) -- x is less than and nonoverlapping
    | otherwise = mergeRuns ((s1, max e1 e2) : xs) -- there is overlap
mergeRuns x = x

merge xs ys = mergeRuns $ mergeList xs ys

(未测试)

如果您添加一些内联编译指示，ghc应该会负责为您生成更多融合代码。否则，您也可以手动合并它们，以得到更臃肿但更高效的实现。或者，您也可以不做任何操作，因为它应该已经非常高效了。

另一种方法是编写一个函数mergeCons :: (n,n) -> [(n,n)] -> [(n,n)]（实际上只是mergeRuns的一种变体），然后将其替换标准的cons函数在mergeList函数中。这将使内联推断变得更加容易。以下是一些演示解决方案的代码（同样未经测试）：

mergeCons x@(s1,e1) (x'@(s2,e2):xs) 
    | e1 < s2   = x : (x':xs) -- x is less than and nonoverlapping
    | otherwise = (s1, max e1 e2) `mergeCons` xs -- there is overlap
mergeCons x [] = [x]

merge' (x@(s1,_):xs) (y@(s2,_):ys) = case compare s1 s2 of
      LT -> x `mergeCons` merge xs (y:ys)
      GT -> y `mergeCons` merge (x:xs) ys
      EQ -> x `mergeCons` y `mergeCons` merge xs ys
merge' xs ys = xs ++ ys

- sclv

---

确实，我觉得这比我的好。mergeCons 对我来说感觉像是一个 foldr，我猜你可以用 foldr mergeCons 来得到 mergeRuns。下次遇到这种问题，我会更加努力地思考如何分解它的方法。 - Evan Laforge

@Evan 我认为你对于 foldr 是正确的。mergeCons 对于区间列表来说感觉是一个很好的基本原始操作，可以从中构建出许多片段。 - sclv

Answer 2

虽然这并不是针对你具体情况的解决方案，但是通常对于可交换函数，您可以在参数上定义任意顺序，如果它们的顺序“错误”，则使函数调用自身并翻转参数。

- hammar

---

好主意。我认为我可以用我的merge实现这个功能，只需要进行一些复杂的检查来确定参数是否按照规范顺序排列。但是这会让代码更难读懂，因为你需要确信这个检查是正确的，否则就会出现无限循环。但是在检查是微不足道的情况下或者镜像分支没有交错的情况下，这绝对是一个好主意。 - Evan Laforge