Purely Functional Data Structures - Chris Okasaki

gistfile1.ml

(* This uses the @ operator (aka List.append) which is not tail recursive *)
let suffixes list =
	let rec loop l acc =
		match l with
		| [] -> acc
		| x::xs -> loop xs (acc @ [xs]) in
	loop list [list]

(* This uses an operator @+ constructed from two tail recursive methods... :P *)
let suffixesTR list =
        let (@+) x y = List.rev_append (List.rev x) y in
	let rec loop l acc =
		match l with
		| [] -> acc
		| x::xs -> loop xs (acc @+ [xs]) in
	loop list [list]

(* These can be rewritten from scratch... *)
let myrev list =
   let rec loop acc list1 =
      match list1 with
      | [] -> acc
      | x::xs -> loop (x::acc) xs
   in loop [] list

let myappend lis t =
   let rec loop acc list =
      match list with
      | [] -> acc
      | x::xs -> loop (x::acc) xs
   in loop t (myrev lis)

(*...*)

(* Or even more condensed *)
let rec myrevappend acc list = 
   match list with
   | [] -> acc
   | x::xs -> myrevappend (x::acc) xs

let myappend1 lis t =
   myrevappend t (myrevappend [] lis)

let suffixesTR1 list =
        let (@++) = myappend1 in
	let rec loop l acc =
		match l with
		| [] -> acc
		| x::xs -> loop xs (acc @++ [xs]) in
	loop list [list]

(* This isn't really that much better than what we started with, of course. :D *)