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

Я исхожу из фона 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))

Ответы

Ответ 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 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 ...), который не является хвостовым рекурсивным.

Ответ 2

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

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

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