## 433Re: "ocaml_beginners"::[] I/O -> imperative? functional? with loops or recursion

Expand Messages
• Sep 3, 2002
>From: Stalkern 2 <stalkern2@...>
>...
> >
> > It has a few examples they work out step by step.
>
>Yes... in Scheme! :-(
>I'll try to manage it... thank you Ryan
>
>Ernesto
>

Sorry about that! I wasn't thinking correctly :) As an exercise for myself,
I translated all the examples to OCaml. These should run without any
changes, since I tested them myself. The main difference is that I used
pattern matching, which Lisp doesn't have. I could have used List.hd and
List.tl, but I thought it better not to. Here we go:

let rec sum n =
if n = 0 then 0
else n + (sum (n-1))
;;
sum 1000;;

let rec sum2 n r =
if n = 0 then r
else sum2 (n - 1) (r + n)
;;
sum2 1000 0;;

let rec make_list n =
if n = 0 then []
else n::(make_list (n - 1))
;;
make_list 1000;;

let rec make_list2 n r =
if n = 0 then r
else make_list2 (n - 1) (n::r)
;;
make_list2 1000 [];;

let rec snoc i = function
| [] -> [i]
| hd::tl -> hd::(snoc i tl)
;;

(*
snoc is reverse cons, which in OCaml is simply "::". An easier way to
OCaml-ize it is "let snoc i ls = ls @ [i];;" *)

let rec make_list3 n k =
if n = 0 then k []
else make_list3 (n - 1) (fun ls -> k (n::ls))
;;
make_list3 1000 (fun ls -> ls);;
(*
= make_list3 999 (fun ls -> (fun ls -> ls) 1000::ls)
= make_list3 998 (fun ls -> (fun ls -> (fun ls -> ls) 1000::ls) 999::ls)
...
= make_list 0 (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 1::ls)
= (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 1::ls) []
= (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 2::ls) [1]
= (fun ls -> ... (fun ls -> ls) 1000::ls) 999::ls) ... 3::ls) [2;1]
...
= (fun ls -> (fun ls -> ls) 1000::ls) [999..1]
= (fun ls -> ls) [1000..1]
= [1000..1]
*)

let rec dont_make_list n k =
if n = 0 then ()
else dont_make_list (n - 1) (fun ls -> k (n::ls))
;;
dont_make_list 1000 (fun ls -> ls);;

(*
Step 3:
Select a variable X and wrap the expression with (fun X -> ...)
(1 + (f x)) transforms to (f x (fun v -> 1 + v))
*)

let rec map f = function
| [] -> []
| hd::tl -> (f hd)::(map f tl)
;;

(*
CPS conversion:

let rec map2 f ls k = match ls with
| [] -> []
| hd::tl -> (f hd)::(map2 f tl)
;;

let rec map2 f ls k = match ls with
| [] -> k []
| hd::tl -> k ((f hd)::(map2 f tl))
;;

let rec map2 f ls k = match ls with
| [] -> k []
| hd::tl -> f hd (fun v -> k (v::(map2 f tl)))
;;
*)

let rec map2 f ls k = match ls with
| [] -> k []
| hd::tl -> f hd (fun v -> map2 f tl (fun v2 -> k (v::v2)))
;;

let rec filter f = function
| [] -> []
| hd::tl ->
if f hd then hd::(filter f tl)
else (filter f tl)
;;

let rec filter2 f ls k = match ls with
| [] -> k []
| hd::tl ->
(f hd (fun v ->
if v then filter2 f tl (fun v2 -> k (hd::v2))
else filter2 f tl k))
;;

It was definitely helpful for me to write those out! Now I'm going to try
my hand at the little exercise at the end... :)

Oh, I almost forgot; here's the exercise! It becomes a bit different from
the Lisp version because of OCaml's strong type checking; Lisp will let you
have a list of different-typed objects (i.e. the first item in a list is an
integer but the second item is another list) and that can be used to make
trees more easily.

type tree =
| Node of tree * tree
| Leaf of int
;;

let rec sum_tree = function
| Leaf x -> x
| Node (left,right) -> (sum_tree left) + (sum_tree right)
;;
sum_tree (Node (Node (Leaf 1,Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf
5))));;

Bye,

Ryan Tarpine, rtarpine@...
"To err is human, to compute divine. Trust your computer but not its
programmer."
- Morris Kingston

_________________________________________________________________
MSN Photos is the easiest way to share and print your photos:
http://photos.msn.com/support/worldwide.aspx
• Show all 11 messages in this topic