Skip to content

Instantly share code, notes, and snippets.

@killerswan

killerswan/gist:941923

Forked from mneedham/gist:941892
Created April 26, 2011 07:04
Download ZIP

Revisions

  1. killerswan revised this gist Apr 26, 2011. 1 changed file with 12 additions and 4 deletions.
    16 changes: 12 additions & 4 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,3 @@

    (* This uses the @ operator (aka List.append) which is not tail recursive *)
    let suffixes list =
    let rec loop l acc =
    @@ -7,6 +6,7 @@ let suffixes list =
    | 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
    @@ -16,6 +16,7 @@ let suffixesTR list =
    | x::xs -> loop xs (acc @+ [xs]) in
    loop list [list]


    (* These can be rewritten from scratch... *)
    let myrev list =
    let rec loop acc list1 =
    @@ -33,6 +34,7 @@ let myappend lis t =

    (*...*)


    (* Or even more condensed *)
    let rec myrevappend acc list = (* note that this is different from the builtin *)
    match list with
    @@ -50,9 +52,8 @@ let suffixesTR1 list =
    | 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
    Adding a left fold to the mix... *)

    (* Adding a left fold to the mix... *)
    let suffixesTR2 list =
    let (@+++) li st =
    let xcons acc x = x::acc in
    @@ -64,4 +65,11 @@ let suffixesTR2 list =
    | [] -> acc
    | x::xs -> loop xs (acc @+++ [xs]) in

    loop list [list]
    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.
    *)
  2. killerswan revised this gist Apr 26, 2011. 1 changed file with 8 additions and 12 deletions.
    20 changes: 8 additions & 12 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,4 @@



    (* This uses the @ operator (aka List.append) which is not tail recursive *)
    let suffixes list =
    let rec loop l acc =
    @@ -52,20 +50,18 @@ let suffixesTR1 list =
    | 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 *)


    (* Adding a left fold to the mix... *)
    (* This isn't really that much better than what we started with, of course. :D
    Adding a left fold to the mix... *)

    let suffixesTR2 list =
    let (@+++) li st =
    let prepend acc x = x::acc in
    let lfc = (List.fold_left prepend) in
    lfc st (lfc [] li) in
    let xcons acc x = x::acc in
    let fc = List.fold_left xcons in
    fc st (fc [] li) in

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

    loop [list] list
    loop list [list]
  3. killerswan revised this gist Apr 26, 2011. 1 changed file with 3 additions and 5 deletions.
    8 changes: 3 additions & 5 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -1,8 +1,6 @@





    (* This uses the @ operator (aka List.append) which is not tail recursive *)
    let suffixes list =
    let rec loop l acc =
    @@ -38,7 +36,7 @@ let myappend lis t =
    (*...*)

    (* Or even more condensed *)
    let rec myrevappend acc list =
    let rec myrevappend acc list = (* note that this is different from the builtin *)
    match list with
    | [] -> acc
    | x::xs -> myrevappend (x::acc) xs
    @@ -61,8 +59,8 @@ let suffixesTR1 list =

    let suffixesTR2 list =
    let (@+++) li st =
    let xcons xs x = x::xs in (* okay... *)
    let lfc = (List.fold_left xcons) in
    let prepend acc x = x::acc in
    let lfc = (List.fold_left prepend) in
    lfc st (lfc [] li) in

    let rec loop acc l =
  4. killerswan revised this gist Apr 26, 2011. 1 changed file with 27 additions and 22 deletions.
    49 changes: 27 additions & 22 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -1,19 +1,24 @@





    (* 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]
    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]
    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 =
    @@ -42,15 +47,16 @@ 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]
    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 *)


    (* Adding a left fold to the mix... *)

    let suffixesTR2 list =
    @@ -59,10 +65,9 @@ let suffixesTR2 list =
    let lfc = (List.fold_left xcons) in
    lfc st (lfc [] li) in

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

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

    loop [list] list
  5. killerswan revised this gist Apr 26, 2011. 1 changed file with 15 additions and 0 deletions.
    15 changes: 15 additions & 0 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -51,3 +51,18 @@ let suffixesTR1 list =

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

    (* Adding a left fold to the mix... *)

    let suffixesTR2 list =
    let (@+++) li st =
    let xcons xs x = x::xs in (* okay... *)
    let lfc = (List.fold_left xcons) in
    lfc st (lfc [] li) in

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

    loop [list] list

  6. killerswan revised this gist Apr 26, 2011. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -49,4 +49,5 @@ let suffixesTR1 list =
    | 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 *)
    (* This isn't really that much better than what we started with, of course. :D *)

  7. killerswan revised this gist Apr 26, 2011. No changes.
  8. killerswan revised this gist Apr 26, 2011. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -15,7 +15,7 @@ let suffixesTR list =
    | x::xs -> loop xs (acc @+ [xs]) in
    loop list [list]

    (* These can be rewritten... *)
    (* These can be rewritten from scratch... *)
    let myrev list =
    let rec loop acc list1 =
    match list1 with
  9. killerswan revised this gist Apr 26, 2011. 1 changed file with 36 additions and 0 deletions.
    36 changes: 36 additions & 0 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -14,3 +14,39 @@ let suffixesTR list =
    | [] -> acc
    | x::xs -> loop xs (acc @+ [xs]) in
    loop list [list]

    (* These can be rewritten... *)
    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 *)
  10. killerswan revised this gist Apr 26, 2011. 1 changed file with 6 additions and 5 deletions.
    11 changes: 6 additions & 5 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -1,15 +1,16 @@
    (* This uses the @ operator (aka List.append) which is not tail recursive *)
    let suffixes list =
    let rec loop l acc =
    match l with
    | [] -> acc
    | hd::tl -> loop tl (acc @ [tl]) in
    | 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 (@+) xs ys = List.rev_append (List.rev xs) ys in
    let rec loop list1 acc =
    match list1 with
    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]
  11. killerswan revised this gist Apr 26, 2011. 1 changed file with 12 additions and 3 deletions.
    15 changes: 12 additions & 3 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,15 @@
    let suffixesTR list =
    let suffixes list =
    let rec loop l acc =
    match l with
    | [] -> acc
    | hd::tl -> loop tl (List.concat [acc; [tl]])
    in loop list [list]
    | hd::tl -> loop tl (acc @ [tl]) in
    loop list [list]


    let suffixesTR list =
    let (@+) xs ys = List.rev_append (List.rev xs) ys in
    let rec loop list1 acc =
    match list1 with
    | [] -> acc
    | x::xs -> loop xs (acc @+ [xs]) in
    loop list [list]
  12. killerswan revised this gist Apr 26, 2011. 1 changed file with 2 additions and 3 deletions.
    5 changes: 2 additions & 3 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -2,6 +2,5 @@ let suffixesTR list =
    let rec loop l acc =
    match l with
    | [] -> acc
    | hd::tl -> loop tl (List.concat [acc; [l]])
    in
    loop list []
    | hd::tl -> loop tl (List.concat [acc; [tl]])
    in loop list [list]
  13. killerswan revised this gist Apr 26, 2011. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -2,7 +2,6 @@ let suffixesTR list =
    let rec loop l acc =
    match l with
    | [] -> acc
    | [last] -> loop [] (List.concat [acc; [[last]]; [[]]])
    | hd::tl -> loop tl (List.concat [acc; [l]])
    in
    loop list []
  14. @mneedham mneedham created this gist Apr 26, 2011.
    8 changes: 8 additions & 0 deletions gistfile1.ml
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,8 @@
    let suffixesTR list =
    let rec loop l acc =
    match l with
    | [] -> acc
    | [last] -> loop [] (List.concat [acc; [[last]]; [[]]])
    | hd::tl -> loop tl (List.concat [acc; [l]])
    in
    loop list []