Re: [Caml-list] to merge list of lists

[skaller <skaller@users.sourceforge.net>]

On Mon, 2007-03-05 at 08:53 +0000, Jon Harrop wrote:
> On Monday 05 March 2007 08:37, skaller wrote:
> > On Mon, 2007-03-05 at 17:10 +1100, Pietro Abate wrote:
> > > mergel [] [[1;2;3];[4;5;6];[7;8;9]];;
> > > - : int list list = [[1; 4; 7]; [2; 5; 8]; [3; 6; 9]]
> >
> > In this case there is a library function:
> >
> >       List.concat
> >
> > that already does exactly what you want :)
> 
> List.concat doesn't do that:
> 
> # List.concat [[1;2;3];[4;5;6];[7;8;9]];;
> - : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
> 
> Note that the OP is not asking for a concat or even a merge, but a transpose.

Yes, sorry! I didn't look closely enough.
I have a related function in Felix, which transposes
a tuple of tuples, which is done with a term like

	_tuple_trans ((1,2,3),(4,5,6),(7,8,9))

here's the code, which is quite imperative, and which has
extra mess from the error diagnostics. In this case there
is a special representation for the type of a tuple
with all the elements the same type, instead of

	int * int * int

the type can be given as

	int * 3

where 3 = 1 + 1 + 1, 1 is the usual unit type, and + is
an anonymous variant combinator. A type like 3 is
called a unitsum (it is a sum of units). This in turn
allows arrays to be considered as tuples of the same
element type, and the special representation is required
to allow arrays of large extent (there's no way a representation
of a 20,000 integer tuple is going to fly in a production
compiler). Also note the result of this calculation is
a bound term, the function 'be' binds expressions,
and this code is part of that function.

So the code is somewhat more complex, but it does the
same thing. It's very hard to tell if the code is correct:
I'd be interested in a more functional way to do this
that was actually simpler (but had the same semantics).
The 'guts' of the calculation is done by the 'tr'
function introduced on line 2.


  | `AST_apply (sr,(`AST_name (_,"_tuple_trans",[]),e)) ->
    let tr nrows ncolumns =
      let e' = ref [] in
      for i = nrows - 1 downto 0 do
        let x = ref [] in
        for j = ncolumns - 1 downto 0 do
          let v = `AST_get_n (sr,(i,`AST_get_n (sr,(j,e)))) in
          x := v :: !x;
        done;
        e' := `AST_tuple (sr,!x) :: (!e');
      done
      ;
      be (`AST_tuple (sr,!e'))
    in
    let calnrows t = 
      let nrows =
        match t with 
        | `BTYP_tuple ls -> length ls
        | `BTYP_array (_,`BTYP_unitsum n) -> n
        | _ -> clierrn [sr] "Tuple transpose requires entry to be tuple"
      in 
      if nrows < 2 then
        clierr sr "Tuple transpose requires tuple argument with 2 or
more elements"
      ;
      nrows
    in
    let colchk nrows t =
      match t with 
      | `BTYP_tuple ls -> 
        if length ls != nrows then
          clierr sr ("Tuple transpose requires entry to be tuple of
length " ^ si nrows)

      | `BTYP_array (_,`BTYP_unitsum n) ->
        if n != nrows then
          clierr sr ("Tuple transpose requires entry to be tuple of
length " ^ si nrows)
        
      | _ -> clierr sr "Tuple transpose requires entry to be tuple"
    in
    let _,t = be e in
    let ncolumns, nrows = 
      match t with
      | `BTYP_tuple ls ->
        let ncolumns  = length ls in
        let nrows = calnrows (hd ls) in
        iter (colchk nrows) ls;
        ncolumns, nrows

      | `BTYP_array (t,`BTYP_unitsum ncolumns) ->
        let nrows = calnrows t in
        ncolumns, nrows

      | _ -> clierr sr "Tuple transpose requires tuple argument"
    in
      if nrows > 20 then
        clierr sr ("tuple fold: row bound " ^ si nrows ^ ">20, to
large")
      ;
      if ncolumns> 20 then
        clierr sr ("tuple fold: column bound " ^ si ncolumns^ ">20, to
large")
      ;
      tr nrows ncolumns


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net