反转链式地图？

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的函数链定义了一个新的归纳类型(a, c) fun_chain；换句话说，对于异构函数列表[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 pre-reducing the chain first,
   * but then it is just a more convoluted way of pre-composing functions,
   * as in the first suggestion. If you want a slightly different behavior,
   * you would reimplement [map] with a nested loop (once for iterating
   * on the list, the other for applying each function in turn). Not sure
   * whether that would improve performance, though. *)
  let map : type a c. (a, c) fun_chain -> a list -> c list =
    fun chain ->
      List.map (reduce chain)

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. … is a type annotation with explicit (forced) polymorphism. You can think of this as the universal quantifier: ∀ a, … or as a binder for a type-level argument. In the code above we make use of advanced features of the type system, namely, polymorphic recursion and branches with different types，这让类型推断无所适从。为了在这种情况下进行程序类型检查，我们需要像这样强制多态性。

有关更详细的解释，请参阅。

反转链式地图？

Inverting chained maps?

ocaml

通过组合函数

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

关于多态类型注释的注释