用于“对称”功能 [英] patterns for "symmetric" functions
问题描述
这是每隔一段时间出现的模式和一段时间：一个函数需要两个对称对待的参数。 mappends经常拥有这个属性。举个例子：
- |合并排序的范围列表。
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）：合并rest1 r2
| e2< s1 =（s2，e2）：合并r1 rest2
| s1> = s2&& e1 <= e2 =在2
|内合并rest1 r2 - 1 s2> = s1&& e2 <= e1 =在1
|内合并r1 rest2-2 e1> e2 =合并（merged：rest1）rest2
|否则= merge rest1（merged：rest2）
where merged =（min s1 s2，max e1 e2）
注意'r1'和'r2'的处理是对称的。实际上只有4种情况：与null合并产生非null值，不重叠会使范围保持不变，其中一个包含在另一个抛出的范围内，重叠会创建合并范围并尝试将其与其余的合并。然而，每种情况下都有一个镜像变体，因此即使镜像4可以机械地派生出来，也会变成8。不仅有两倍的错误空间，由于对称性，错误不会被类型检测器捕获。这种模式有没有名字？一种分析重复的方法？我想我可以尝试将它定义为一个列表，然后写'mappend ab = mconcat [a，b]'，但是这个问题对我来说很难用一般形式来考虑（例如，它让我感到头疼尝试考虑将哪个列表放回合并间隔）。定义mappend然后让mconcat脱离这个更容易。也许有更好的方式来思考列表版本，以避免头部受伤？
我想我要做的是重点在一个案件，所以我可以用这个和那个来写。这不仅比两个同样特权的'r1'和'r2'更容易想到，那个 - >这个情况应该从这个 - >那个隐含。
诀窍是你正在融合两个独立的步骤。第一步就是合并列表。第二个是合并间隔，使它们不重叠。
mergeList（x @（s1，_）：xs）（y @（s2） ，_）：ys）=案例比较s1 s2 of
LT - > x：合并xs（y：ys）
GT - > y：merge（x：xs）ys
EQ - > x：y：合并xs ys
mergeList xs ys = xs ++ ys
mergeRuns（x @（s1，e1）：x'@（s2，e2）：xs）
| e1< s2 = x：mergeRuns（x'：xs） - x小于并且不重叠
|否则= mergeRuns（（s1，max e1 e2）：xs） - 存在重叠
mergeRuns x = x
合并xs ys = mergeRuns $ mergeList xs ys
<
$（未经测试）
如果添加了一些内联编译指示，ghc应该请注意为您生成更加融合的代码。否则，你可以用手融合它们来派生更庞大但更高效的实现。我们的，你可以留下它，因为它应该是非常有效的。
另一种方法是编写一个函数 mergeCons :: （n，n）→> [（n，n）] - > [（n，n）] （它实际上只是 mergeRuns 的变体），然后用 mergeList 函数。这会使内联的推理更容易一些。下面是一些演示该解决方案的代码（再次未经测试）：
$ merge $ x $（s1，e1） e2）：xs）
| e1< s2 = x：（x'：xs） - x小于并且不重叠
|否则=（s1，max e1 e2）`mergeCons` xs - 存在重叠
mergeCons x [] = [x]
merge'（x @（s1，_）：xs ）（y @（s2，_）：ys）=案例比较s1 s2 of
LT - > x`mergeCons`合并xs（y：ys）
GT - > y`mergeCons` merge（x：xs）ys
EQ - > x`mergeCons` y`mergeCons`合并xs ys
合并'xs ys = xs ++ ys
Trying out this new stackoverflow thing, as suggested :) This is not really haskell specific, but it's clearest in haskell.
Here's a pattern that comes up every once and a while: a function takes two arguments which it treats symmetrically. mappends frequently have this property. An example:
-- | 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)
Notice that the treatment of 'r1' and 'r2' is symmetrical. There are really only 4 cases: merge with a null yields the non-null one, not overlapping yields the range unchanged, one contained in the other tosses the subsumed range, and overlapping creates a merged range and tries to merge it with the rest.
However, each case has a mirrored variant so there winds up being 8, even though the mirror 4 can be derived mechanically. Not only is there twice as much room to make mistakes, due to the symmetry the mistakes won't be caught by the typechecker. Is there a name for this pattern? A way to factor out the repetition? I suppose I can try to define it for a list and then write 'mappend a b = mconcat [a, b]', but the problem is rather harder for me to think of in the general form (for example, it hurts my head to try to think of which list to put the merged interval back on). It's so much easier to define mappend and then get mconcat out of that. Maybe there's a better way to think of the list version to avoid the head hurting?
What I think I want to do is "focus" on one case, so I can write in terms of "this" and "that". Not only is this easier to think of than two equally priviledged 'r1' and 'r2', the that->this case should be implicit from the this->that one.
The trick is that you're fusing two seperate steps. The first step is just merging lists. The second is merging intervals such that they do not overlap. Factor out the two steps and everthing simplifies.
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
(untested)
If you add some inline pragmas, ghc should take care of generating somewhat more fused code for you. Otherwise, you could fuse them by hand to derive a bulkier but more efficient implementation. Our, you could just leave it be since it should be pretty efficient as is anyway.
Another approach would be to write a function mergeCons :: (n,n) -> [(n,n)] -> [(n,n)] (which is really just a variation of mergeRuns) and then substitute that for standard cons in the mergeList function. That would make reasoning about inlining somewhat easier. Here's some code demonstrating that solution (again untested):
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
这篇关于用于“对称”功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
