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

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

8 голосов
/ 07 июня 2011

Я родом из 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))

Ответы [ 3 ]

11 голосов
/ 07 июня 2011

Выбор между пониманиями и функциями более высокого порядка в основном зависит от стиля.Я думаю, что понимание иногда более читабельно, но это всего лишь личное предпочтение.Обратите внимание, что функция 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 StackOverflowException
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 ...), что не является хвостовой рекурсией.

4 голосов
/ 07 июня 2011

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

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

0 голосов
/ 10 февраля 2017

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

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
...