在HASKELL中找到最少的元组列表

Question

我试图找到具有最小距离（（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）]。我试图实现这一点，但我有一种问题，我认为这是与bas有关电子情况。有没有人可以帮助我？

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) 

在此先感谢！

Answer 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 

Answer 2

，已经排除disSolver到其自身的功能，这是很好的。您可以进一步并抽象出“按某个指定度量标准查找最小值”的算法。 closestTuple就是这两者的组成。 （除了我使用leventov的distSolver，而不是你disSolver，因为类型结合在一起更好。）

我选择使用的功能，而不是明确的模式匹配和递归管道证明minimaBy，因为我忽然想到在这种情况下，它更清晰且更不容易出错。

另请注意，我给出的类型minimaBy表示如果编译它，它会自动释放某些错误。我们不能意外地按照c类型（对应于closestTuple的签名中的(a, a)）进行排序，因为只有b被宣布执行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 

文档的链接为：

• Control.Arrow --- &&&
  • 忽略类型类现在
  • 假装(&&&) :: (b -> c) -> (b -> c') -> (b -> (c, c'))
• Data.Function --- on
• --- Data.List模块groupBy，sortBy
• Data.Maybe --- fromMaybe，listToMaybe
• 数据。奥德--- comparing