Функция разделения связанного списка и обратные результаты

Question

Я написал эту функцию F # для разбиения списка до определенной точки и не дальше - во многом как нечто среднее между takeWhile и partition.

let partitionWhile c l =
    let rec aux accl accr =
        match accr with
        | [] -> (accl, [])
        | h::t ->
            if c h then
                aux (h::accl) t
            else
                (accl, accr)
    aux [] l

Единственная проблема заключается в том, что "взятые" предметы меняются местами:

> partitionWhile ((>=) 5) [1..10];;
val it : int list * int list = ([5; 4; 3; 2; 1], [6; 7; 8; 9; 10])

Кроме обращения к rev, можно ли написать эту функцию, чтобы первый список был в правильном порядке?

Answer 1

Вот версия для продолжения. Он хвостовой рекурсивен и возвращает список в исходном порядке.

let partitionWhileCps c l =
  let rec aux f = function
    | h::t when c h -> aux (fun (acc, l) -> f ((h::acc), l)) t
    | l -> f ([], l)
  aux id l

Вот некоторые контрольные показатели, которые можно продолжить с обсуждением после ответа Брайана (и версии для сравнения):

let partitionWhileAcc c l =
  let rec aux acc = function
    | h::t when c h -> aux (h::acc) t
    | l -> (List.rev acc, l)
  aux [] l

let test = 
  let l = List.init 10000000 id
  (fun f ->
    let r = f ((>) 9999999) l
    printfn "%A" r)

test partitionWhileCps // Real: 00:00:06.912, CPU: 00:00:07.347, GC gen0: 78, gen1: 65, gen2: 1
test partitionWhileAcc // Real: 00:00:03.755, CPU: 00:00:03.790, GC gen0: 52, gen1: 50, gen2: 1

Cps в среднем ~ 7 с, Acc ~ 4 с. Короче говоря, продолжения ничего не дают для этого упражнения.

Answer 2

Полагаю, вы можете использовать продолжения, но в конце лучше позвонить List.rev.

Answer 3

Я обычно предпочитаю последовательности вместо списка, потому что они ленивы, и у вас есть функции List.toSeq и Seq.toList для преобразования между ними.Ниже приведена реализация вашей функции partitionWhile с использованием последовательностей.

let partitionWhile (c:'a -> bool) (l:'a list) = 
    let fromEnum (e:'a IEnumerator) = 
        seq { while e.MoveNext() do yield e.Current}
    use e = (l |> List.toSeq).GetEnumerator()
    (e |> fromEnum |> Seq.takeWhile c |> Seq.toList)
    ,(e |> fromEnum |> Seq.toList)

Answer 4

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

    let partitionWhileCps cond l1 =

        let rec aux f l2 = 
            match l2 with
            | h::t when cond h ->   aux  (fun (acc, l3) -> f (h::acc, l3))  t
            | l4 -> f ([], l4)

        aux id l1

(Обратите внимание, что "[]" в совпадении l4 является начальным значением acc.) Мне нравится это решение, потому что он чувствует себя менее хитроумно, не используя List.rev, сверляя до конца первого списка и создавая второй список задом наперед. Я думаю, что другой основной способ избежать .rev будет использовать хвостовую рекурсию с операцией cons. Некоторые языки оптимизируют «противодействие хвостовой рекурсии» так же, как и правильную хвостовую рекурсию (но Дон Сайм сказал, что это не произойдет в F #).

Так что это не является хвостовой рекурсивной безопасностью в F #, но это делает мой ответ ответом и избегает List.rev (это уродливо иметь доступ к двум элементам кортежа и было бы более подходящим параллельно подходу cps, иначе Я думаю, как если бы мы только вернули первый список):

    let partitionWhileTrmc cond l1 = 

        let rec aux acc l2 =  
            match l2 with 
            | h::t when cond h ->  ( h::fst(aux acc t), snd(aux acc t)) 
            | l3 -> (acc, l3)

        aux [] l1

Answer 5

Вы можете переписать функцию следующим образом:

let partitionWhile c l =
  let rec aux xs =
    match xs with
      | [] -> ([], [])
      | h :: t ->
          if c h then
            let (good, bad) = aux t in
              (h :: good, bad)
          else
            ([], h :: t)
  aux l

Да, как заметил Брайан, он больше не является хвостовым рекурсивом, но отвечает на поставленный вопрос. Кстати, span в Haskell реализован точно так же, как в Hugs:

span p []       = ([],[])
span p xs@(x:xs')
    | p x       = (x:ys, zs)
    | otherwise = ([],xs)
    where (ys,zs) = span p xs'

Хорошей причиной для предпочтения этой версии в Haskell является лень: в первой версии все хорошие элементы посещаются до того, как список перевернут. Во второй версии первый хороший элемент может быть возвращен немедленно.