data Quad p v = Nil
              | Node (p, p) v
                (Quad p v) -- NW
                (Quad p v) -- NE
                (Quad p v) -- SE
                (Quad p v) -- SW
                deriving (Show)

insert :: (Ord p) => (p, p) -> v -> Quad p v -> Quad p v
insert loc val Nil = Node loc val Nil Nil Nil Nil
insert loc@(x, y) val (Node loc0@(x0, y0) val0 nw ne se sw) = Node loc0 val0 cnw cne cse csw
    where
        cnw = if x < x0 && y > y0 then insert loc val nw else nw
        cne = if x >= x0 && y > y0 then insert loc val ne else ne
        cse = if x >= x0 && y <= y0 then insert loc val se else se
        csw = if x < x0 && y <= y0 then insert loc val sw else sw

region :: (Ord p) => (p, p) -> (p, p) -> Quad p v -> [v]
region _ _ Nil = []
region pl@(xl, yl) pr@(xr, yr) (Node loc@(x, y) val nw ne se sw) = pnw ++ pne ++ pse ++ psw ++ here
    where
        here = if x >= xl && x < xr && y >= yl && y < yr then [val] else []
        pnw = if xl >= x || yr <= y then [] else region pl pr nw
        pne = if xr < x  || yr <= y then [] else region pl pr ne
        pse = if xr < x  || yl > y  then [] else region pl pr se
        psw = if xl >= x || yl > y  then [] else region pl pr sw

quad = Nil
quad1 = insert (0, 1) "a" quad
quad2 = insert (-1, -1) "b" quad1
quad3 = insert (7, 7) "c" quad2
quad4 = insert (100, 100) "d" quad3