# HG changeset patch
# User Matthias Görgens <matthias.goergens@xxxxxxxxxx>
# Date 1265126416 0
# Node ID c3c6244bb7d6387caed5c200ead5b20fab27485f
# Parent  93721338057fdff1465e54be45bd282fd1af0de0
Adds take and tails to our extended list module

`take' gives the first n elements of a list (or less if the list is
shorter).  `tails' gives a list of all suffixes of a list.

Signed-off-by: Matthias Görgens <matthias.goergens@xxxxxxxxxx>

diff -r 93721338057f -r c3c6244bb7d6 stdext/listext.ml
--- a/stdext/listext.ml
+++ b/stdext/listext.ml
@@ -11,6 +11,7 @@
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU Lesser General Public License for more details.
  *)
+open Fun
 module List = struct include List
 
 (** Turn a list into a set *)
@@ -174,4 +175,21 @@
 (* Like the Lisp cons *)
 let cons a b = a :: b
 
+(* Could use fold_left to get the same value, but that would necessarily go through the whole list everytime, instead of the first n items, only. *)
+(* ToDo: This is complicated enough to warrant a test. *)
+(* Is it wise to fail silently on negative values?  (They are treated as zero, here.)
+   Pro: Would mask fewer bugs.
+   Con: Less robust.
+*)
+let take n list =
+    let rec helper i acc list =
+	if i <= 0 || list = []
+	then acc
+	else helper (i-1)  (List.hd list :: acc) (List.tl list)
+    in List.rev $ helper n [] list
+
+(* Thanks to sharing we only use linear space. (Roughly double the space needed for the spine of the original list) *)
+let rec tails = function
+    | [] -> [[]]
+    | (_::xs) as l -> l :: tails xs
 end
diff -r 93721338057f -r c3c6244bb7d6 stdext/listext.mli
--- a/stdext/listext.mli
+++ b/stdext/listext.mli
@@ -172,4 +172,9 @@
     (* Like Lisp cons*)
     val cons : 'a -> 'a list -> 'a list
 
+    (* take n list: Return the first n elements of list (or less if list is shorter).*)
+    val take : int -> 'a list -> 'a list
+	
+    val tails : 'a list -> ('a list) list
+
   end