Miranda To Haskell - What is the Enhanced Version?

Question

I am developing code from this document. It annoyed me that my translation was more detailed. It seems to me that I am missing something obvious that would make it as brief as the original Miranda.

Here is 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))) where merge(Internal (Leaf(x), Leaf(x), Leaf(x), Leaf(x))) = Leaf(x) merge(other) = other 

Pay attention to the LHS merge . It captures the case when all four sheets have the same value. I cannot perform direct transliteration in Haskell, because I will receive a complaint about several x definitions. Here is my version:

 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@ (Internal (Leaf w) (Leaf x) (Leaf y) (Leaf z)) | (w == x) && (x == y) && (y == z) = Leaf x | otherwise = internal merge other = other 

How can I get closer to what's going on in Miranda's code?

Answer 1

For reference, a template with a duplicate name like this is called non-linear . Miranda supports this, and Haskell does not. This is a design compromise made by the original Haskell Design Committee back in 1988 . There is additional justification in this thread for the lack of support for non-linear patterns in Haskell.

Unfortunately, this means that you cannot get close to Miranda using the Haskell pattern matching. You will need to write code that explicitly compares values ​​for equality, just like you do.

The only improvement that you can easily make is to get rid of your othewise case: if all the defenders do not work, the pattern matching proceeds to the next pattern. You can also make the equality check a little shorter, but you cannot completely get rid of the check . Here is a version that has improved a bit for 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 

Answer 2

You may find that uniplate or something like this works fine for your quadrant:

 {-# 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 lw@ (Leaf w):xyz | all (lw ==) xyz -> lw _ -> t 

These simple generics plus our ability to combine predicates with pattern matching in the case fix what really bothered me about all versions that were duplicated identical branches.