tricu

An interpreted language for exploring Tree Calculus
Log | Files | Refs | README | LICENSE

Tree.hs (1102B)

      1 -- Lazy runtime trees and kernel reduction; no source-language representation.
      2 module Runtime.Tree where
      3 
      4 import qualified Data.Map as Map
      5 
      6 -- Tree Calculus Types
      7 data T = Leaf | Stem T | Fork T T
      8   deriving (Show, Eq, Ord)
      9 
     10 -- Environment containing previously evaluated TC terms
     11 type Env = Map.Map String T
     12 
     13 -- Triage Calculus Reduction Rules
     14 {-
     15   The t operator is left associative.
     16   1.  t  t      a b       -> a
     17   2.  t (t a)   b c       -> a c (b c)
     18   3a. t (t a b) c t       -> a
     19   3b. t (t a b) c (t u)   -> b u
     20   3c. t (t a b) c (t u v) -> c u v
     21 -}
     22 apply :: T -> T -> T
     23 apply (Fork Leaf a)         _         = a
     24 apply (Fork (Stem a) b) c             = apply (apply a c) (apply b c)
     25 apply (Fork (Fork _a _b) _c)  Leaf      = _a
     26 apply (Fork (Fork _a _b) _c) (Stem u)   = apply _b u
     27 apply (Fork (Fork _a _b) _c) (Fork u v) = apply (apply _c u) v
     28 -- Left associative `t`
     29 apply  Leaf b                         = Stem b
     30 apply (Stem a) b                      = Fork a b
     31 
     32 -- Booleans
     33 _false :: T
     34 _false = Leaf
     35 
     36 _true :: T
     37 _true = Stem Leaf
     38 
     39 _not :: T
     40 _not = Fork (Fork _true (Fork Leaf _false)) Leaf
     41