Кластеризация списка с использованием граничной функции

Учитывая список, я хотел бы разделить его на кластеры, используя «граничную функцию». Такая функция будет принимать два последовательных элемента списка и решать, должны ли они принадлежать одному и тому же кластеру.

По сути, я хочу что-то вроде этого:

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, что не совсем то, что мне нужно (оно не учитывает порядок элементов).

Есть ли какая-нибудь библиотечная функция, которая делает что-то подобное? Или альтернативно: как это можно реализовать чисто, т.е. не прибегая к циклу хвостовой рекурсии?

EDIT: для справки, реализация, которую мне удалось приготовить, выглядит следующим образом:

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

cluster-analysis haskell
person Xion    schedule 27.12.2011    source источник
comment
Почему цикл хвостовой рекурсии не является чистым? Какова цель избежать такого прямого решения?   -  person Thomas M. DuBuisson    schedule 27.12.2011
comment
Я отредактировал вопрос, добавив хвостовую рекурсивную версию, которую мне удалось придумать. Я недоволен количеством терминальных условий и общей многословностью. Откровенно говоря, он совсем не выглядит очень хаскельским — это, по сути, императивная версия, встроенная в функциональный язык.   -  person Xion    schedule 27.12.2011

Ответы (1)


arrow_upward
4
arrow_downward

Это то, что вы хотите?

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 в противном случае), но я дал его в форме, которую вы просили.

person dave4420    schedule 27.12.2011
comment
Идеальный. Я пытался использовать сгиб, но не думал о таком сложном сопоставлении с образцом. Спасибо! - person Xion; 27.12.2011