Понимание списка и функции высокого порядка в F#

Question

Я родом из SML и чувствую себя довольно комфортно с функциями высокого порядка. Но я не совсем понимаю идею составления списков. Есть ли ситуация, когда понимание списка более подходит, чем функции высокого порядка на List и наоборот?

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

Для примера рассмотрим Эффективное проектирование списка списков в F#, где ответ @cfern содержит две версии, использующие функции понимания списка и функции высокого порядка соответственно:

let rec cartesian = function
  | [] -> [[]]
  | L::Ls -> [for C in cartesian Ls do yield! [for x in L do yield x::C]]

а также:

let rec cartesian2 = function
  | [] -> [[]]
  | L::Ls -> cartesian2 Ls |> List.collect (fun C -> L |> List.map (fun x->x::C))

Answer 1

Выбор между пониманиями и функциями более высокого порядка - это в основном вопрос стиля. Я думаю, что понимание иногда более читабельно, но это всего лишь личное предпочтение. Обратите внимание, что cartesian Функция может быть написана более элегантно, как это:

let rec cartesian = function  
  | [] -> [[]]  
  | L::Ls -> 
     [ for C in cartesian Ls do for x in L do yield x::C ]

Интересный случай - при написании рекурсивных функций. Если вы используете последовательности (и последовательности понимания), они удаляют ненужное распределение временных списков, и если вы используете yield! в позиции хвостового вызова вы также можете избежать исключений переполнения стека:

let rec nums n = 
  if n = 100000 then []
  else n::(nums (n+1))
// throws StackruException
nums 0 

let rec nums n = seq {
  if n < 100000 then
    yield n
    yield! nums (n+1) }
// works just fine
nums 0 |> List.ofSeq 

Это довольно интересный шаблон, потому что он не может быть написан одинаково с использованием списков. При использовании списков вы не можете вернуть какой-либо элемент, а затем сделать рекурсивный вызов, потому что он соответствует n::(nums ...), который не является хвостово-рекурсивным.

Answer 2

Глядя на сгенерированный код в ILSpy, вы можете увидеть, что списочные выражения компилируются в конечные автоматы (например, методы, использующие yield return в C#), затем перешел на что-то вроде List.ofSeq, Функции высшего порядка, с другой стороны, кодируются вручную и часто используют изменяемое состояние или другие императивные конструкции, чтобы быть максимально эффективными. Как это часто бывает, универсальный механизм более дорогой.

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

Answer 3

Добавление к ответу Томаса Петричека. Вы можете сделать список версий хвостовым рекурсивным.

let nums3 n =
    let rec nums3internal acc n = 
        if n = 100000 then
            acc
        else
            nums3internal (n::acc) (n+1) //Tail Call Optimization possible

    nums3internal [] n |> List.rev

nums3 0

С дополнительным преимуществом значительное ускорение. По крайней мере, когда я измерял с помощью инструмента секундомер, я получаю. (nums2 - алгоритм, использующий Seq).

Nums2 takes 81.225500ms
Nums3 takes 4.948700ms

Для больших чисел это преимущество уменьшается, поскольку List.rev неэффективен. Например, за 10000000 я получаю:

Nums2 takes 11054.023900ms
Nums3 takes 8256.693100ms