Ближайший сосед и распознавание образов с Haskell

Question

Вот упрощенная версия трех наборов данных, которые у меня есть:

Set A = [1, 1, 2, 2, 1, 2, 2, 1]
Set B = [2, 2, 1, 2, 2, 1, 1, 3]
Set C = [8, 4, 4, 4, 4, 9, 8, 4]

Есть ли в Haskell какие-либо встроенные функции для поиска неопределенных шаблонов между наборами данных? Я хотел бы запустить мою программу на 2 или более наборах данных и сообщить, какие из них похожи, в данном случае это наборы A и B.

Answer 1

Если вы не говорите о нахождении последующего пересечения.

Для каждых 2 списков мы можем использовать функцию intersect из Data.List, которая берет их пересечение.

Итак, идея состоит в том, чтобы рассчитать пересечение всего списка и отсортировать их.

> snd . last . sort $ [ (length $ intersect x y, (x,y)) | let list = [[1,1,2,2,1,2,2,1],[2,2,1,2,2,1,1,3],[8,4,4,4,4,9,8,4]], x <- list, y <- list, x /= y ]
([1,1,2,2,1,2,2,1],[2,2,1,2,2,1,1,3])

Если вы заинтересованы в нахождении последующего пересечения, вы можете использовать что-то вроде этого:

import Data.List (sort, subsequences)

intersectCons :: (Ord a) => [a] -> [a] -> [a]
intersectCons x y = snd . last . sort $
  [ (length x1, x1) | x1 <- subsequences x
                    , x2 <- subsequences y
                    , x1 == x2 ]

Например:

> intersectCons [1, 1, 2, 2, 1, 2, 2, 1] [2, 2, 1, 2, 2, 1, 1, 3]
[2,2,1,2,2,1]

Также мы можем использовать его для поиска наиболее похожих пар списков:

> snd . last . sort $ [ (length $ intersectCons x y, (x,y)) | let list = [[1,1,2,2,1,2,2,1],[2,2,1,2,2,1,1,3],[8,4,4,4,4,9,8,4]], x <- list, y <- list, x /= y ]
([2,2,1,2,2,1,1,3],[1,1,2,2,1,2,2,1])

На самом деле, если вы хотите получить не только одну пару списков, но и все «похожие» пары, вы можете удалить snd . last . sort $ и получить их все.