列表理解與F中的高階函數＃

我來自SML背景，對高階函數感覺很舒服。但我並沒有真正理解列表理解。 在List上有什麼情況下列表理解比高階函數更適合，反之亦然？列表理解與F中的高階函數＃

我聽說列表理解比高階函數慢，我應該在編寫性能關鍵函數時避免使用它嗎？

對於這個例子的緣故，看看Projecting a list of lists efficiently in 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))

來源

2011-06-07 pad

選擇理解與高級功能之間的關係大多是風格問題。我認爲理解有時更具可讀性，但這只是個人偏好。需要注意的是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 ...)，這不是尾遞歸。

來源

2011-06-07 11:14:57

查看ILSpy中生成的代碼，可以看到列表推導被編譯爲狀態機（例如在C＃中使用yield return的方法），然後傳遞給像List.ofSeq之類的東西。另一方面，高階函數是手工編碼的，並且經常使用可變狀態或其他命令式結構以儘可能高效。通常情況下，通用機制更昂貴。

因此，要回答您的問題，如果性能很關鍵，通常會有一個特定於您的問題的高階函數，這應該是首選。

來源

2011-06-07 14:37:23 Daniel

添加到Tomas Petricek的回答。您可以使列表版本尾部遞歸。

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

來源

2017-02-10 08:57:24 CodeMonkey

列表理解與F中的高階函數＃

回答

相關問題