Ok, so I've been hacking with Haskell for a while now, and I want to share some of the wow factor:
I'm doing some graph-fu with meshes, something that is particularly problematic for reasons I won't go into today (watch this space). I extract the edges from a list of triangles, themselves extracted from a list of triangle strips, and immediately run into swearsville as both the extraction from triangles and the triangle strips introduce non-unique edges.
After realising it's borderline impossible to efficient edges uniquely even if I was going to refactor like crazy, I start thinking about checking for uniqueness. A naive approach is to check each item in the original list to see if there's an identical one. Eww. O(n^2) So what if we sort the list and then think about uniqueness. Then we can do uniqueness in O(n).
Then I realise I'm working with a non-trivial datatype
--Edge stores the indicies of my point Array. Eww, but fixing that comes later.
type Edge = (Int,Int)
and start worrying. Fortunately I check first
Prelude
> (1,
2) < (3,
4)
True
Prelude> "Wow" > "Haskell knows comparison-fu"
True
That's worth a victory dance on its own. Then I realise that I can drop duplicates at the same time by changing one of the comparisons.
-- A standard quick sort
qsort :: [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort ls ++ [x] ++ qsort hs
where
ls = [v | v <- xs, v <= x]
hs = [v | v <- xs, v > x]
-- A reasonably efficient way of getting unique data
uniQsort :: [a] -> [a]
uniQsort [] = []
uniQsort (x:xs) = uniQsort ls ++ [x] ++ uniQsort hs
where
ls = [v | v <- xs, v < x]
hs = [v | v <- xs, v > x]
--discarded = [v | v <- xs, v == x]
I now have a massive grin.
