Как написать эффективные функции list/seq в F #? (mapFoldWhile)

Question

Я пытался написать общую функцию mapFoldWhile, которая является только mapFold, но требует, чтобы state был option и останавливается, как только он сталкивается с состоянием None.

Я не хочу использовать mapFold, потому что он преобразует весь список, но я хочу, чтобы он остановился, как только будет найдено недопустимое состояние (т. Е. None).

Это была попытка myfirst:

let mapFoldWhile (f : 'State option -> 'T -> 'Result * 'State option) (state : 'State option) (list : 'T list) = 
    let rec mapRec f state list results = 
    match list with 
    | [] -> (List.rev results, state) 
    | item :: tail -> 
     let (result, newState) = f state item 
     match newState with 
     | Some x -> mapRec f newState tail (result :: results) 
     | None -> ([], None) 
    mapRec f state list [] 

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

Так что я посмотрел, что F # 'ы очень собственные map делает, что было:

let map f list = Microsoft.FSharp.Primitives.Basics.List.map f list 

Зловещий Microsoft.FSharp.Primitives.Basics.List.map можно найти here и выглядит следующим образом:

let map f x = 
    match x with 
    | [] -> [] 
    | [h] -> [f h] 
    | (h::t) -> 
     let cons = freshConsNoTail (f h) 
     mapToFreshConsTail cons f t 
     cons 

consNoTail материал также в этот файл:

// optimized mutation-based implementation. This code is only valid in fslib, where mutation of private 
// tail cons cells is permitted in carefully written library code. 
let inline setFreshConsTail cons t = cons.(::).1 <- t 
let inline freshConsNoTail h = h :: (# "ldnull" : 'T list #) 

Итак, я полагаю, что неизменяемые списки F # на самом деле изменяемы, потому что производительность? Я немного обеспокоен этим, воспользовавшись подменю-потом-обратным списком, поскольку я думал, что это «путь» в F #.

Я не очень опытен с F # или функциональным программированием в целом, поэтому возможно (возможно) вся идея создания новой функции mapFoldWhile - это не то, что нужно делать, но тогда что мне делать?

Я часто оказываюсь в ситуациях, когда мне нужно «выйти раньше», потому что элемент коллекции «недействителен», и я знаю, что мне не нужно смотреть на остальных. В некоторых случаях я использую List.pick или Seq.takeWhile, но в других случаях мне нужно сделать больше (mapFold).

Есть ли эффективное решение этой проблемы (mapFoldWhile в частности и «выход рано» в целом) с концепциями функционального программирования, или мне нужно переключиться на императивное решение/использовать Collections.Generics.List?

Answer 1

В большинстве случаев использование List.rev является вполне достаточным решением.

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

Запуск функции следующим:

let l = [ 1 .. 1000000 ] 

#time 
mapFoldWhile (fun s v -> 0, s) (Some 1) l 

я получаю ~ 240ms на второй линии, когда я запустить функцию без изменений. Когда я просто бросаю List.rev (чтобы он возвращал данные в другом порядке), я обхожу около ~ 190 мс.Если вы действительно вызываете функцию достаточно часто, чтобы это имело значение, тогда вам придется использовать мутацию (на самом деле, ваш собственный тип изменяемого списка), но я думаю, что это редко стоит того.

Для общих проблем с «выходом на раннем этапе» вы часто можете написать код в виде композиции Seq.scan и Seq.takeWhile. Например, вы хотите, чтобы суммировать числа из последовательности, пока не дойдете до 1000. Вы можете написать:

input 
|> Seq.scan (fun sum v -> v + sum) 0 
|> Seq.takeWhile (fun sum -> sum < 1000) 

Использование Seq.scan генерирует последовательность сумм, которая на протяжении всего ввода, но так как это лениво генерируется, используя Seq.takeWhile останавливает вычисление, как только происходит условие выхода.