在F#中,列表的前置操作有些令人烦恼,因为一旦完成,您必须将其反转。是否有一种从开头直接构建列表的方法?
在F#中,列表的前置操作有些令人烦恼,因为一旦完成,您必须将其反转。是否有一种从开头直接构建列表的方法?
在对列表进行前置和反转操作时没有任何问题。你可以在单元素列表上使用 append (@
),但这是一种代码异味。一个可容忍的(尾递归)方法是:
let appendSingle xs x =
[ yield! xs
yield x ]
let filter f l =
let rec loop acc l =
match l with
| [] -> List.rev acc
| x::xs when f x -> loop (x::acc) xs
| x::xs -> loop acc xs
loop [] l
使用更高效的对应物
let filter f l =
let rec loop (acc : ResizeArray<_>) l =
match l with
| [] -> Seq.toList acc
| x::xs when f x ->
acc.Add(x)
loop acc xs
| x::xs -> loop acc xs
loop (ResizeArray()) l
appendSingle
函数基本上与 xs @ [x] 具有相同的性能特征,但以一种更复杂的方式实现。 - Gustavo Guerraxs
添加x
,可以像这样:xs @ [x]
回顾您的原始代码,我认为您要使用List.foldBack
而不是List.fold
。本质上,foldBack
从列表末尾开始重复应用folder
函数,而不是从列表开头开始。它不像fold
那样高效,但最好使用foldBack
并避免翻转列表。
使用foldBack
,将累加函数folder
应用于列表x0::x1::...::xlast
,其中folder
的初始参数为init
:
folder x0 (folder x1 ( ... (folder xlast init) ... ) )
参见 fold
folder (... (folder (folder init x0) x1) ...) xlast
您的原始问题有一些其他答案提供了替代解决方案,但如果坚持使用您的代码,将 fold
替换为 foldBack
将得到第一个实现。
let chunkOrig items chunkSize =
let folder =
fun x (result, chunk) ->
if List.length chunk < chunkSize then
(result, x::chunk)
else
(chunk::result, [x])
let (a,b) = List.foldBack folder items ([], [])
b::a
现在这个代码简单多了,因为所有的列表反转都被去掉了。看起来它似乎能够正常工作。
> chunkOrig [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]
foldBack
从最后一个元素开始。> chunkOrig [1..11] 2;;
val it : int list list = [[1]; [2; 3]; [4; 5]; [6; 7]; [8; 9]; [10; 11]]
folder
的参数化,参数应该是当前块中剩余的长度而不是整个块本身。let chunk items chunkSize =
let folder =
fun x (result, lenLeft) ->
if lenLeft > 0 then
match result with
| [] -> ([[x]], lenLeft-1)
| r0::rtail -> ((x::r0)::rtail, lenLeft-1)
else
([x]::result, chunkSize-1)
let (result, lenLeft) = List.foldBack folder items ([], (List.length items) % chunkSize)
result
> chunk [1..10] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]]
> chunk [1..11] 2;;
val it : int list list = [[1; 2]; [3; 4]; [5; 6]; [7; 8]; [9; 10]; [11]]