Функция Haskell для сохранения повторяющихся элементов списка

Question

Вот ожидаемый ввод / вывод:

повторение "Миссисипи" == "ips"

повторение [1,2,3,4,2,5,6, 7,1] == [1,2]

повторяется "" == ""

А вот мой код:

repeated :: String -> String
repeated "" = "" 
repeated x = group $ sort x 

Я знаю, что последняя часть кода не работает.Я думал отсортировать список, затем сгруппировать его, затем я хотел сделать фильтр в списке списка, который больше 1, или что-то в этом роде.

Answer 1

Хорошо, хорошее начало.Одна непосредственная проблема заключается в том, что спецификация требует, чтобы функция работала со списками чисел, но вы определяете ее для строк.Список должен быть отсортирован, поэтому его элементы должны иметь класс типов Ord.Поэтому давайте исправим сигнатуру типа:

repeated :: Ord a => [a] -> [a]

После вызова sort и group у вас будет список списков [[a]].Давайте рассмотрим вашу идею использования filter.Это работает.Ваш предикат должен, как вы сказали, проверить length каждого списка в списке, а затем сравнить, что length с 1.

Фильтрация списка списков дает вам подмножество, которое является другим спискомсписки типа [[a]].Вам нужно сгладить этот список.То, что вы хотите сделать, это map каждая запись в списке списков для одного из ее элементов.Например, первый.В Prelude есть функция для этого.

Итак, вы можете заполнить следующий скелет:

module Repeated (repeated) where

import Data.List (group, sort)

repeated :: Ord a => [a] -> [a]
repeated = map _
         . filter (\x -> _)
         . group
         . sort 

Я написал это в стиле без точек с помощью фильтрацииПредикат как лямбда-выражение, но многие другие способы написать это одинаково хороши.Найдите тот, который вам нравится!(Например, вы также можете написать предикат filter в стиле без точек, как композицию из двух функций: сравнение с результатом length.)

Когда вы попытаетесь скомпилировать это,компилятор скажет вам, что есть два типизированных отверстия , _ записей справа от знаков равенства.Он также скажет вам тип отверстий.Первая дыра нуждается в функции, которая берет список и возвращает вам единственный элемент.Для второго отверстия требуется логическое выражение, использующее x.Заполните их правильно, и ваша программа будет работать.

Answer 2

Вот некоторые другие подходы, чтобы оценить комментарий @ chepner к решению, используя group $ sort.(Эти решения выглядят проще, поскольку некоторые сложности скрыты в подпрограммах библиотеки.)

Хотя верно, что сортировка - это O (n lg n), ...

Это не просто сортировка, но особенно group: она использует span, и они оба создают и уничтожают временные списки.Т.е. они делают это:

линейный обход несортированного списка потребует некоторой другой структуры данных для отслеживания всех возможных дубликатов, и поиск в каждом из них, по крайней мере, увеличит сложность пространства.В то время как тщательно выбранные структуры данных могут использоваться для поддержания общего времени работы O (n), константа, вероятно, на практике сделает алгоритм более медленным, чем решение O (n lg n), ...

group/span значительно увеличивает эту сложность, поэтому O (n lg n) не является правильной мерой.

, значительно усложняя реализацию.

Следующие всепройти список ввода только один раз.Да, они строят вспомогательные списки.(Возможно, Set даст лучшую производительность / более быстрый поиск.) Возможно, они выглядят более сложными, но для сравнения яблок с яблоками посмотрите также код для group/span.

repeated2, repeated3, repeated4 :: Ord a => [a] -> [a]

• repeated2/inserter2 создает вспомогательный список пар [(a, Bool)], в котором Bool равен True, если a появляется более одного раза, False, если пока только один раз.

  repeated2 xs = sort $ map fst $ filter snd $ foldr inserter2 [] xs
  
  inserter2 :: Ord a => a -> [(a, Bool)] -> [(a, Bool)]
  inserter2 x [] = [(x, False)]
  inserter2 x (xb@(x', _): xs)
      | x == x'   = (x', True): xs
      | otherwise = xb: inserter2 x xs
  

• repeated3/inserter3 создает вспомогательный список пар [(a, Int)], в котором Int подсчитывает, сколько из a появляется.Вспомогательный список в любом случае отсортирован, просто ради черта.

  repeated3 xs = map fst $ filter ((> 1).snd) $ foldr inserter3 [] xs
  
  inserter3 :: Ord a => a -> [(a, Int)] -> [(a, Int)]
  inserter3 x [] = [(x, 1)]
  inserter3 x xss@(xc@(x', c): xs) = case x `compare` x' of
      { LT -> ((x, 1): xss)
      ; EQ -> ((x', c+1): xs)
      ; GT -> (xc: inserter3 x xs)
      }
  

• repeated4/go4 создает выходной список элементов, о которых известно, что они повторяются.Он поддерживает промежуточный список элементов, встреченных один раз (пока), когда проходит через входной список.Если встречается повтор: он добавляет этот элемент в список вывода;удаляет его из промежуточного списка;отфильтровывает этот элемент из хвоста списка ввода.

  repeated4 xs = sort $ go4 [] [] xs
  
  go4 :: Ord a => [a] -> [a] -> [a] -> [a]
  go4 repeats _ [] = repeats
  go4 repeats onces (x: xs) = case findUpd x onces of
      { (True, oncesU) -> go4 (x: repeats) oncesU (filter (/= x) xs)
      ; (False, oncesU) -> go4 repeats oncesU xs
      }
  
  findUpd :: Ord a => a -> [a] -> (Bool, [a])
  findUpd x [] = (False, [x])
  findUpd x (x': os) | x == x' = (True, os)      -- i.e. x' removed
                     | otherwise =
                       let (b, os') = findUpd x os in (b, x': os')
  

  (Этот последний бит списка в findUpd очень похож на span.)

Answer 3

Ваш код уже выполняет половину работы

> group $ sort "Mississippi"
["M","iiii","pp","ssss"]

Вы сказали, что хотите отфильтровать недубликаты.Давайте определим предикат, который идентифицирует списки, имеющие как минимум два элемента:

atLeastTwo :: [a] -> Bool
atLeastTwo (_:_:_) = True
atLeastTwo _       = False

Использование этого:

> filter atLeastTwo . group $ sort "Mississippi"
["iiii","pp","ssss"]

Хорошо.Теперь нам нужно взять только первый элемент из таких списков.Поскольку списки не пусты, мы можем безопасно использовать head:

> map head . filter atLeastTwo . group $ sort "Mississippi"
"ips"

В качестве альтернативы, мы могли бы заменить фильтр на filter (\xs -> length xs >= 2), но это было бы менее эффективно.

Покадругой вариант - использовать понимание списка

> [ x | (x:_y:_) <- group $ sort "Mississippi" ]
"ips"

Этот шаблон соответствует спискам, начинающимся с x и имеющим хотя бы другой элемент _y, объединяющий фильтр с взятием головы.