0

我试图找到具有特定点的最小距离（（x1，x2）和（y1，y2）距离= abs（y2-y1）+abs（x2-x1）的元组（一个或多个）。对于例子 ：

列表将是 [(1,2),(3,4),(5,4),(5,6),(9,12) ]

具体点是(xpos,ypos)=(4,4)。

然后我的函数应该返回 [(3,4),(5,4)]。我试图实现这个，但我有一个问题，我认为它与基本情况有关。有没有人可以帮助我？

disSolver xpos ypos coor = abs (xpos - (fst coor)) +abs(ypos-(snd coor))



closestTuple _ _ [] =[]
closestTuple xpos ypos (x:y:xs) = if (disSolver xpos ypos x)<= (disSolver xpos ypos y)
then [x] ++ closestTuple xpos ypos (xs)
else closestTuple xpos ypos (y:xs)

提前致谢 ！

4

2 回答 2

3

你已经考虑disSolver到它自己的功能，这很好。你可以走得更远，也可以抽象出“通过某些指定度量找到最小值”的算法。closestTuple那么只是两者的组成。（除了我使用 leventovdistSolver而不是你的disSolver，因为这些类型更好地结合在一起。）

我选择演示minimaBy使用函数管道而不是显式模式匹配和递归，因为我碰巧认为在这种情况下它更清晰且不易出错。

另请注意，我给出的类型minimaBy意味着如果它编译，它会自动没有某些错误。我们不能不小心按c类型排序（对应于(a, a)inclosestTuple的签名），因为 onlyb被声明为 implement Ord。

（话虽如此，我还没有编译或以其他方式测试过这段代码，它只能保证在我的脑海中完美地工作:-)）

import Control.Arrow ((&&&))
import Data.Function (on)
import Data.List (groupBy, sortBy)
import Data.Maybe (fromMaybe, listToMaybe)
import Data.Ord (comparing)

minimaBy :: Ord b => (c -> b) -> [c] -> [c]
minimaBy f = map fst
           . fromMaybe []
           . listToMaybe
           . groupBy ((==) `on` snd)
           . sortBy (comparing snd)
           . map (id &&& f)

closestTuple :: (Num a, Ord a) => (a, a) -> [(a, a)] -> [(a, a)]
closestTuple = minimaBy . distSolver

文档链接：

于 2013-03-24T11:53:20.357 回答
1

当要从中找到最近点的列表恰好包含 1 个元素时，您错过了这种情况。closestTuple您的实现逻辑似乎也存在错误。

这是我编写函数的方式：

distSolver :: Num a => (a, a) -> (a, a) -> a
distSolver (px, py) (x, y) = (abs (x - px)) + (abs (y - py))

closestTuple :: (Num a, Ord a) => (a, a) -> [(a, a)] -> [(a, a)]
closestTuple _ [] = []
closestTuple pos (x:xs) = mins (distSolver pos x) [x] pos xs

mins _ mxs _ [] = mxs
mins minDist mxs pos (x:xs)
    | dist < minDist  = mins dist [x] pos xs
    | dist == minDist = mins dist (x:mxs) pos xs
    | otherwise       = mins minDist mxs pos xs
  where dist = distSolver pos x
于 2013-03-24T10:42:33.457 回答