WikiLuc

Guest connection: login: Guest, password: anonymous

User Tools

Site Tools


dit:cours:prog1:cours04

(**************** Interface Module Milist *****************)
 
type milist (* Opaque type *)
val empty : unit -> milist
val cons : int -> milist -> milist
val car : milist -> int
val cdr : milist -> milist
val is_empty : milist -> bool
val rplaca : milist -> int -> unit
val rplacd : milist -> milist -> unit

(**************** Implementation Module Milist *****************)
 
type milist = Empty | Cell of cell
and cell = {item: int ref; next: milist ref}
 
let empty () = Empty
 
let cons x l = Cell {item = (ref x); next = (ref 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
 
let rplaca l x =
  match l with
  | Cell c -> (c.item := x)
  | _ -> failwith "rplaca"
 
let rplacd l m =
  match l with
  | Cell c -> (c.next := m)
  | _ -> failwith "rplacd"

(**************** Using Type milist as an opaque data type *****************)
#load "milist.cma";;
open Milist;;
 
let rec print l =
  if is_empty l then ()
  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;;
 
let l = cons 1 (cons 2 (cons 3 (empty())));;
let m = cons 4 (cons 5 (cons 6 (empty())));;
 
rplaca (cdr l) 7;;
print l;;
 
rplacd (cdr l) (cdr m);;
print l;;
print m;;
 
let l = cons 1 (cons 2 (cons 3 (empty())));;
rplacd (cdr l) l;;
 
let rec print l n =
  if is_empty l then ()
  else if n <= 0 then print_string "..."
  else begin print_int (car l); print_string " "; print (cdr l) (n - 1) end
;;
 
print l 100;;

dit/cours/prog1/cours04.txt · Last modified: 2018/10/01 22:07 by luc.bouge