Haskell 见解

Question

我发现自己迫切需要您的见解。

这是我感兴趣的对象:

class Mergable m where
    merge :: m -> m -> Maybe m
    mergeList :: [m] -> [m]

    mergeList [] = []
    mergeList [x] = [x]
    mergeList (x:y:t) = r1 ++ mergeList (r2 ++ t)
        where
            (r1,r2) = case (x `merge` y) of
                Just m  -> ([ ], [m])
                Nothing -> ([x], [y])

但我稍后会回到它。现在我准备了一些例子:

data AffineTransform = Identity
                     | Translation Float Float
                     | Rotation Float
                     | Scaling Float Float
                     | Affine Matrix3x3

instance Monoid AffineTransform where
    mempty = Identity

    Identity `mappend` x = x
    x `mappend` Identity = x
    (Translation dx1 dy1) `mappend` (Translation dx2 dy2) = Translation (dx1+dx2) (dy1+dy2)
    (Rotation theta1) `mappend` (Rotation theta2) = Rotation (theta1+theta2)
    (Scaling sx1 sy1) `mappend` (Scaling sx2 sy2) = Scaling (sx1*sx2) (sy1*sy2)

    -- last resort: compose transforms from different subgroups 
    -- using an "expensive" matrix multiplication
    x `mappend` y = Affine (toMatrix x `mult3x3` toMatrix y) 

所以现在我可以这样做:

toMatrix $ Rotation theta1 `mappend` Translation dx1 dy1 `mappend` Translation dx2 dy2 `mappend` Rotation theta2

或更简短地说:

(toMatrix . mconcat) [Rotation theta1, Translation dx1 dy1, Translation dx2 dy2, Rotation theta2]

或更一般地说:

(toMatrix . (fold[r|r'|l|l'] mappend)) [Rotatio...], etc

在上面的例子中，第一次旋转和平移将(昂贵地)组合成一个矩阵；然后，该矩阵与平移相结合(也使用乘法)，然后再次使用乘法来产生最终结果，即使(由于关联性)中间的两个平移可以便宜地组合为总共两次乘法三个。

无论如何，我的 Mergable 类来救援:

instance Mergable AffineTransform where
    x `merge` Identity = Just x
    Identity `merge` x = Just x
    x@(Translation _ _) `merge` y@(Translation _ _) = Just $ x `mappend` y
    x@(Rotation _) `merge` y@(Rotation _) = Just $ x `mappend` y
    x@(Scaling _ _) `merge` y@(Scaling _ _) = Just $ x `mappend` y
    _ `merge` _ = Nothing

所以现在 (toMatrix . mconcat . mergeList) ~ (toMatrix . mconcat)，因为它应该:

mergeList [Rotation theta1, Translation dx1 dy1, Translation dx2 dy2, Rotation theta2] == [Rotation theta1, Translation (dx1+dx2) (dy1+dy2), Rotation theta2]

我想到的其他例子更多地涉及(代码方面)，所以我只会陈述这些想法。

假设我有一些

data Message = ...

和一个

dispatch :: [Message] -> IO a

其中 dispatch 从列表中获取消息，根据它的类型打开一个适当的 channel (文件、流等)，写入该消息，关闭 channel 并继续下一条消息。因此，如果打开和关闭 channel 是一项“昂贵”的操作，那么简单地组合(dispatch .mergeList)可以帮助以最小的努力提高性能。

其他时候我用它来处理 gui 应用程序中的事件，例如合并鼠标移动、按键、撤消重做系统中的命令等。

一般模式是我从列表中取出两个项目，检查它们是否以某种方式“可合并”，如果是，则尝试将结果与列表中的下一个项目合并，否则我将第一个项目保持原样并继续与下一对(现在我认为它有点像广义运行长度编码)

我的问题是我无法摆脱我正在重新发明轮子的感觉，并且必须在 haskell 中使用类似的结构。如果不是这样，那么:

1)如何将其推广到列表以外的其他容器？
2) 你能发现 Mergable 是一个实例的任何其他结构吗？ (特别是箭头，如果适用，我无法将头环绕在它们周围)
3)关于 mergeList 应该有多严格/懒惰以及如何将其呈现给用户的任何见解？
4)优化技巧？堆栈溢出？还要别的吗？

谢谢!

Answer 1

我不认为图书馆里已经有这样的东西。 Hoogle 和 Hayoo 没有找到任何合适的。
Mergeable (我认为它是这样拼写的)看起来像是 Monoid 的概括。 .不是 Arrow ， 对不起。

有时您需要合并保留顺序。有时您在合并时不需要保留顺序。

我可能会做类似的事情

newtype MergedInOrder a = MergedInOrder [a] -- without exporting the constructor

mergeInOrder :: Mergeable a => [a] -> MergedInOrder a
mergeInOrder = MergedInOrder . foldr f []
  where f x []            = [x]
        f x xs @ (y : ys) = case merge x y of
                                 Just z  -> z : ys
                                 Nothing -> x : xs

以及用于无序列表的类似新类型，它们利用并且不需要 Ord实例，分别。

这些新品种有明显的 Monoid实例。

我不认为我们可以编写代码来合并 Mergeable 的任意容器s，我认为必须为每个容器明确完成。