Inverting chained maps?

Question

A very common pattern in functional programming is to chain a series of calls to map on lists. A contrived, simple example:

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

Where the result is:

[4; 6; 8]

Now it's easy enough to flip this on its head and avoid the creation of lists at each stage, if the types never change: simply have map take a list of functions to apply in order:

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

Which we can use like this:

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

But if we want to do the same thing to a sequence like the following:

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

Now the types do change, but because of the heterogenous nature of the types, the functions cannot be stored in anything like a list that expects (and requires) homogenous types. Obviously this is very straightforward in a less strictly typed programming language like 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]

I know a fair amount about Ocaml, but I am open to not knowing it all. Is there a way to accomplish this within Ocaml's type system that is not more trouble than it's worth?

Feck

And now if I put that expression in toplevel, it produces... [1; 2; 3] |> List.map (fun x -> x + 1) |> List.map (fun x -> x * 2) |> List.map (fun x -> float_of_int x /. 3.);; - : float list = [1.33333333333333326; 2.; 2.66666666666666652] – Carlisle

Which is expected. I'm seeking a means of applying a (variable arity) series of functions which may not all have the same type to a list of values, thus avoiding the creation of a new list at each stage in the process. Of course, this trivial example I could also simply write: [1; 2; 3] |> List.map (fun x -> float_of_int ((x + 1) * 2) /. 3.), but that wouldn't be challenging, and thus no fun. – Feck

You could probably use difflists. – Ikey

Thanks @glennsl. A good read for when I'm awake enough to type ; instead of ,. – Feck

Answer 1

By composing functions

Instead of actually storing the sequence of functions to apply successively, why not compose them right ahead?

(* (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

Storing a heterogeneous list of (chained) functions with a GADT

Now I don’t think there is any reason to do it, but if you actually want what you said in your question, you can achieve it with a GADT. I think this is what @glennsl was suggesting in a comment when mentioning “difflists”.

In the code below, we define a new inductive type (a, c) fun_chain for function chains whose composed type is a -> c; in other words, for heterogeneous lists of functions [f0; f1; …; fn] whose types are as follows:

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

As the b1, …, bn do not appear in the final type, they are existentially quantified, and so is 'b in the type of the (::) constructor.

(* (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

A note on polymorphic type annotations

In the code above, you might be intrigued by the type annotations on the definition of reduce and map (for map it is not actually needed, but I like to make sure we have the intended type).

Briefly, : 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, and that leaves type inference at a loss. In order to have a program typecheck in such a situation, we need to force polymorphism like this.

For a more lengthy explanation, see this question.

Baseball

The syntax trick (overloading the list notation) is independent from the problem at hand. To make things conceptually simpler, you can rename the fancy [] and :: constructors into something more regular such as Nil and Cons, and then the heterogeneous list of functions [f1; f2; f3] would rather be written as Cons (f1, Cons (f2, Cons (f3, Nil))). – Alley

@Maëlan, very nice explanation.. the only thing which I couldn't get my head around is... : type a c. (a, c) fun_chain -> a ->c.... Is it something like type-brother of lambda the function ? Still lot to discover, but do you have any thing which I can follow and understand? Quick links, books, articles, anything... – Carlisle

You’re right asking about that, I left it unexplained. I just added some explanations but that ended up pretty lengthy and off-topic, so I think I should move it to a separate question, Q&A style. – Alley