使用邊界函數對列表進行聚類

給出一個列表，我想用「邊界函數」將它分成多個簇。這樣的功能將需要兩個連續的列表元素並決定它們是否應該屬於同一個集羣。使用邊界函數對列表進行聚類

所以基本上，我想是這樣的：

clusterBy :: (a -> a -> Bool) -> [a] -> [[a]] 

ghci> farAway x y = abs (x - y) > 10 
ghci> clusterBy farAway [1, 4, 18, 23, 1, 17, 21, 12, 30, 39, 48] 
[[1, 4], [18, 23], [1], [17, 21, 12], [30, 39, 48]]

仰望它Hoogle這種類型的聲明只產生groupBy這不是我所需要的東西（它沒有考慮要素的順序考慮）。

是否有任何類似的庫函數？或者，也可以：它如何能夠乾淨地實施，即不採用尾遞歸循環？

編輯：作爲參考，我設法編造實行的是以下幾點：

clusterBy :: (a -> a -> Bool) -> [a] -> [[a]] 
clusterBy isBoundary list = 
loop list [] [] 
    where 
     loop (first:rest) [] result = loop rest [first] result 
     loop [email protected](next:rest) cluster result = 
      if isBoundary (head cluster) next then 
       loop list [] ((reverse cluster):result) 
      else 
       loop rest (next:cluster) result 
     loop [] [email protected](_:_) result = cluster:result 
     loop _ _ result = result

來源

2011-12-27 Xion

爲什麼尾部遞歸循環不乾淨？避免這種直接解決方案的目的是什麼？ – 2011-12-27 18:09:02

我編輯了這個問題，添加了我設法提出的尾遞歸版本。我對終端條件的數量和總體冗長度感到不滿。坦率地說，它看起來並沒有什麼特別的 - 它基本上是一個迫切需要的功能語言版本。 – Xion 2011-12-27 18:30:22

這是你想要的嗎？

clusterBy :: (a -> a -> Bool) -> [a] -> [[a]] 
clusterBy isDifferentCluster = foldr f [] 
    where f x (ys @ (y : _) : yss) | not (isDifferentCluster x y) = (x : ys) : yss 
     f x     yss         = [x]  : yss

函數參數的意義或許應該被逆轉（即返回true時，它的參數應該是相同的集羣，否則爲false中），但我已經在你的報的形式給它。

來源

2011-12-27 18:32:27 dave4420

完美。我試圖用摺疊，但沒有想過這種複雜的模式匹配。謝謝！ – Xion 2011-12-27 18:55:11

使用邊界函數對列表進行聚類

回答

相關問題