OCaml -- return a list containing the tails of that list

For [1;2;3;4;5], I want to return [[1;2;3;4;5];[2;3;4;5];[3;4;5;];[4;5];[5];[]]

I'm trying to use the List library but I'm unsure how to. So far, I know I have to use List.tl to get the list without the first element

let rec tailsoflist (l : 'a list) : 'a list list =
  match l with
      [] -> [[]]
    | x::xs -> l::(tails xs)

I did this recursively but now I want to just use the list library without using recursion.

let tails (l : 'a list) : 'a list list

EDIT: Sorry guys, w开发者_如何学编程hat I specified for the function to return is incorrect. Just updated it with the correct output.

As I said in the comment, these are not the tails of l but copies of the tails of l:

# let tails l = List.fold_right (fun e acc -> (e::(List.hd acc))::acc) l [[]] ;;
val tails : 'a list -> 'a list list = <fun>
# tails [1; 2; 3; 4] ;;- : int list list = [[1; 2; 3; 4]; [2; 3; 4]; [3; 4]; [4]; []]

There is no good way to write that function in terms of the built-in functions.

The answer you give in your question is fine but it would be more idiomatic to not annotate the types and use function:

let rec tails = function
  | [] -> [[]]
  | _::xs' as xs -> xs::tails xs'

Other languages, like F#, provide a List.unfold function that tails can be written in terms of.

Ah, the old trick to accumulate on the original list to cast tails as a catamorphism. This is done without explicit recursion using just functions on the List module:

let tails l = List.rev ( [] :: snd (List.fold_right
    (fun _ (t,ts) -> List.tl t, t::ts) l (l, [])) )

It produces the tails as you expect:

# tails [1;2;3;4;5];;
- : int list list = [[1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5]; []]

and the tails are the actual structural tails of the input list, so that List.tl l == List.hd (List.tl (tails l)).

"Without using recursion"... why ? Recursion is a useful tool, even outside the List library.

let rec suffixes = function
| [] -> [[]]
| hd::tl as suff -> suff :: suffixes tl

Your function (which doesn't compile because you use tails instead of tailsoflist) returns the list of suffixes of a list. Due to the list structure, it's easier to compute than the prefixes.

You can express the prefixes from the suffixes :

let prefixes li = List.map List.rev (suffixes (List.rev li));;

You could do a direct version using an accumulator:

let prefixes li =
  let rec pref acc = function
    | [] -> List.rev acc :: []
    | hd::tl -> List.rev acc :: pref (hd :: acc) tl
  in pref [] li

and express it using List.fold_left if you want to avoid recursion, but this is convoluted so you should prefer the direct version in my opinion:

let prefixes li =
  let acc, res =
    List.fold_left
      (fun (acc, res) e -> (e :: acc), (List.rev acc :: res))
      ([], []) li in
  List.rev acc :: res

Finally, it is possible to destroy your brain with a version using continuations, but I don't remember the exact code. Roughly, the continuation is equivalent to the "accumulator" of the direct version.