Geek Answers Handbook

Haskell Views

I really need your insights.

Here is my interesting thing:

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])

But I will return to him later. So far I have prepared some examples:

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)

So now I can do:

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

or more briefly:

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

or more broadly:

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

In the above examples, the first rotation and translation will be combined (expensively) with the matrix; then this matrix is ​​combined with a translation (also using multiplication), and then multiplication will be used again to obtain the final result, although (due to associativity) the two translations in the middle can be combined cheaply for only two out of three multiplications.

Anyway, my Mergable class comes to the rescue:

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

so now (toMatrix. mconcat. mergeList) ~ (toMatrix. mconcat), as it should:

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

Other examples that I mean are more involved (by code), so I’ll just formulate ideas.

,

data Message = ...

a

dispatch :: [Message] -> IO a

, (, ..), , . , "" , (. MergeList) .

gui, mousemoves, , undo-redo ..

, , , "" - , , , (, , )

, , , haskell , . , :

1) , ? 2) - ? (, , , ) 3) , / mergeList, ? 4) ? ? - ?

!

+5
2

, - . 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, , .

+2

. " Ord". , :

import Data.Monoid import Data.List

data AffineTransform = Identity
                     | Translation Float Float
                     | Rotation Float
                     | Scaling Float Float
                     | Affine Matrix3x3
                     deriving (Eq, Show, Ord)

-- some dummy definitions to satisfy the typechecker
data Matrix3x3 = Matrix3x3
               deriving (Eq, Show, Ord)

toMatrix :: AffineTransform -> Matrix3x3
toMatrix _ = Matrix3x3

mult3x3 :: Matrix3x3 -> Matrix3x3 -> Matrix3x3
mult3x3 _ _ = 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)

, :

mergeList :: [AffineTransform] -> [AffineTransform]
mergeList = map mconcat . groupBy sameConstructor . sort
  where sameConstructor Identity Identity                   = True
        sameConstructor (Translation _ _) (Translation _ _) = True
        sameConstructor (Rotation _) (Rotation _)           = True
        sameConstructor (Scaling _ _) (Scaling _ _)         = True
        sameConstructor (Affine _) (Affine _)               = True
        sameConstructor _ _                                 = False

, , , ? ( ?) Haskell, : group . sort . , sameConstructor mergeList:

mergeList :: (Monoid a, Ord a) => (a -> a -> Bool) -> [a] -> [a]
mergeList f = map mconcat . groupBy f . sort

P.S. , -

mergeList = map mconcat . groupBy canMerge

, merge mappend , .

0

More articles:


All Articles