Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Clustering a list using boundary function

Given a list, I'd like to divide it into clusters using a "boundary function". Such function would take two consecutive elements of the list and decide whether or not they should belong to the same cluster.

So essentially, I want something like this:

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]]

Looking up it this type declaration in Hoogle yielded only groupBy which isn't exactly what I need (it doesn't take order of elements into account).

Is there any library function that does something similar? Or alternatively: how it could be implemented cleanly, i.e. without resorting to tail-recursive loop?

EDIT: For reference, the implementation I managed to cook up is the following:

clusterBy :: (a -> a -> Bool) -> [a] -> [[a]]
clusterBy isBoundary list = 
loop list [] []
    where
        loop (first:rest) [] result = loop rest [first] result
        loop list@(next:rest) cluster result =
            if isBoundary (head cluster) next then
                loop list [] ((reverse cluster):result)
            else
                loop rest (next:cluster) result
        loop [] cluster@(_:_) result = cluster:result
        loop _ _ result = result
like image 573
Xion Avatar asked Sep 19 '26 00:09

Xion


1 Answers

Is this what you want?

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

The sense of the function argument should probably be reversed (i.e. return true when its arguments should be in the same cluster and false otherwise), but I've given it in the form you asked for.

like image 200
dave4420 Avatar answered Sep 20 '26 20:09

dave4420