I'm working out the code from this paper. It's bugging me that my translation is more verbose. It occurs to me I'm missing something obvious that would make it as succinct as the original Miranda.

Here's the Miranda:

``fix :: qtree(*) -> qtree(*)fix(Leaf(x)) = Leaf(x)fix(Internal(nw, ne, sw, se)) =merge(Internal(fix(nw), fix(ne), fix(sw), fix(se)))wheremerge(Internal (Leaf(x), Leaf(x), Leaf(x), Leaf(x))) = Leaf(x)merge(other) = other``

Notice the LHS of `merge`. It captures the case where all four leaves have the same value. Can't do a straight transliteration into Haskell, for I'll get a complaint of multiple definitions of `x`. Here's my version:

``fix :: (Eq a) => QTree a -> QTree afix (Leaf a) = Leaf afix (Internal nw ne sw se) =merge (Internal (fix nw) (fix ne) (fix sw) (fix se))wheremerge [email protected](Internal (Leaf w) (Leaf x) (Leaf y) (Leaf z))| (w == x) && (x == y) && (y == z) = Leaf x| otherwise = internalmerge other = other``

How can I get closer to what is going on in the Miranda code?

For reference, a pattern with a repeated name like that is called non-linear. Miranda supports these and Haskell doesn't. It's a design trade-off taken by the original Haskell design comittee back in 1988. This thread has some additional rationale for not supporting non-linear patterns in Haskell.

Unfortunately, this means that you can't really get close to Miranda using Haskell's pattern matching. You'll have to write some code that explicitly compares values for equality, like you have.

The one improvement you can easily make is to get rid of your `othewise` case: if all the guards fail, pattern matching moves on to the next pattern. You could also make your equality check a bit shorter, but you can't get rid of the check completely. Here's a version that seems a bit improved to me:

``````fix :: (Eq a) => QTree a -> QTree a
fix (Leaf a) = Leaf a
fix (Internal nw ne sw se) =
merge (Internal (fix nw) (fix ne) (fix sw) (fix se))
where merge (Internal (Leaf w) (Leaf x) (Leaf y) (Leaf z))
| all (== w) [x, y, z] = Leaf x
merge other = other
``````

You might find that uniplate or something like it works really well for your quadtree:

``````{-# LANGUAGE DeriveDataTypeable #-}
import Data.Generics.Uniplate.Data
import Data.Data(Data)
import Data.Typeable(Typeable)

data QTree a = Internal (QTree a) (QTree a) (QTree a) (QTree a)
| Leaf a
deriving (Data,Typeable -- for uniplate
, Eq, Show)
-- not tested:
fix :: (Data a, Eq a) => QTree a -> QTree a
fix t = case map fix \$ children t of
[email protected](Leaf w):xyz
| all (lw ==) xyz -> lw
_                   -> t
``````

These simple generics plus our ability to combine predicates with pattern matching in a `case` fix what actually bothered me about both versions which were the duplicated identical branches.

Top