Haskell ::循环中的递归递归 [英] Haskell :: Recursion in Recursion for Loop in Loop
问题描述
运行方式:基于元组(id，x，y)，找到x和y的最小最大值，然后创建两个点(红色点).元组中的每个元素根据到红点的距离分为两组.
How it goes: Based on the set of tuple (id, x, y), find the min max for x and y , then two dots (red points) created. Each element in tuple are grouped to two groups based on the distance towards the red dots.
每个组不能超过5个点.如果超过，则应计算新的组.我已经设法在第一阶段进行递归.但是我不知道第二阶段该怎么做.第二阶段应如下所示:
Each group cant exceed 5 dots. If exceed, new group should be computed. I've managed to do recursion for the first phase. But I have no idea how to do it for second phase. The second phase should look like this:
基于这两个组，同样需要找到x和y的最小最大值(每个组)，然后创建四个点(红色点).元组中的每个元素根据到红点的距离分为两组.
Based on these two groups, again it need to find the min max for x and y (for each group), then four dots (red points) created. Each element in tuple are grouped to two groups based on the distance towards the red dots.
getDistance :: (Int, Double, Double) -> (Int, Double, Double) -> Double
getDistance (_,x1,y1) (_,x2,y2) = sqrt $ (x1-x2)^2 + (y1-y2)^2
getTheClusterID :: (Int, Double, Double) -> Int
getTheClusterID (id, _, _) = id
idxy = [(id, x, y)]
createCluster id cs = [(id, minX, minY),(id+1, maxX, minY), (id+2, minX, maxY), (id+3, maxX, maxY)]
where minX = minimum $ map (\(_,x,_,_) -> x) cs
maxX = maximum $ map (\(_,x,_,_) -> x) cs
minY = minimum $ map (\(_,_,y,_) -> y) cs
maxY = maximum $ map (\(_,_,y,_) -> y) cs
idCluster = [1]
cluster = createCluster (last idCluster) idxy
clusterThis (id,a,b) = case (a,b) of
j | getDistance (a,b) (cluster!!0) < getDistance (a,b) (cluster!!1) &&
-> (getTheClusterID (cluster!!0), a, b)
j | getDistance (a,b) (cluster!!1) < getDistance (a,b) (cluster!!0) &&
-> (getTheClusterID (cluster!!1), a, b)
_ -> (getTheClusterID (cluster!!0), a, b)
groupAll = map clusterThis idxy
我正在从命令性转变为职能性.对不起，如果我的思考方式仍然是当务之急.还在学习.
I am moving from imperative to functional. Sorry if my way of thinking is still in imperative way. Still learning.
要澄清的是，这是原始数据的样子.
To clarify, this is the original data looks like.
推荐答案
编写这样的算法要遵循的基本原理是编写小型的组合程序.这样，每个程序都易于推理和隔离测试，最终程序可以用较小的程序编写.
The basic principle to follow in writing such an algorithm is to write small, compositional programs; each program is then easy to reason about and test in isolation, and the final program can be written in terms of the smaller ones.
算法可以总结如下:
- 计算限制点集的点.
- 将其余点分成两个簇，一个簇包含更接近最小点的点，另一个簇包含所有其他点(等效地，接近最大点的点).
- 如果任何集群包含5个以上的点，请对该集群重复该过程.
重复处理"步骤的存在表明这是分而治之问题.
The presence of a 'repeat the process' step indicates this to be a divide and conquer problem.
我认为每个点都不需要一个ID，因此我已经省去了.
I see no need for an ID for each point, so I've dispensed with this.
首先，为您要使用的 data 的每个类型定义数据类型:
To begin, define datatypes for each type of data you will be working with:
import Data.List (partition)
data Point = Point { ptX :: Double, ptY :: Double }
data Cluster = Cluster { clusterPts :: [Point] }
对于如此简单的数据来说，这似乎很愚蠢，但是它可以在调试过程中为您节省很多困惑.还要注意我们稍后将使用的功能的导入.
This may seem silly for such simple data, but it can potentially save you quite a bit of confusion during debugging. Also note the import of a function we will be using later.
第一步:
minMaxPoints :: [Point] -> (Point, Point)
minMaxPoints ps =
(Point minX minY
,Point maxX maxY)
where minX = minimum $ map ptX ps
maxX = maximum $ map ptX ps
minY = minimum $ map ptY ps
maxY = maximum $ map ptY ps
这与您的 createCluster 函数基本相同.
This is essentially the same as your createCluster function.
第二步:
pointDistance :: Point -> Point -> Double
pointDistance (Point x1 y1) (Point x2 y2) = sqrt $ (x1-x2)^2 + (y1-y2)^2
cluster1 :: [Point] -> [Cluster]
cluster1 ps =
let (mn, mx) = minMaxPoints ps
(psmn, psmx) = partition (\p -> pointDistance mn p < pointDistance mx p) ps
in [ Cluster psmn, Cluster psmx ]
该功能应该清除-它是将上述步骤的上述语句直接翻译成代码. partition 函数使用一个谓词和一个列表，并生成两个列表，第一个包含该谓词为true的所有元素，第二个包含它为false的所有元素. pointDistance 本质上与您的 getDistance 函数相同.
This function should clear - it is a direct translation of the above statement of this step into code. The partition function takes a predicate and a list and produces two lists, the first containing all elements for which the predicate is true, and the second all elements for which it is false. pointDistance is essentially the same as your getDistance function.
第三步:
cluster :: [Point] -> [Cluster]
cluster ps =
cluster1 ps >>= \cl@(Cluster c) ->
if length c > 5
then cluster c
else [cl]
这也非常直接地实现了上面的语句.也许唯一令人困惑的部分是>> = 的使用，该代码在这里的类型为 [a]->.(a-> [b])->[b] ;只需将给定函数应用于给定列表的每个元素，然后将结果连接起来(等效地，将其写为 flip concatMap ).
This also implements the statement above very directly. Perhaps the only confusing part is the use of >>=, which (here) has type [a] -> (a -> [b]) -> [b]; it simply applies the given function to each element of the given list, and concatenates the result (equivalently, it is written flip concatMap).
最后是您的测试用例(希望我已将其正确地从图片转换为Haskell数据):
Finally your test case (which I hope I've translated correctly from pictures to Haskell data):
testPts :: [Point]
testPts = map (uncurry Point)
[ (0,0), (1,0), (2,1), (0,2)
, (5,2), (5,4), (4,3), (4,4)
, (8,2), (9,3), (10,2)
, (11,4), (12,3), (13,3), (13,5) ]
main = mapM_ (print . map (\p -> (ptX p, ptY p)) . clusterPts) $ cluster testPts
运行该程序会产生
[(0.0,0.0),(0.0,2.0),(2.0,1.0),(1.0,0.0)]
[(4.0,4.0),(5.0,2.0),(5.0,4.0),(4.0,3.0)]
[(10.0,2.0),(9.0,3.0),(8.0,2.0)]
[(13.0,3.0),(12.0,3.0),(11.0,4.0),(13.0,5.0)]
这篇关于Haskell ::循环中的递归递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
