Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Ryan Tarpine
    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