Re: [Caml-list] Induction over types

["Christopher L Conway" <cconway@cs.nyu.edu>]

Dawid,

Your example seems to require dependent types (e.g., "nested lists of
depth k") or runtime type inspection. Neither is directly supported by
OCaml (although there might be experimental extensions out there that
do what you want). You might be interested the "Scrap Your
Boilerplate" approach which is available in the latest versions of
Haskell (http://www.cs.vu.nl/boilerplate). I think this would
accomplish what you're asking. But it's implementation and use is
non-trivial.

Chris

On Jan 31, 2008 12:38 PM, Dawid Toton <d0@wp.pl> wrote:
> I want to write a polymorphic function that invokes itself recursively,
> but with different types.
> For example I'd like to translate the following pseudo-code into OCaml:
>
> let rec deep_rev (lst:'a list) = List.rev (List.map (deep_rev:'a->'a) lst)
> let deep_rev (element:'a) = element  (* initial induction step *)
>
> let rec super_wrap (depth:int) (lst:'a list) =
>   match depth with
>    | 0 -> lst
>    | d -> super_wrap (d+1) [lst]
>
> And how can I have arbitrary transposition:
>
> val transpose: int list -> 'a list -> 'a list
>
> # transpose [2;0;1]
>   [[[1;2];[3;4]]
>   ;[[5;6];[7;8]]
>   ]
> - : int list list list = [[[1; 3]; [5; 7]]; [[2; 4]; [6; 8]]]
>
> Do I have to have separate functions:
>
> val transpose1: int list -> 'a list -> 'a list   (* identity *)
> val transpose2: int list -> 'a list list -> 'a list list
> val transpose3: int list -> 'a list list list -> 'a list list list
> ...
>
> But this is huge amount of redundant code!
> Here is for example my transpose3:
> http://www.toton.2-0.pl/OCaml/transpose.ml
>
> Dawid Toton
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>