Как объединить элементы равной последовательности (функциональное программирование)?

Question

Я хочу написать функцию, которая принимает последовательность <1,1,2,2,3> и возвращает последовательность с равными элементами, сгруппированными как << 1,1>, <2,2>, <3> >.

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

Reduce принимает ассоциативную функцию и возвращает последовательность, "уменьшенную" этим оператором. Итак, уменьшаем оп + 0 <1,2,3> = 6.

Моей первой мыслью было использовать карту, чтобы поднять последовательность на один уровень. Итак, <1,1,2,2,3> => << 1>, <1>, <2>, <2>, <3 >>.

Затем я подумал об использовании Reduce, в котором я создаю функцию, которая принимает пары элементов, таких как (x, y). Если x == y, тогда я возвращаюсь, я ничего не делаю. Но ... это не совсем работает, так как функция должна возвращать что-то одинакового типа в обоих случаях.

Может кто-нибудь дать мне несколько советов о том, как выбрать правильный путь, например, какие функции более высокого порядка я мог бы использовать? Я использую SML, но я не прошу, чтобы кто-нибудь дал мне полный ответ, так что любые советы высокого уровня будут оценены (честно на любом функциональном языке)

Answer 1

В Haskell у вас есть group и groupBy.Они сделаны с помощью вспомогательной функции под названием span.Стандартный ML, к сожалению, не так богат, как стандартная библиотека, поэтому вам придется создавать эту функцию самостоятельно.Но вы можете использовать тот же подход:

1. Определить функцию span, которая разбивает список на две части, где первая часть является самым длинным префиксом, для которого некоторый предикат является истинным, а втораячасть является остатком списка.

   fun span p [] = ...
     | span p (x::xs) = ... if p x then ... else ...
   

   Например,

   - span (fn n => n <= 3) [2,3,4,1,5]
   > val it = ([2,3], [4,1,5])
   

   Это немного сложно, потому что вы должны как-то добавить x к результату вызова span p xsрекурсивно, даже если он возвращает пару списков;поэтому вы не можете просто написать x :: span p xs;Вы должны распаковать возвращенную пару и вернуть (x :: ys, zs) или (ys, x :: zs) (и прекратить повторное использование, если p x равно false).

2. Определить функцию groupBy, которая используетspan.Функция, которую использует groupBy, должна иметь два аргумента, в отличие от span, где p принимает один аргумент: первый - это элемент, с которым нужно группировать, а второй - последующие элементы.

   fun groupBy f [] = ...
     | groupBy f (x::xs) = ... use span, f, x and xs to create (ys, zs) ...
                           ... ys is the first group ...
                           ... groupBy f zs is the remaining groups ...
   

   Здесь полезно, если функция f каррирована, т.е. имеет тип

   'a -> 'a -> bool
   

   , с тех пор ее можно использовать как val (ys, zs) = span (f x) xs.

Feelсвободно задавать дополнительные вопросы, если вы хотите использовать этот подход.

Answer 2

Я полагаю, что функция reduce, на которую вы ссылаетесь, такая же, как функция fold в F #:

val fold : ('State -> 'Value -> 'State) -> 'State -> 'Value list -> 'State

Для этого требуется список значений вместе с начальным состоянием и функцией, которая преобразует это состояние, перебирая значения списка.

Вы можете делать то, что вы хотите в один раз. Есть пара вещей, которые вам нужно сохранить в штате. Представьте, что вы где-то в середине 1,1,2,2,3 (скажем, на втором 2). Теперь вам понадобится:

• Значение, которое вы в настоящее время собираете - это 2
• Список значений, содержащий текущие собранные значения, то есть [2] (первый 2 из последовательности)
• Список списков значений, которые вы собрали ранее - это [ [1; 1] ].

Вы начнете с начального состояния -1, [], [] (используя -1 в качестве некоторого значения, которое не будет отображаться при вводе). Затем вам нужно написать функцию, которая преобразует состояние на основе текущего значения. Это должно решить пару ситуаций:

• Когда значение не совпадает со значениями, которые вы собирали, вам нужно добавить список собранных значений в список списков (если он не пустой)
• Когда значение совпадает, вам нужно добавить его в список значений, собранных сейчас, и продолжить

Надеюсь, это даст вам достаточно информации, чтобы выяснить, как это сделать, фактически не раскрывая полный исходный код!

Answer 3

Если F # является вашим языком, просто используйте функцию Seq.groupBy :

input |> Seq.groupBy id |> Seq.map snd

В противном случае,

Я предполагаю, что ваш язык поддерживает Seq.distinct,Seq.fold, Seq.map и Seq.init.Версия этих функций на F # может быть найдена в этом документе .

Затем вы можете выполнить следующие шаги:

1) Создайте отдельный последовательность извведите seq с Seq.distinct:

input |> Seq.distinct

2) Напишите функцию, которая подсчитывает количество вхождений значения в seq, используя Seq.fold:

let count x theSeq =
    theSeq
    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

3) Используйте функцию count, чтобы украсить каждый элемент отдельного seq числом его вхождений во входном seq:

Seq.map (fun x -> (x, count x input))

4) Наконец, используйте Seq.init для копирования равных элементов:

Seq.map (fun (x, count) -> Seq.init count (fun i -> x))

Весь код:

let count x theSeq =
    theSeq
    |> Seq.fold (fun n e -> if x = e then n+1 else n) 0

input
|> Seq.distinct
|> Seq.map (fun x -> (x, count x input))
|> Seq.map (fun (x, count) -> Seq.init count (fun i -> x))

Answer 4

Не знаю, какие языки вы используете, но с функциональной точки зрения я бы:

1. принимает последовательность различных значений
2. сопоставить каждое значение в отдельной последовательности с отфильтрованной исходной последовательностью.

Псевдокод:

originalSequence = <1,1,2,2,3>
distinctSequence = originalSequnce.distinct() // <1,2,3>
result = distinctSequence.map(elem => originalSequence.filter(e == elem)) // <<1,1>, <2, 2>, <3>>