Связанная функция списка списков и обратные результаты

Ответ 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 усредненный ~ 7s, Acc ~ 4s. Короче говоря, продолжения вы ничего не покупаете для этого упражнения.

Ответ 2

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

Ответ 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)

Ответ 4

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

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 [email protected](x:xs')
    | p x       = (x:ys, zs)
    | otherwise = ([],xs)
    where (ys,zs) = span p xs'

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

Ответ 5

Я не думаю, что я единственный, кто многому научился (борясь с) решением 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