反转链式地图？

Question

函数式编程中一个非常常见的模式是在列表上链接一系列对

map

的调用。一个人为的简单例子：

[1; 2; 3] |> List.map (fun x -> x + 1) |> List.map (fun x -> x * 2)

结果是：

[4; 6; 8]

现在很容易翻转它并避免在每个阶段创建列表，如果类型永远不会改变：只需让

map

按顺序应用一个函数列表：

let list_map_chained : 'a. ('a -> 'a) list -> 'a list -> 'a list =
  let rec apply x chain =
    begin match chain with
    | []          -> x
    | f :: chain' -> apply (x |> f) chain'
    end
  in
  fun chain xs ->
    List.map (fun x -> apply x chain) xs

我们可以这样使用：

[1; 2; 3] |> list_map_chained [ (fun x -> x + 1) ; (fun x -> 2 * x) ]

但是如果我们想对如下序列做同样的事情：

[1; 2; 3] |> List.map (fun x -> x + 1) 
          |> List.map (fun x -> x * 2)
          |> List.map (fun x -> float_of_int x /. 3.)

现在类型确实发生了变化，但由于类型的异构性质，函数不能存储在类似于期望（并需要）同质类型的列表之类的内容中。显然，这对于像 Ruby 这样类型不太严格的编程语言来说是非常简单的：

class Array
  def inverted_map(*lambdas)
    self.map { |x| lambdas.inject(x) { |sum, l| l.call(sum) } }
  end
end

irb(main):032:0> [1,2,3].inverted_map(lambda { |x| x + 1 }, lambda { |x| x * 2 }, lambda { |x| x.to_f / 3})
=> [1.3333333333333333, 2.0, 2.6666666666666665]

我对 Ocaml 有相当多的了解，但我也愿意接受不了解全部的情况。有没有一种方法可以在 Ocaml 的类型系统中完成此任务，并且不会带来更多麻烦？

Answer 1

通过组合函数

与其实际存储要连续应用的函数序列，为什么不直接组合它们呢？

(* (0) ORIGINAL CODE: *)

let () =
  [1; 2; 3]
  |> List.map (fun x -> x + 1)
  |> List.map (fun x -> float x /. 3.)
  |> List.map string_of_float
  |> List.iter print_endline

(* (1) BY COMPOSING FUNCTIONS: *)

let (%>) f g x = x |> f |> g

let () =
  [1; 2; 3]
  |> List.map (
      (fun x -> x + 1) %>
      (fun x -> float x /. 3.) %>
      string_of_float
    )
  |> List.iter print_endline

使用 GADT 存储异构（链式）函数列表

现在我认为没有任何理由这样做，但如果您“实际上”想要您在问题中所说的内容，您可以通过 GADT 来实现。我认为这就是 @glennsl 在提到“difflists”时在评论中建议的内容。 在下面的代码中，我们为组合类型为

(a, c) fun_chain

的函数链定义了一个新的归纳类型

a -> c

；换句话说，对于异构函数列表

[f0; f1; …; fn]

，其类型如下：

f0 :     a -> b1
f1 :          b1 -> b2
…                      …
f{n-1} :                 b{n-1} -> bn
fn :                               bn -> c

由于

b1, …, bn

没有出现在最终类型中，因此它们是存在量化的，

'b

在

(::)

构造函数的类型中也是存在量化的。

(* (2) WITH A GADT: *)

(* Syntax tip: we overload the list notation [x1 ; … ; xn],
 * but wrap our notation in a module to help disambiguation. *)
module Chain = struct

  type (_, _) fun_chain =
    |  []  : ('a, 'a) fun_chain
    | (::) : ('a -> 'b) * ('b, 'c) fun_chain -> ('a, 'c) fun_chain

  (* [reduce] reduces a chain to just one function by composing all
   * functions of the chain. *)
  let rec reduce : type a c. (a, c) fun_chain -> a -> c =
    fun chain ->
      begin match chain with
      | []          -> fun x -> x
      | f :: chain' -> f %> reduce chain'
      end

  (* [map] is most easily implemented by first reducing the chain... *)
  let map : type a c. (a, c) fun_chain -> a list -> c list =
    fun chain ->
      List.map (reduce chain),
  (* ... but then it’s just a more convoluted way of pre-composing functions,
   * as in suggestion (1). If you don’t want to do that,
   * you would reimplement [map] with nested loops
   * (the outer loop goes through the list of pre-images,
   * the inner loop applies each function in turn).
   * But it is equivalent both from a high-level algorithmic perspective,
   * and at the low-level memory representation,
   * so I only expect a negligible performance difference. *)

end

let () =
  [1; 2; 3]
  |> Chain.map [
      (fun x -> x + 1) ;
      (fun x -> 2 * x) ;
      (fun x -> float x /. 3.) ;
      string_of_float
    ]
  |> List.iter print_endline

关于多态类型注释的注释

在上面的代码中，您可能会对

reduce

和

map

定义上的类型注释感兴趣（对于

map

实际上并不需要，但我想确保我们拥有预期的类型）。简单地说，

: type a. …是具有显式（强制）多态性的类型注释

。您可以将其视为通用量词：∀ 

a，...或作为类型级参数的绑定器。在上面的代码中，我们利用了类型系统的高级功能，即“多态递归”和“不同类型的分支”，这使得类型推断不知所措。为了在这种情况下进行程序类型检查，我们需要像这样强制多态性。 有关更详细的解释，请参阅此问题。