funpat: A generalization of pattern matching

This library provides pattern matching with restricted function patterns (RFPs). An expression is an RFP iff exists an equivalent valid Haskell pattern. For example ("abc" ++ xs) is an RFP, because ('a' : 'b' : 'c' : xs) is an equivalent valid Haskell pattern. On the other hand, (xs ++ "abc") is not an RFP. Details are discussed in the paper Restricted Function Patterns presented at TFP 2011.

Example 1. Here is a function to chop off the prefix "prefix" of strings:

unprefix :: String -> String
unprefix s = match s $ do
   with $ \z ->   "prefix" ++ z ~> z
   with $ \z ->   z             ~> z

Example 2. Let's have a small embedded language:

data Expr = Symbol String | Expr :$ Expr
    deriving (Eq,Show,Typeable)

instance Num Expr where
    fromInteger n = Symbol $ show n
    a + b = Symbol "+" :$ a :$ b
    a * b = Symbol "*" :$ a :$ b
    ...

In order to allow pattern matching on expressions of type Expr, the following Matchable instance is needed:

instance Matchable Expr where
    Symbol s .=. Symbol z   = Just [s :=: z]
    (e :$ f) .=. (g :$ h)   = Just [e :=: g, f :=: h]
    _ .=. _                 = Nothing

Now we can pattern match on expressions even if the constructors of the Expr type were hidden:

transform :: Expr -> Expr
transform e = match e $ do
    with $ \a ->        0 + a       ~> a
    with $ \a b c ->    a * (b + c) ~> a * b + a * c
    with $ \a ->        a           ~> a

Modules

[Index]

Downloads

• funpat-0.1.tar.gz [browse] (Cabal source package)
• Package description (as included in the package)

Maintainer's Corner

Package maintainers

• GergelyDevai

For package maintainers and hackage trustees

• edit package information

Candidates

• No Candidates