Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2017
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Control.Print.printDepth := 100;
  2.  
  3. datatype expression =  Constant of int |
  4.         Variable of string |
  5.         Operator of string * expression |
  6.         Pair of expression list |
  7.         List of expression list
  8.  
  9. datatype pattern = ConstantP of int
  10.     | VariableP of string
  11.     | OperatorP of string * pattern
  12.     | PairP of pattern list
  13.     | ListP of pattern list
  14.     | UnorderedListP of pattern list
  15.     | Wildcard
  16.  
  17. (*cross*)
  18. fun cross(tp) =
  19.     case tp of
  20.         (nil, xs) => nil
  21.         |(xs, nil) => nil
  22.         |(h::t, xs) => (List.map (fn x => (h, x) ) xs) @ cross(t, xs)
  23.  
  24. (*match*)
  25. fun match(ex: expression, pt: pattern) =
  26.     case pt of
  27.         Wildcard => SOME nil
  28.         | VariableP s => (case ex of
  29.                      Constant x => SOME[(s, Constant x)]
  30.                     | Variable y => SOME[(s, Variable y)]
  31.                     | Operator z => SOME[(s, Operator z)]
  32.                     | Pair w => SOME[(s, Pair w)]
  33.                     | List l => SOME[(s, List l)] )
  34.        
  35.         | ConstantP x => (case ex of
  36.                     Constant y => if(x = y) then SOME nil else NONE
  37.                     | _ => NONE)
  38.      
  39.         | ListP ps => ((
  40.             case ex of
  41.                 List xs => if(List.length(xs) <> List.length(ps)) then NONE else case (xs, ps) of
  42.                     (h::nil, g::nil) => match(h, g)
  43.                     | (h::t, g::r) => case match(h, g) of
  44.                         SOME v => SOME (v @ Option.valOf(match(List t, ListP r)))
  45.                         | NONE => NONE
  46.                     )handle Option => NONE)
  47.  
  48.         | PairP([a1, a2]) => (case ex of
  49.             Pair([b1,b2]) => (if(match(b2, a2) = NONE orelse match(b1, a1) = NONE) then NONE else SOME (Option.valOf(match(b1, a1)) @ Option.valOf(match(b2, a2)))))
  50.  
  51.         |OperatorP(a, x) => (case ex of
  52.             Operator(b, y) => if(a = b) then ( case(x,y) of (x,y) => match(y, x)) else NONE)
  53. (*eval*)
  54. exception InvalidVariable of string
  55. exception InvalidExpression  of expression
  56.  
  57. fun dobi(xs, var) =
  58.     case xs of
  59.         (a, b)::[] => if(a = var) then b else raise InvalidVariable a
  60.         |(a, b)::t => if(a = var) then b else dobi(t, var)
  61.  
  62. fun eval xs exp =
  63.     case exp of
  64.         Operator("+", a) => let
  65.             fun calc a =   case a of
  66.                 Constant a => a
  67.                 | Variable a => dobi(xs, a)
  68.                 | Pair [a1, a2] => calc(a1) + calc(a2)
  69.                 | Pair a => raise InvalidExpression (Pair a)
  70.                 | Operator(a, b) => eval xs (Operator(a,b))
  71.                 | List b => case b of
  72.                     nil => 0
  73.                     | b =>List.foldl (fn(x,y) => y + calc(x)) (calc(hd b)) (tl b)          
  74.         in
  75.             calc a
  76.         end
  77.         | Operator("-", a) => let
  78.             fun calc a =   case a of
  79.                 Constant a => a
  80.                 | Variable a => dobi(xs, a)
  81.                 | Pair [a1, a2] => calc(a1) - calc(a2)
  82.                 | Pair a => raise InvalidExpression (Pair a)
  83.                 | Operator(a, b) => eval xs (Operator(a,b))
  84.                 | List b => raise InvalidExpression (List b)
  85.         in
  86.             calc a
  87.         end
  88.          | Operator("*", a) => let
  89.             fun calc a =   case a of
  90.                 Constant a => a
  91.                 | Variable a => dobi(xs, a)
  92.                 | Pair [a1, a2] => calc(a1) * calc(a2)
  93.                 | Pair a => raise InvalidExpression (Pair a)
  94.                 | Operator(a, b) => eval xs (Operator(a,b))
  95.                 | List b => case b of
  96.                     nil => 1
  97.                     | b => List.foldl (fn(x,y) => y * calc(x)) (calc(hd b)) (tl b)
  98.         in
  99.             calc a
  100.         end
  101.         | Operator("/", a) => let
  102.             fun calc a =   case a of
  103.                 Constant a => a
  104.                 | Variable a => dobi(xs, a)
  105.                 | Pair [a1, a2] => if(calc(a2) = 0) then raise InvalidExpression (Pair [a1, a2]) else calc(a1) div calc(a2)
  106.                 | Pair a => raise InvalidExpression (Pair a)
  107.                 | Operator(a, b) => eval xs (Operator(a,b))
  108.                 | List b => raise InvalidExpression (List b)
  109.         in
  110.             calc a
  111.         end
  112.         | Operator("%", a) => let
  113.             fun calc a =   case a of
  114.                 Constant a => a
  115.                 | Variable a => dobi(xs, a)
  116.                 | Pair [a1, a2] => if(calc(a2) = 0) then raise InvalidExpression (Pair [a1, a2]) else calc(a1) mod calc(a2)
  117.                 | Pair a => raise InvalidExpression (Pair a)
  118.                 | Operator(a, b) => eval xs (Operator(a,b))
  119.                 | List b => raise InvalidExpression (List b)
  120.         in
  121.             calc a
  122.         end
  123.         | Operator(a, b) => raise InvalidExpression(Operator(a, b))
  124.    
  125. (* derivative *)
  126. fun derivative exp s = case exp of
  127.     Variable a => if(a = s) then Constant 1 else Constant 0
  128.     | Constant c => Constant 0
  129.     | Operator("+", Pair [a, b]) => Operator("+", Pair [derivative a s , derivative b s])
  130.     | Operator("-", Pair [a, b]) => Operator("-", Pair [derivative a s , derivative b s])
  131.     | Operator("/", Pair([a, b])) => Operator("/", Pair([ Operator("-", Pair([Operator("*", Pair([derivative a s, b])), Operator("*", Pair([a, derivative b s]))])), Operator("*", Pair([b, b]))]))
  132.     | Operator("*", Pair [a, b]) =>
  133.     case ([a,b]) of
  134.         ([Constant a, b]) => Operator("*", Pair([Constant a, derivative b s]))
  135.         | ([a, Constant b]) => Operator("*", Pair([derivative a s, Constant b]))
  136.         | ([a, b]) => Operator("+", Pair([Operator("*", Pair([derivative a s, b])), Operator("*", Pair([a, derivative b s]))]))
  137.  
  138. (*removeEmpty fn : expression -> expression - poenostavi izraz tako, da odstrani odvečne dele
  139. (množenja/seštevanja nobenega/enega elementa, //fix//
  140.  
  141. množenja, pri katerih je eden izmed členov 0,///fix///
  142. množenje z ena, //fix//
  143.  
  144. prištevanje ničle, //fix//
  145. odštevanje ničle, //fix//
  146. deljenje z 1 //fix// ). *)
  147.  
  148. (* (0+0) + 0*x*x + (1-0)*x*1*1
  149. removeEmpty (Operator ("+", List [
  150.     Operator ("+", Pair [Constant 0, Constant 0]),
  151.     Operator ("*", List [Constant 0, Variable "x", Variable "x"]),
  152.     Operator ("*", List [Operator ("-", Pair [Constant 1, Constant 0]), Variable "x", Constant 1, Constant 1])]))
  153.  val it = Variable "x" : expression  *)
  154.  
  155.    
  156.  
  157.     fun obdelajkrat l = case (List.exists (fn x => if(x = Constant 0) then true else false) ((hd l)::(List.filter (fn x => if(x = Constant 1) then false else true) (tl l)))) of
  158.                 true => Constant 0
  159.                 | false => List ((hd l)::(List.filter (fn x => if(x = Constant 1) then false else true) (tl l)))
  160.  
  161.     fun removeEmpty exp = case exp of
  162.         Operator("+", b) => (case b of
  163.             List l => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l) )) of
  164.                 0 => Constant 0
  165.                 | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))
  166.                 | _ => Operator("+", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))))
  167.  
  168.             | Pair p => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p) )) of
  169.                 0 => Constant 0
  170.                 | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))
  171.                 | _ => Operator("+", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))) )
  172.             | Constant c => Constant c
  173.             | Variable v => Variable v)
  174.  
  175.         | Operator("-", b) => (case b of
  176.             List l => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))) of
  177.                 0 => Constant 0
  178.                 | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))
  179.                 | _ => Operator("-", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))))
  180.  
  181.             | Pair p => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))) of
  182.                 0 => Constant 0
  183.                 | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))
  184.                 | _ => Operator("-", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))))
  185.             | Constant c => Constant c
  186.             | Variable v => Variable v)
  187.  
  188.         | Operator("/", b) => (case b of
  189.             List l => case (List.length((hd l)::(List.filter (fn x => if(x = Constant 1) then false else true) (tl l)))) of
  190.                 | 0 =>
  191.                 | 1 =>
  192.                 | _ =>
  193.             | Pair p => Pair ((hd p)::(List.filter (fn x => if(x = Constant 1) then false else true) (tl p)))
  194.             | Constant c => Constant c
  195.             | Variable v => Variable v)
  196.  
  197.         | Operator("*", b) => (case b of
  198.             List l => obdelajkrat l
  199.             | Pair p => obdelajkrat p
  200.             | Constant c => Constant c
  201.             | Variable v => Variable v)
  202.  
  203.         | Constant c => Constant c
  204.         | Variable v => Variable v
  205.        
  206.      
  207.  
  208.  
  209.              
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.          
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232. fun combinations a: 'a list list = a
  233. fun flatten exp = List [exp]
  234. fun joinSimilar exp = List [exp]
  235. fun divide(exp, exp1) = List [exp, exp1]
  236.  
  237.  
  238.  
  239. (*;;;; "type tests"  ;;;;
  240.  
  241. val test_cross_type: 'a list * 'b list -> ('a * 'b) list = cross
  242.  
  243. val test_match_type: expression * pattern -> (string * expression) list option = match
  244.  
  245. val test_eval_type: (string * int) list -> expression -> int = eval
  246.  
  247. val test_derivative_type: expression -> string -> expression = derivative
  248.  
  249. val test_removeEmpty_type: expression -> expression = removeEmpty
  250.  
  251. val test_combinations_type: 'a list list -> 'a list list = combinations
  252.  
  253. val test_flatten_type: expression -> expression = flatten
  254.  
  255. val test_joinSimilar_type: expression -> expression = joinSimilar
  256.  
  257. val test_divide_type: expression * expression -> expression = divide *)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement