Miranda To Haskell - Was ist die verbesserte Version?

Question

Ich arbeite den Code aus this Papier aus. Es nervt mich, dass meine Übersetzung ausführlicher ist. Es fällt mir auf, dass ich etwas Offensichtliches vermisse, das es so prägnant machen würde wie das Original Miranda.

Hier ist der 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 

Beachten Sie die linke Seite von merge. Es erfasst den Fall, in dem alle vier Blätter den gleichen Wert haben. Ich kann keine direkte Transliteration in Haskell machen, denn ich werde mehrere Definitionen von x beanstanden. Hier ist meine 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 

Wie kann ich näher an, was in dem Miranda-Code ist hier los?

Answer 1

Als Referenz wird ein Muster mit einem wiederholten Namen nichtlinearen genannt. Miranda unterstützt diese und Haskell nicht. Es ist ein Design-Trade-off von der Comittee original Haskell Design zurückgenommen in 1988. This thread hat einige zusätzliche Gründe dafür, nicht-lineare Muster in Haskell nicht zu unterstützen.

Leider bedeutet dies, dass Sie nicht wirklich in der Nähe Miranda mit Haskells Anpassungsmuster erhalten. Sie müssen Code schreiben, der Werte für Gleichheit explizit vergleicht, wie Sie es haben.

Die eine Verbesserung, die Sie können leicht machen ist Ihre Fall loswerden: Wenn alle Wachen scheitern, bewegt sich Mustererkennung auf das nächste Muster. Sie könnten auch Ihre Gleichheitsüberprüfung etwas kürzer machen, aber Sie können den Scheck nicht vollständig loswerden. Hier ist eine Version, die ein bisschen verbessert mir scheint:

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

Sie können feststellen, dass uniplate oder so etwas wie es wirklich gut für Ihre Quadtree funktioniert:

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

Diese einfachen Generika sowie unsere Fähigkeit, Prädikate zu kombinieren mit Mustererkennung in einem case fix was eigentlich störte mich über beide Versionen, die die doppelte identische Zweige waren.