Matt's Blog

Looping without loops

Sun Sep 17 18:09:04 EST 2006

A standard exercise when first learning to program is to draw a triangle of stars using for loops, i.e.

*
**
***
****

How do you do this in a language that doesn't allow variable assignment? By (tail) recursion with an extra accumulator argument and loop index. Below is the Ocaml code for drawing a number of different triangles. Note the use of the higher order function string_gen.

let make_line c n = String.make n c

let make_tri c n =
  let rec aux k acc =
    if k=0 then acc else aux (k-1) ((make_line c k) :: acc)
  in aux n []

let string_gen shift_fun ind_update lst =
  snd (List.fold_left
    (fun (ind,acc) x -> (ind_update ind,
                         acc ^ (shift_fun ind) ^ x ^ "\n"))
    (0,"") lst)

let odd_els lst =
  List.rev (snd (List.fold_left
        (fun (ind, acc) x -> if ind=0 then (1,x::acc) else (0,acc))
        (0,[]) lst))

(* Offset all strings in list by n spaces *)
let offset n lst = List.map (fun x-> (String.make n ' ') ^ x) lst

let up_left_tri n =
  string_gen (fun x->"") (fun x->x) (make_tri '*' n)
let up_right_tri n =
  string_gen (fun x-> String.make (n-1-x) ' ')
             (fun x->x+1) (make_tri '*' n)
let dn_left_tri n =
  string_gen (fun x->"") (fun x->x) (List.rev (make_tri '*' n))
let dn_right_tri n =
  string_gen (fun x-> String.make x ' ') (fun x->x+1)
  (List.rev (make_tri '*' n))
let up_sym_tri n =
  string_gen (fun x-> String.make (n-1-x) ' ') (fun x->x+1)
  (odd_els (make_tri '*' (2*n)))
let dn_sym_tri n =
  string_gen (fun x-> String.make x ' ') (fun x->x+1)
  (List.rev (odd_els (make_tri '*' (2*n))))
let dn_sym_tri_offset d n =
  string_gen (fun x-> String.make x ' ') (fun x->x+1)
  (offset d (List.rev (odd_els (make_tri '*' (2*n)))))

let draw_ul n = Printf.printf "%s" (up_left_tri n)
let draw_ur n = Printf.printf "%s" (up_right_tri n)
let draw_dl n = Printf.printf "%s" (dn_left_tri n)
let draw_dr n = Printf.printf "%s" (dn_right_tri n)
let draw_us n = Printf.printf "%s" (up_sym_tri n)
let draw_ds n = Printf.printf "%s" (dn_sym_tri n)
let draw_dia n = Printf.printf "%s%s"
  (up_sym_tri n) (dn_sym_tri_offset 1 (n-1))

[code]

[permlink]