Re: [Caml-list] recursive module, object types, tying knot

[Gabriel Scherer <gabriel.scherer@gmail.com>]

On Tue, Sep 13, 2011 at 6:56 AM, Dmitry Grebeniuk <gdsfh1@gmail.com> wrote:
>  I've tried to write some code where the initial container is
> stored in the object itself, but couldn't make it work.  And
> this approach (map = fold_right + cons) is somewhat limited,
> it will work good for single-linked lists, but I can't imagine
> it can work with more complex data structures like trees

You may define more general folds. The idea is that from any algebraic
datatype you can derive a fold operator.

See for example:

  type 'a list = Nil | Cons of 'a * 'a list
  val list_fold : 'r -> ('a -> 'r -> 'r) -> 'r

  type 'a tree = Nil | Leaf of 'a list * 'a * 'a list
  val tree_fold : 'r -> ('r -> 'a -> 'r) -> 'r

  type ('a, 'b, 'c) strange_list =
    | End of 'c
    | ACons of 'a * ('a, 'b, 'c) strange_list
    | BCons of 'b * ('a, 'b, 'c) strange_list
  val strange_list_fold : ('c -> 'r) -> ('a -> 'r -> 'r) -> ('b -> r -> r) -> r

The idea is that for each constructor of the datatype, you add an
argument to the fold, that has the same signature as its type as a
function (Nil : 'a list) (Cons :  'a -> 'a list -> 'a list), with
recursive occurences of the type replaced by the elimination type
parameter 'r.

There is a more abstract construction : if you express recursive
datatypes as fixpoint of a type with one more parameter (~ polynomial
functor), you can define fold recursively from a `map` operation on
this type. For example, ('a list) is the fixpoint on 'b of (type ('a,
'b) cons = Nil' | Cons' of 'a * 'b), which is witnessed by the
existence of reciprocal (val wrap : ('a, 'a list) cons -> 'a list) and
(val unwrap : 'a list -> ('a, 'a list cons)), and (some form of)
list_fold can be defined as
  let rec list_fold li = f (map_cons (list_fold f) (unwrap li))

For a more abstract and hardly readable presentation of this topic,
see the article "Functional programming with Bananas, Lenses,
Envelopes and Barbed Wire" by Meijer, Fokkinga and Paterson, 1991.

> (and I can imagine the overhead of folding + consing
> over arrays).  So I prefer to avoid such style of mapping.

An `iter` function is sufficient for arrays:

class type ['a] array = object
  ...
  method length : int
  method iter : (int -> 'a -> unit) -> unit
end

You can then express the map operation:
  let map f t =
    let result = make_array t#length in
    t#iter (fun i x -> result#set i (f x));
    result

An internal map would have to allocate a new array anyway (in the
general case where (f : 'a -> 'b), you can't mutate the array
in-place), so this is as efficient memory-wise. Similarly, a map
defined by the user from a fold on a recursive datatype has the same
allocation profile as an internally-defined fold. The only potential
overhead comes from the passing of the fold function (which means one
more indirect call per node traversed), but if you're at this level of
detail you may not want to design your core data structures as object
anyway.