RE: [Caml-list] Preferred Way to Split a List

["David Allsopp" <dra-news@metastack.com>]

Christophe Raffalli wrote:
> let split l n =
>   let rec aux acc l n =
>      if n = 0 then List.rev acc, l
>      else match l with
>         [] -> List.rev acc, []
>      | hd::l -> aux (hd::acc) l (n-1)
>   in aux [] l n

I'd go one stage further and use Obj.magic to eliminate the List.rev calls
(cf. ExtList.List in ExtLib). I'm sensibly wary of using Obj.magic in
general but find it acceptable here because its use is hidden within the
function (you are constructing a new list anyway, you just use Obj.magic to
allow tail-consing instead) - and there is no risk of "entertaining" side
effects (cf. John's earlier email!). I've got tail-consing wrapped in a few
extra functions in List so that this would become:

let split l n =
  let acc = List.tlempty ()
  in
    let rec aux l n =
       if n = 0 then (List.tlresult acc, l)
       else match l with
              []    -> (List.tlresult acc, [])
            | hd::l -> List.tlcons hd acc; aux l (n-1)
    in
      aux l n


David


PS List.tlempty:        returns a new, empty tail-consing list
   List.tlcons x tlist: adds x to the end of the given tlist and returns
                        the same tlist pointer
   List.tlresult tlist: casts an 'a tlist to an 'a list - and marks the
                        tlist as "exported", preventing future tail-consing
                        (which would violate the semantics of O'Caml 'a
                        lists)