F# построить список / массив значений + последовательные дубликаты

Question

F# построить список / массив значений + последовательные дубликаты

Мне нужно упаковать данные вот так:

let data = [1; 2; 2; 3; 2; 2; 2; 4]

let packed = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]

Где каждый элемент говорит, сколько раз он существует до следующего. Однако он должен работать с несмежными дублированиями.

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

Также, Seq.countBy не работает, потому что он учитывает все значения

600 3

Без рубрики

3 ответов:

Comments

Ничего не найдено.

Mark Seemann · Accepted Answer · 2015-12-28 17:16:03

Если у вас уже есть императивная версия, вы можете выполнить ряд небольших шагов, чтобы перейти к рекурсивной реализации.

Рекурсия

Хотя я не знаю, как выглядит ваша императивная версия, вот рекурсивная версия:
let pack xs =
    let rec imp acc = function
    | [] -> acc
    | h::t ->
        match acc with
        | [] -> imp [(h, 1)] t
        | (i, count) :: ta ->
            if h = i
            then imp ((i, count + 1) :: ta) t
            else imp ((h, 1) :: (i, count) :: ta) t
    xs |> imp [] |> List.rev
Эта функция имеет тип 'a list -> ('a * int) list when 'a : equality. Он использует частную "функцию реализации", называемую imp для выполнения работы. Эта функция рекурсивна и пронизывает накопитель (называемый acc) на всем протяжении. Этот аккумулятор является список результатов, имеющий вид ('a * int) list.

Если список накопителей пуст, то глава исходного списка (h), а также счетчик 1, создаются как кортеж как единственный элемент обновленного накопителя, и функция imp рекурсивно вызывается с этим обновленным накопителем.

Если накопитель уже содержит хотя бы один элемент, элемент извлекается путем сопоставления с шаблоном, и элемент в этом кортеже (i) сравнивается с h. Если h = i, то аккумулятор обновляется; в противном случае новый Кортеж сохраняется на acc. В обоих случаях, однако, imp рекурсивно вызывается с новым аккумулятором.

Вы можете вызвать его с помощью списка , эквивалентного вашему оригинальному кортежу, например:
> pack [1; 2; 2; 3; 2; 2; 2; 4];;
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]
Сложить

Если у вас есть рекурсивная версия,у вас часто есть рецепт для версии, использующей сгиб. В этом случае, поскольку указанная выше функция pack должна в конце концов обратить аккумулятор (используя List.rev), A правая складка наиболее подходящий. В F# это делается с помощью встроенной функции List.foldBack:
let pack' xs =
    let imp x = function
        | (i, count) :: ta when i = x -> (i, count + 1) :: ta
        | ta -> (x, 1) :: ta
    List.foldBack imp xs []
В этом случае функция, переданная в List.foldBack, слишком сложна, чтобы передать ее как анонимную функцию, поэтому я решил определить ее как частную внутреннюю функцию. Это эквивалентно рекурсивной функции imp, используемой вышеупомянутой функцией pack, но вы не заметите, что она не должна вызывать себя рекурсивно. Вместо этого он просто должен вернуть новое значение для аккумулятора.
Результатом является то же самое:
> pack' [1; 2; 2; 3; 2; 2; 2; 4];;
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]

PiotrWolkowski · Accepted Answer · 2017-05-23 15:03:59

Мое решение предполагает, что коллекция data - это список. Если иметь его в виде кортежа (в соответствии с вашим примером) было намеренно, то для того, чтобы мое решение работало, кортеж должен быть преобразован в список (пример, как это сделать, можно найти здесь).
let groupFunc list = 
    let rec groupFuncRec acc lst init count =
        match lst with
        | [] -> List.rev acc
        | head::[] when head = init
            -> groupFuncRec ((init, count)::acc) [] 0 0
        | head::[] when head <> init
            -> groupFuncRec ((head, 1)::acc) [] 0 0
        | head::tail when head = init 
            -> groupFuncRec acc tail head (count+1)
        | head::tail when head <> init
            -> groupFuncRec ((init, count)::acc) tail head 1
    let t = List.tail list
    let h = List.head list
    groupFuncRec [] t h 1
Когда я запускаю функцию на ваших образцах данных, я получаю ожидаемый результат:
 list = [(1, 1); (2, 2); (3, 1); (4, 1)]

kaefer · Accepted Answer · 2015-12-28 10:55:56

Вы можете заставить Seq.countBy работать, включив некоторую позиционную информацию в его аргумент. Конечно, вам нужно затем сопоставить свои исходные данные.
[1; 2; 2; 3; 2; 2; 2; 4]
|> Seq.scan (fun (s, i) x ->
    match s with
    | Some p when p = x -> Some x, i
    | _ -> Some x, i + 1 ) (None, 0)
|> Seq.countBy id
|> Seq.choose (function 
| (Some t, _), n -> Some(t, n)
| _ -> None )
|> Seq.toList
// val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]