練習問題 14.3 (2) 拡張リストの map関数

max や map関数の拡張リストに対しての定義を、上の length、alength と同じように、差分（`App の場合のみ）を記述するように定義しなさい。

解答

(* サンプルリスト *)
let l1 = `Cons (1, `Cons (2, `Nil));;
let l2 = `Cons (3, `Cons (4, `Nil));;
let l6 = `Cons (5, `App (l1, l2));;
let l7 = `Cons (10, `Cons (17, `App (l1, l2)));;


(****************************************
 *             map
 ****************************************)

let rec map f = function
    `Nil -> `Nil
    | `Cons (a, l) ->
            `Cons((f a), map f l);;
(* val map :
  ('a -> 'b) ->
  ([< `Cons of 'a * 'c | `Nil ] as 'c) -> ([> `Cons of 'b * 'd | `Nil ] as 'd) =
  <fun>  *)

map (fun x -> x * 2) l1;;
(*  - : [> `Cons of int * 'a | `Nil ] as 'a = `Cons (2, `Cons (4, `Nil))  *)

(* ---------------- ふつうの `Cons リスト ------------- *)
let make_map func f = function
    `Nil -> `Nil
    | `Cons (a, l) ->
            `Cons((f a), func f l);;

let rec map_list f l = make_map map_list f l;;

map_list (fun x -> x * 2) l1;;  (* `Cons (2, `Cons (4, `Nil))  *)

#use "ex14-1.ml";;  (*  append関数を使うため *)

(* ----------------- 拡張リスト --------------------- *)

let amake_map func f = function
    (`Nil | `Cons(_, _)) as l -> make_map func f l
    | `App(l1, l2) ->
            append (func f l1) (func f l2);;

let rec amap_list f l = amake_map amap_list f l;;

amap_list (fun x -> x * 2) l7;;
(* - : [ `Cons of int * 'a | `Nil ] as 'a =
`Cons (20, `Cons (34, `Cons (2, `Cons (4, `Cons (6, `Cons (8, `Nil))))))  *)

Tweet