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.合并列表)〜(toMatrix.mconcat),因为它应该:

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

我想到的其他例子更多(代码方面),所以我只是陈述想法.

比方说我有一些

data Message = ...

和a

dispatch :: [Message] -> IO a

其中dispatch从列表中获取消息,具体取决于它的类型打开适当的通道(文件,流等),写入该消息,关闭通道并继续下一条消息.因此,如果打开和关闭通道是一项"昂贵"的操作,那么简单地编写(dispatch.合并列表)可以帮助您以最小的努力提高性能.

其他时候我用它来处理gui应用程序中的事件,比如合并鼠标移动,按键,undo-redo系统中的命令等.

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

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

1)如何将其推广到列表以外的其他容器？2)你能发现任何其他结构Mergable是一个实例吗？(特别是Arrows,如果适用的话,我很难绕过它们)3)有关mergeList的严格/懒惰的任何见解以及如何将它呈现给用户？4)优化提示？堆栈溢出？还要别的吗？

谢谢!

Answer 1

我认为图书馆里还没有这样的东西。胡格尔和哈尤没有找到任何合适的东西。

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例子。

我不认为我们可以编写代码来合并Mergeables 的任意容器，我认为必须为每个容器显式完成。