Zajímavosti z Haskellu: Lazy pattern matching

Za anglický nadpis se omlouvám, ale opravdu mě nenapadl žádný vhodný překlad tohoto slovního spojení ("líné hledání vzorů" či "líný pattern matching" zní divně). Lazy pattern matching (LPM) je typ pattern matchingu (PM), nebo, chcete-li, hledání vzorů, při kterém nedochází k okamžitému navázání hodnoty na vzor, ale až při prvním použití tohoto vzoru. V následujícím příspěvku bych chtěl ukázat, jak tato technika funguje a k čemu se dá použít.

Úvod

Mějme následující funkci, která pro neprázdný seznam vrací hodnotu True, a pro prázdný seznam vrátí hodnotu False.

f :: [a] -> Bool
f (_:_) = True
f []    = False

Pokud takovouto funkci aplikujeme na libovolnou hodnotu, dojde k jejímu vyhodnocení, aby se zjistilo, kterému vzoru odpovídá, a podle toho se vrátí příslušná pravá strana. Při použití PM tedy vždy dochází k vyhodnocení hodnoty, podle které se rozhoduje, kterému ze vzorů odpovídá (kromě jednoho speciálního případu, kterému se ale tady nebudu věnovat). Když se nad tím zamyslíte, tak to dává smysl -- bez vyhodnocení by nešlo určit, která pravá strana se má vrátit jako výsledek. Haskell ale také nabízí možnost, jak zabezpečit, že se hodnota, podle které se rozhoduje, nebude vyhodnocovat při samotném PM, ale až při prvním vyhodnocení na pravé straně (případně vůbec). Zaručí se to použitím speciálního operátoru ~ před vzorem:

f ~(_:_) = True
f []     = False

Vzorům ve tvaru ~vzor se říká "lazy patterns" či "irrefutable patterns" (bez překladu), a při PM vždy uspějí. Pokud teď aplikujeme na prázdný seznam tuto funkci f, tak dojde k vrácení hodnoty True, protože první vzor při PM vždy uspívá. Tato druhá definice funkce f by se ekvivalentně dala zapsat následujícím způsobem:

f _  = True
f [] = False

Tento příklad byl však čistě ilustrační a v praxi k ničemu není -- reálné použití bude následovat.

Reálný příklad použití

Následující příklad je převzat odtud. LPM se může hodit v případě, že se nepotřebujeme rozhodovat na základě hodnoty, ale na základě typu. Představte si, že chcete implementovat funkci, která podle typu parametru vrátí výchozí (default) hodnotu daného typu. Začneme takto:

class Def a where
    defValue :: a -> a

Jednotlivé instance pro základní typy definujeme snadno:

instance Def Bool where
    defValue _ = False
 
instance Def Int where
    defValue _ = 0

Zajímavější to bude např. u typu Maybe, protože chceme výchozí hodnotu pro předaný typ, ale konstruktorem hodnoty může být Nothing. Následující definice je sice funkční, ale pokud ji aplikujeme na Nothing :: X, tak místo chtěného Just (defValue X) obdržíme Nothing :: X.

instance Def a => Def (Maybe a) where
    defValue (Just x) = Just (defValue x)
    defValue Nothing  = Nothing

Jak už jsem psal, tak bychom raději chtěli Just (defValue X). Jak na to? Zde se nám (překvapivě) bude hodit LPM. Budeme předstírat, že jsme provedli úspěšný PM na Just x a využijeme toho k získání defValue x (i v případě, kdy je tato funkce aplikována na Nothing :: X).

instance Def a => Def (Maybe a) where
    defValue ~(Just x) = Just (defValue x)

Díky tomu, že se v definicích defValue pro základní typy hodnota x nikdy nevyhodnocuje (vždy je použito _), tak je to bezpečné. Jedinou vadou na kráse je to, že musíme Haskellu v určitých případech dodat typové anotace, jinak si nebude schopen sám poradit:

-- Vrátí "Just False"
defMB = defValue (Nothing :: Maybe Bool)

Další informace

Další informace k tomuto tématu lze nalézt v následujících zdrojích: 1, 2, 3, 4, 5, 6.