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

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

 let partitionWhile cl = let rec aux accl accr = match accr with | [] -> (accl, []) | h::t -> if ch 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 , существует ли способ, которым эта функция могла бы быть написана, чтобы первый список был в правильном порядке?

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

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

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

 let partitionWhileAcc cl = let rec aux acc = function | h::t when ch -> 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. Короче говоря, продолжения не покупают вам ничего для этого упражнения.

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

Обычно я предпочитаю Sequences over List, поскольку они ленивы, и у вас есть функции 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) 

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

 let partitionWhile cl = let rec aux xs = match xs with | [] -> ([], []) | h :: t -> if ch 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') | px = (x:ys, zs) | otherwise = ([],xs) where (ys,zs) = span p xs' 

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

Я не думаю, что я единственный, кто многому научился (борясь с) решением 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. Некоторые языки оптимизируют «хвостовую рекурсию мод-минус» так же, как правильная recursion хвоста (но Дон Симе сказал, что это не произойдет в 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 
  • Как сгладить список в список без принуждения?
  • Предоставляет ли List , что элементы будут возвращены в том порядке, в котором они были добавлены?
  • Проверьте, содержит ли список любой другой список
  • Как закрепить два списка по-разному?
  • Пролог удаляет только уникальные элементы
  • Android: добавление статического заголовка в начало ListActivity
  • Найти наиболее распространенный элемент в списке
  • Найти полномочия 2 в списке Prolog
  • Создание категорий в ListView?
  • Можете ли вы удалить элементы из std :: list во время итерации через него?
  • Стоит ли инициализировать размер коллекции List , если размер его разумно известен?
  • Давайте будем гением компьютера.