尾递归List.map

Question

OCaml 中典型的 List.map 函数非常简单，它需要一个函数和一个列表，并将该函数递归地应用于列表的每个项目。我现在需要将List.map转换为尾递归函数，该怎么做？累加器应该累加什么？

Answer 1

可以说，最简单的方法是根据尾递归辅助函数

map

来实现

map_aux

，该函数遍历列表，同时累积已映射的前缀：

let map f l =
  let rec map_aux acc = function
    | [] -> acc
    | x :: xs -> map_aux (acc @ [f x]) xs
  in
  map_aux [] l

但是，由于列表串联运算符

@

所花费的时间与其第一个参数的长度成线性关系，因此这会产生二次时间遍历。此外，列表串联本身不是尾递归的。

因此，我们要避免使用

@

。该解决方案不使用列表串联，而是通过 prepending 新映射到累加器的参数进行累加：

let map f l =
  let rec map_aux acc = function
    | [] -> List.rev acc
    | x :: xs -> map_aux (f x :: acc) xs
  in
  map_aux [] l

为了按正确的顺序恢复映射的元素，我们只需在空列表的情况下反转累加器即可。请注意，

List.rev

是尾递归的。

这种方法最终通过积累所谓的差异列表：

避免了递归列表串联和列表反转。

let map f l =
  let rec map_aux acc = function
    | [] -> acc []
    | x :: xs -> map_aux (fun ys -> acc (f x :: ys)) xs
  in
  map_aux (fun ys -> ys) l

这个想法是让累积的前缀列表由函数

acc

表示，当应用于参数列表

ys

时，返回前缀列表

ys

。因此，作为累加器的初始值，我们有

fun ys -> ys

，代表一个空前缀，对于

[]

，我们只需将

acc

应用于

[]

即可获得映射的前缀。

Answer 2

（我相信你的话，这不是作业。）

答案是函数式编程中的经典模式之一，即 cons/reverse 习惯用法。首先，您以相反的顺序排列列表，这很容易以尾递归方式完成。最后，你颠倒了列表。反转也是尾递归操作，因此不会对堆栈安全造成问题。

缺点是额外的分配和更笨拙的代码。

let map f list =
  let rec loop acc = function
    | [] -> List.rev acc
    | x::xs -> loop (f x::acc) xs in
  loop [] list

一个很好的练习是使用这种风格（重新）实现一堆“标准”列表函数（

append

、

rev_append

、

fold_left

、

fold_right

、

filter

、

forall

等）在必要时使它们成为尾递归。

Answer 3

在 OCaml 4.14 及更高版本中，在向您招手的类别中，有 tail_mod_cons，它为这个问题提供了一个优雅的答案，允许非常自然地实现

map

，而不会出现堆栈溢出。

# let[@tail_mod_cons] rec map f = 
    function
    | [] -> []
    | x::xs -> f x :: map f xs;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
# List.init 10_000_000 Fun.id 
  |> map ((+) 1);;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22;
 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40; 41;
 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58; 59; 60;
 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77; 78; 79;
 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96; 97; 98;
 99; 100; 101; 102; 103; 104; 105; 106; 107; 108; 109; 110; 111; 112; 113; 114;
 115; 116; 117; 118; 119; 120; 121; 122; 123; 124; 125; 126; 127; 128; 129;
 130; 131; 132; 133; 134; 135; 136; 137; 138; 139; 140; 141; 142; 143; 144;
 145; 146; 147; 148; 149; 150; 151; 152; 153; 154; 155; 156; 157; 158; 159;
 160; 161; 162; 163; 164; 165; 166; 167; 168; 169; 170; 171; 172; 173; 174;
 175; 176; 177; 178; 179; 180; 181; 182; 183; 184; 185; 186; 187; 188; 189;
 190; 191; 192; 193; 194; 195; 196; 197; 198; 199; 200; 201; 202; 203; 204;
 205; 206; 207; 208; 209; 210; 211; 212; 213; 214; 215; 216; 217; 218; 219;
 220; 221; 222; 223; 224; 225; 226; 227; 228; 229; 230; 231; 232; 233; 234;
 235; 236; 237; 238; 239; 240; 241; 242; 243; 244; 245; 246; 247; 248; 249;
 250; 251; 252; 253; 254; 255; 256; 257; 258; 259; 260; 261; 262; 263; 264;
 265; 266; 267; 268; 269; 270; 271; 272; 273; 274; 275; 276; 277; 278; 279;
 280; 281; 282; 283; 284; 285; 286; 287; 288; 289; 290; 291; 292; 293; 294;
 295; 296; 297; 298; 299; ...]
# List.init 10_000_000 Fun.id 
  |> List.map ((+) 1);;
Stack overflow during evaluation (looping recursion?).