Version française
Home     About     Download     Resources     Contact us    
Browse thread
Induction over types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Dawid Toton <d0@w...>
Subject: Induction over types
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