Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I reduce syntactic clutter when tagging a polymorphic tree in Haskell?

So I want a type that represents trees containing a set of node-types. I would also like types that represent similar tree defined over overlapping sets. This is another version of the Typed AST problem. Say that my pool of node-types is:

data Lit = Lit Int
data Var = Var String
data Hole = Hole Int

A parse-tree can contain Lits or Vars but no Holes. A second kind tree called a template can contain Lits, Vars or Holes.

To keep things simple there is a single type of recursive node called Add.

data Parse = A Lit | B Var
data Template = C Lit | D Var | E Hole
data Tree a = Leaf a 
            | Add (Tree a) (Tree a)

So now I can declare data, and I can still pattern-match on it, the only problem is the syntactic clutter.

aParse = Add (A Lit 3) (B Var "x")
aTemplate = Add (C Lit 4) (E Hole 3)
fun (Add (A lit) (B var) = ...

What I would like is some sugar similar to :

ParseLit = A . Lit
TempLit = C . Lit 

Obviously aliases for compositions of constructors (not types) is not legal in Haskell. But what is the cleanest way to write this, avoiding as much boiler-plate as possible?

like image 742
Andrew Avatar asked Aug 24 '15 16:08

Andrew


1 Answers

The PatternSynonyms language extension can help here. It lets you specify aliases for patterns:

{-# LANGUAGE PatternSynonyms #-}

pattern ParseLit x = A (Lit x)

someFunc :: Parse -> Int
someFunc p = case p of
    ParseLit x -> x
    _ -> 0

There are two flavors of pattern synonyms: bidirectional (like in the example) and unidirectional. The bidirectional ones can also be used as constructors:

*Main> :t ParseLit
ParseLit :: Int -> Parse

*Main> ParseLit 77
like image 114
danidiaz Avatar answered Sep 29 '22 10:09

danidiaz