OCaml - retourner une liste contenant les queues de cette liste

Question

Pour [1;2;3;4;5], je veux revenir [[1;2;3;4;5];[2;3;4;5];[3;4;5;];[4;5];[5];[]]

Je suis en train d'utiliser la bibliothèque de la liste mais je ne suis pas sûr comment. Jusqu'à présent, je sais que je dois utiliser List.tl pour obtenir la liste sans le premier élément

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

Je l'ai fait récursive, mais maintenant, je veux simplement utiliser la bibliothèque de la liste sans utiliser récursivité. EDIT: Désolé, ce que j'ai spécifié pour la fonction à retourner est incorrect. Juste mis à jour avec la sortie correcte.

Answer 1

Comme je l'ai dit dans le commentaire, ce ne sont pas les queues de l mais des copies des queues de 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]; []] 

Answer 2

Il n'y a pas de bonne façon d'écrire cette fonction en termes de fonctions intégrées .

La réponse que vous donnez dans votre question est bien, mais il serait plus idiomatiques de ne pas annoter les types et l'utilisation function:

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

D'autres langues, comme F #, fournir une fonction List.unfold que tails peut être écrit en terme de.

Answer 3

"Sans utiliser la récursivité" ... pourquoi? La récursivité est un outil utile, même en dehors de la bibliothèque List.

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

Votre fonction (qui ne compile pas parce que vous utilisez tails au lieu de tailsoflist) retourne la liste des suffixes d'une liste. En raison de la structure de la liste, il est plus facile à calculer que les préfixes.

Vous pouvez exprimer les préfixes des suffixes:

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

Vous pouvez faire une version directe à l'aide d'un accumulateur:

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

et l'exprimer en utilisant List.fold_left si vous voulez éviter récursion, mais ceci est alambiqué donc vous devriez préférer la version directe à mon avis:

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 

Enfin, il est possible de détruire votre cerveau avec une version utilisant des suites, mais je ne me souviens pas du code exact. En gros, la continuation est équivalente à l '"accumulateur" de la version directe.

Answer 4

Ah, l'ancien truc à accumuler sur la liste originale pour lancer tails comme un catamorphisme.Cela se fait sans récursion explicite en utilisant seulement les fonctions du module List:

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

Elle produit les queues que vous attendez:

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

et les queues sont les queues de structure réelle de la liste d'entrée , de sorte que List.tl l == List.hd (List.tl (tails l)).