Pack Consecutive Duplicates - difference in proposed solution on the Exercises page

Learning
1

Hello,
I’m a complete greeny, just started learning my first functional language. I did Pack Consecutive Duplicates exercise in a quite different way than the proposed solution.
Proposed solution:

let pack list =
    let rec aux current acc = function
      | [] -> []    (* Can only be reached if original list is empty *)
      | [x] -> (x :: current) :: acc
      | a :: (b :: _ as t) ->
         if a = b then aux (a :: current) acc t
         else aux [] ((a :: current) :: acc) t  in
    List.rev (aux [] [] list)

Vs. what I came up:

let pack lst = 
    let rec pack_aux acc = function
        | a :: (b :: _ as tl) -> 
                if a = b then pack_aux (b :: acc) tl 
                else acc :: pack_aux [b] tl
        | _ -> [ acc ]
    in
    match lst with
        | [] -> []
        | a :: _ -> pack_aux [a] lst

Expected result:

# pack ["a"; "a"; "a"; "a"; "b"; "c"; "c"; "a"; "a"; "d"; "d"; "e"; "e"; "e"; "e"];;
- : string list list =
[["a"; "a"; "a"; "a"]; ["b"]; ["c"; "c"]; ["a"; "a"]; ["d"; "d"];
 ["e"; "e"; "e"; "e"]]

Both solutions produce the same results, but I’d like to know:

  1. Does my solution fit in ‘functional’ approach to the problem? (In terms of multi year influence of procedural languages on my mind)
  2. Do I miss something in the proposed solution in terms of better design? IDK, maybe some hidden copies or the lack of tail call optimisation in my proposal?
2

Your pack_aux is not tail recursive (acc :: pack_aux [b] tl is not a tail call).
In exchange you get to avoid having the List.rev in the other solution.
It’s a similar difference as the usual

let rec non_tailrec_map f = function
| [] -> []
| x :: tl ->
  let fx = f x in
  fx :: non_tailrec_map f tl

(* vs *)

let tailrec_map f l =
  let rec aux acc = function
    | [] -> acc
    | x :: tl -> aux (f x :: acc) tl
  in
  List.rev (aux [] l)
1 Like
3

But note Tail Modulo Cons.

let[@tail_mod_cons] rec map f = function
  | [] -> []
  | x :: xs ->
    let y = f x in
    y :: map f xs
2 Likes