当前位置: 动力学知识库 > 问答 > 编程问答 >

Miranda To Haskell - What is the improved version?

问题描述:

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

where

merge(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 a

fix (Leaf a) = Leaf a

fix (Internal nw ne sw se) =

merge (Internal (fix nw) (fix ne) (fix sw) (fix se))

where

merge [email protected](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 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.

分享给朋友:
您可能感兴趣的文章:
随机阅读: