# [Haskell-beginners] A strange expression in Quick Hull example

Zhi-Qiang Lei zhiqiang.lei at gmail.com
Tue Apr 24 22:36:32 CEST 2012

```I copy the Quick Hull snippet from http://darcs.haskell.org/packages/dph/examples/quickhull/QuickHull.hs
The "packed" expression in "hsplitList" is much confusing to me. Why does it have to zip points with cross? Is [ p | (c, p) <- cross, c > 0.0 ] not enough? Thanks.

data Point = Point !Double !Double
data Line  = Line  Point Point

instance Show Point where
show (Point x y) = show (x, y)

distance :: Point -> Line -> Double
distance (Point xo yo) (Line (Point x1 y1) (Point x2 y2))
= (x1 - xo) * (y2 - yo) - (y1 - yo) * (x2 - xo)

upper :: (a -> a -> Bool) -> [(a, b)] -> b
upper above = snd . foldl1 pick
where
pick left@(kl, _) right@(kr, _) | kl `above` kr = left
| otherwise     = right

hsplitList :: [Point] -> Line -> [Point]
hsplitList points line@(Line p1 p2)
| length packed < 2 = p1:packed
| otherwise         = hsplitList packed (Line p1 pm) ++ hsplitList packed (Line pm p2)
where
cross  = [ (distance p line, p) | p <- points ]
packed = [ p | (p, (c, _)) <- zip points cross, c > 0.0 ]

pm     = upper (>) cross

quickHullList :: [Point] -> [Point]
quickHullList [] = []
quickHullList points
= hsplitList points (Line minx maxx) ++ hsplitList points (Line maxx minx)
where
xs   = [ (x, p) | p@(Point x y) <- points ]
minx = upper (<) xs
maxx = upper (>) xs

Best regards,
Zhi-Qiang Lei
zhiqiang.lei at gmail.com

-------------- next part --------------
An HTML attachment was scrubbed...