trmc.ml

let rec map f = function
  | [] -> []
  | x :: xs -> f x :: map f xs


module Mutable_list = struct
  type 'a t =
    | Nil
    | Cons of 'a cell

  and 'a cell = {head: 'a; mutable tail: 'a t}

  let rec map f = function
    | Nil -> Nil
    | Cons {head; tail} ->
        Cons {head=f head; tail=map f tail}

  let rec map' result f = function
    | Nil ->
        result.tail <- Nil
    | Cons {head; tail} ->
        let next = {head=f head; tail=Nil} in
        result.tail <- Cons next;
        map' next f tail

   let map f list =
     let result = {head=Obj.magic 0; tail=Nil} in
     map' result f list;
     result.tail


end

module Mutable_list = struct
  type 'a t =
    | Nil
    | Cons of {head: 'a; tail: 'a t ref}

  let rec map f = function
    | Nil -> Nil
    | Cons {head; tail={contents=tail}} ->
        Cons {head=f head; tail=ref (map f tail)}

  let rec map' result f = function
    | Nil ->
        result := Nil
    | Cons {head; tail={contents=tail}} ->
        let next = ref Nil in
        result := Cons {head=f head; tail=next};
        map' next f tail

   let map f list =
     let result = ref (Obj.magic 0) in
     map' result f list;
     !result


end


module Mutable_list = struct
  type 'a t =
    | Nil
    | Cons of 'a cell

  and 'a cell = {head: 'a; mutable tail: 'a t}

  module Natural_style = struct
    let rec map f = function
      | Nil -> Nil
      | Cons {head; tail} ->
          Cons {head=f head; tail=map f tail}
  end

  module Trmc_style = struct
    let rec map_aux result f = function
      | Nil ->
          result.tail <- Nil
      | Cons {head; tail} ->
          let next = {head=f head; tail=Nil} in
          result.tail <- Cons next;
          map_aux next f tail

     let map f = function
       | Nil -> Nil
       | Cons {head; tail} ->
           let result = {head=f head; tail=Nil} in
           map' result f tail;
           Cons result
  end

  module Trmc_style' = struct

     let map f = function
       | Nil -> Nil
       | Cons {head; tail} ->
           let result = {head=f head; tail=Nil} in
           let current = ref result in
           let rec aux = function
             | Nil -> ()
             | Cons {head; tail} ->
                 let next = {head=f head; tail=Nil} in
                 (!current).tail <- Cons next;
                 current := next;
                 aux tail
           in
           aux tail;
           Cons result
  end

  module Trmc_style'' = struct
     let map f = function
       | Nil -> Nil
       | Cons {head; tail} ->
           let rec go prev = function
             | Nil -> ()
             | Cons {head; tail} ->
                 let next = {head=f head; tail=Nil} in
                 prev.tail <- Cons next;
                 go next tail
           in
           let result = {head=f head; tail=Nil} in
           go result tail;
           Cons result
  end

end