# WikiLuc

### Site Tools

dit:cours:prog1:cours03

# Listes catégoriques

```(**************** Interface: ilist.mli *****************)

type ilist
val empty : unit -> ilist
val cons : int -> ilist -> ilist
val car : ilist -> int
val cdr : ilist -> ilist
val is_empty : ilist -> bool```

```(**************** Implementation: ilist.ml *****************)

type ilist = Empty | Cell of cell (* Categorical sum *)
and cell = {item: int; next: ilist} (* Categorical product *)

let empty () = Empty

let cons x l = Cell {item = x; next = l}

let car l =
match l with
| Cell c -> c.item
| Empty -> failwith "car"

let cdr l =
match l with
| Cell c -> c.next
| Empty -> failwith "cdr"

let is_empty l =
match l with
| Cell c -> false
| Empty -> true```

```(**************** Using Type ilist as an opaque data type *****************)

(*
ocamlc -c -o ilist.cmi ilist.mli
ocamlc -c -o ilist.cmo ilist.ml
ocamlc -a -o ilist.cma ilist.cmo
*)

open Ilist;;

let rec print l =
if is_empty l then print_newline ()
else begin print_int (car l); print_string " "; print (cdr l) end
;;

let l = cons 1 (cons 2 (cons 3 (empty())));;

print l;;

let rec append l m =
if is_empty l then m
else cons (car l) (append (cdr l) m)
;;

let rec reverse l =
if is_empty l then l
else append (reverse (cdr l)) (cons (car l) (empty ()))
;;

print (reverse l);;

let rec map f l =
if is_empty l then empty()
else cons (f (car l)) (map f (cdr l))
;;

print (map (fun x -> 2*x) l);;

let rec reduce f a l =
if is_empty l then a
else f (car l) (reduce f a (cdr l))
;;

reduce (fun x -> fun y -> x+y) 0 l;;

let rec iter (f: 'a -> unit) l =
if is_empty l then ()
else begin f (car l); iter f (cdr l) end
;;

iter (fun x -> print_int x; print_string " ") l;;

print_newline ();;```