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 = (* note that this is different from the builtin *)
   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]


(* Adding a left fold to the mix... *)
let suffixesTR2 list =
   let (@+++) li st = 
      let xcons acc x = x::acc in
      let fc = List.fold_left xcons in
      fc st (fc [] li) in

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

   loop list [list]


(* Nice to play with all that, but Brian McNamara's, where we started, 
   has got to be faster: https://gist.github.com/941867

   Every version I've shown here does a bunch of repetitive list reversing.
*)