hacks

ropes.sml (2894B)

 (* Editor's note: transmuting an assignment from one CMU class to another...
  * Sometimes things are easier when the language isn't fighting you :)
  * Comments are lightly edited. Written around the spring of 2024. *)
 
 datatype rope = Leaf of string | Cat of rope ref * rope ref
 
 structure Rope = 
 struct
 fun size (ref (Leaf s)) = String.size s
   | size (ref (Cat(l, r))) = size l + size r
 
 fun charat (ref (Leaf s)) i = String.sub (s, i)
   | charat (ref (Cat(l, r))) i = let 
       val leftSize = size l
   in
     if leftSize > i then charat l i else charat r (i - leftSize)
   end
     
 fun toString (ref (Leaf s)) = s
   | toString (ref (Cat(l, r))) = (toString l) ^ (toString r)
 
 fun join (L, R) = ref (Cat(L, R))
 
 (* Nasty casework: the use of refcells and my lack of knowledge of their semantics also
  * means I had to punt the casework to a case expr so that I could return the original
  * reference if needed. *)					  
 fun sub R lo hi = 
     if (lo = 0 andalso hi = (size R)) then R else 
     (case R of 
          (ref (Leaf s)) => ref (Leaf(String.substring(s, lo, hi))) 
        | (ref (Cat(l, r))) => let 
              val leftSize = size l 
          in
              (case (hi < size l, size l <= lo) of
 				  (* is the substring all on the left? then recur on left *)
                   (true, _) => sub l lo hi
                   (* vice versa *)								   
                 | (_, true) => sub r 0 (hi - size l)
 				  (* otherwise take what we want from either side *)
                 | _ => join (sub l lo leftSize, sub r 0 (hi-leftSize))) 
          end)
 
 (* Takes a list of ropes and modifies them to reuse subtrees from earlier elements in
  * the list (thus 'reducing' the overall size of the collection of ropes). *)
 fun reduce ropes = let
     (* Gross and imperative code both in the hashtable usage and in the overuse of let
      * blocks to do things in sequence. In my defense it was 2AM when I had this idea. *)
     val ropeEqual = fn (R1, R2) => (toString R1) = (toString R2)
     val ropeHash = fn R => HashString.hashString (toString R)
     exception NotFound
     val H = HashTable.mkTable (ropeHash, ropeEqual) (100, NotFound)
                               
     fun reduceHelp H R  = 
         HashTable.lookup H R 
         handle NotFound => 
                let val () = (HashTable.insert H (R,R)) in 
                    (case R of (ref (Leaf s)) => R 
                             | (ref (Cat (l, r))) => join (reduceHelp H l, reduceHelp H r))
                end
     in
         map (fn x => let val () = x := !(reduceHelp H x) in x end) ropes        
 end
 end
 
 val r1 = ref (Cat (ref (Leaf "a"), ref (Leaf "br")))
 val r2 = ref (Cat (ref (Leaf "abr"), ref (Leaf "a")))
 val r3 = ref (Cat (ref (Leaf "a"), ref (Cat (ref (Leaf "br"), ref (Leaf "a")))))
 
 (* seems to work and like... it typechecks™ 
  * (but seriously, not rigorously tested) *)
 val out = Rope.reduce [r1, r2, r3]