Anonymous user
K-d tree: Difference between revisions
m
→{{header|Haskell}}
(Add Haskell - K-d Tree) |
|||
Line 826:
There is a space leak when creating the trees which will lead to terrible performance on massive trees. This can probably be quelled with strictness annotations.
<lang Haskell>import System.Random
import Data.List (sortBy, genericLength, minimumBy)
import Data.Ord (comparing)
-- A finite list of dimensional accessors tell a KDTree how to get a
Line 851 ⟶ 852:
sqrDist dims a b = sum $ map square $ zipWith (-) a' b'
where
a' = map (
b' = map (
square :: Num a => a -> a
square
-- Insert a value into a k-d tree.
Line 881 ⟶ 882:
fList _ [] = Empty
fList (d:ds) values =
let sorted = sortBy (
(lower, higher) = splitAt (genericLength sorted `div` 2) sorted
in case higher of
Line 1,000 ⟶ 1,001:
-- Naive nearest search used to confirm results.
linearNearest :: (Ord b, Num b) => DimensionalAccessors a b -> a -> [a] -> Maybe a
linearNearest _ _ []
linearNearest dims value
main :: IO ()
|