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

Question

我正在计算 this 中的代码纸。我的翻译比较冗长，这让我很烦恼。我发现我遗漏了一些明显的东西，而这些东西可以使它像原来的米兰达一样简洁。

这是米兰达:

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

注意合并的左手边。它捕获所有四个叶子都具有相同值的情况。无法直接音译为 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

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

Answer 1

仅供引用，具有重复名称的模式称为非线性。 Miranda 支持这些，而 Haskell 不支持。这是最初 Haskell 设计委员会在 1988 中采取的设计权衡。 。 This thread Haskell 中不支持非线性模式还有一些额外的理由。

不幸的是，这意味着您无法使用 Haskell 的模式匹配真正接近 Miranda。您必须编写一些代码来显式比较值是否相等，就像您所做的那样。

您可以轻松做出的一个改进是摆脱否则情况:如果所有防护都失败，则模式匹配将转移到下一个模式。您还可以使相等性检查更短一些，但您无法完全摆脱检查。这是一个对我来说似乎有所改进的版本:

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