ropes.hs

data Rope = Empty | Concat Int Rope Rope | Leaf String deriving (Show, Eq)

rope :: String -> Rope
rope "" = Empty
rope s = Leaf s

len :: Rope -> Int
len Empty = 0
len (Leaf s) = length s
len (Concat length _ _) = length

asString :: Rope -> String
asString Empty = ""
asString (Leaf s) = s
asString (Concat _ left right) = (asString left) ++ (asString right)

cat :: Rope -> Rope -> Rope
Empty `cat` a = a
a `cat` Empty = a
a `cat` b = Concat ((len a) + (len b)) a b

rsplitAt :: Int -> Rope -> (Rope, Rope)
rsplitAt i (Leaf s) = (rope s1, rope s2) where (s1, s2) = (splitAt i s)
rsplitAt i (Concat _ left right)
    | i < (len left) =
        let (r1, r2) = (rsplitAt i left)
        in (r1, r2 `cat` right)
    | otherwise =
        let (r1, r2) = (rsplitAt (i - (len left)) right)
        in (left `cat` r1, r2)