Miranda To Haskell - 改进版本是什么？

Question

我从工作了代码此文件.我的翻译更加冗长,这让我烦恼.它发生在我身上我错过了一些显而易见的东西,它会像原来的米兰达一样简洁.

这是米兰达:

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

请注意LHS merge.它捕获了所有四个叶子具有相同值的情况.不能直接音译到Haskell,因为我会得到多个定义的抱怨x.这是我的版本:

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

我怎样才能更接近Miranda代码中发生的事情？

Answer 1

作为参考,具有类似重复名称的模式称为非线性.Miranda支持这些,而Haskell则不支持.这是1988年由原 Haskell设计委员会进行的设计权衡.该线程有一些额外的理由,不支持Haskell中的非线性模式.

不幸的是,这意味着你无法使用Haskell的模式匹配来接近Miranda.您必须编写一些明确比较相等值的代码,就像您所拥有的那样.

你可以轻松做出的一个改进是摆脱你的othewise情况:如果所有的守卫都失败了,模式匹配就会转移到下一个模式.你也可以让你的等式检查更短,但你不能完全摆脱检查.这是一个看起来有点改进的版本:

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

你可能会发现uniplate或类似的东西对你的四叉树很有效:

{-# 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

这些简单的泛型加上我们将谓词和模式匹配组合在一个case修复中的能力实际上困扰了我两个版本的重复相同的分支.