hw3.sml

exception NoAnswer

datatype pattern = Wildcard
		 | Variable of string
		 | UnitP
		 | ConstP of int
		 | TupleP of pattern list
		 | ConstructorP of string * pattern

datatype valu = Const of int
	      | Unit
	      | Tuple of valu list
	      | Constructor of string * valu

fun g f1 f2 p =
    let 
	val r = g f1 f2 
    in
	case p of
	    Wildcard          => f1 ()
	  | Variable x        => f2 x
	  | TupleP ps         => List.foldl (fn (p,i) => (r p) + i) 0 ps
	  | ConstructorP(_,p) => r p
	  | _                 => 0
    end


datatype typ = Anything
	     | UnitT
	     | IntT
	     | TupleT of typ list
	     | Datatype of string



fun only_capitals strs =
    List.filter (fn s => Char.isUpper(String.sub(s,0))) strs

fun longest_string1 strs = 
    case strs of
        [] => ""
        | s::strs' => 
            List.foldl (fn (sn,sl) => if String.size(sn) > String.size(sl) then sn else sl ) s strs'

fun longest_string2 strs = 
    case strs of
        [] => ""
        | s::strs' => 
            List.foldl (fn (sn,sl) => if String.size(sn) >= String.size(sl) then sn else sl ) s strs'

val longest_string_helper = fn f => fn strs =>
        case strs of
            [] => ""
            | s::strs' => List.foldl (fn (sn,sl) => if f (String.size(sn), String.size(sl)) then sn else sl ) s strs'

val longest_string3 = longest_string_helper (fn (s1, s2) => s1 > s2)

val longest_string4 = longest_string_helper (fn (s1, s2) => s1 >= s2)

val longest_capitalized = longest_string3 o only_capitals

val rev_string = String.implode o List.rev o String.explode

fun first_answer f ans =
    case List.filter (fn x => isSome(x)) (List.map f ans) of
        [] => raise NoAnswer
        | s::ss => valOf s 

fun all_answers f ans = 
    let fun helper acc hans =
        case hans of
            [] => SOME acc
            | hs::hans' => case f hs of
                NONE => NONE
                | SOME x => helper (x @ acc) hans'
    in
        helper [] ans
    end


fun count_wildcards p = 
    g (fn () => 1) (fn _ => 0) p

fun count_wild_and_variable_lengths p =
    g (fn () => 1) (fn x => String.size x) p

fun count_some_var (s,p) = 
    g (fn () => 0) (fn x => if x=s then 1 else 0) p


fun check_pat p = 
    let
        fun str_list (p, acc) =
            case p of
                Variable x => x::acc
                 | TupleP ps => List.foldl str_list acc ps
                 | ConstructorP(_,p') => str_list (p',acc) 
                 | _ => acc
        fun check ss =
            case ss of
                []=>true
                | s::ss' => if (List.exists (fn l => s=l) ss') then false else check ss'
    in check (str_list (p, []))
    end

fun match (v,p) = 
    case (v,p) of
        (_, Wildcard) => SOME []
        | (_, Variable x) => SOME [(x,v)]
        | (Unit, UnitP) => SOME []
        | (Const cv, ConstP cp) => if cv = cp then SOME [] else NONE
        | (Tuple vs, TupleP ps) => if length vs = length ps then all_answers match (ListPair.zip (vs,ps)) else NONE
        | (Constructor (sv,v'), ConstructorP (sp,p')) => if sv=sp then match (v',p') else NONE
        | _ => NONE


fun first_match v ps =
    SOME (first_answer (fn p => match (v,p)) ps)
    handle _ => NONE