Hi, I'm Ataias Reis

Programmer, made in Brazil, Alma mater University of Brasilia

Dedup chars in a string using OCaml

Hi there! The goal of this challenge is to remove all duplicate chars in a string. The following input/output will explain it by itself:

# input
abcabczabczabc
# output
abcz

I tried to write the functions to explode and implode from what I remembered, but in the end I had to take another look at their code here. Those were auxiliary functions to help me to write remove_all_dups.

open Core.Std
(* string -> char list *)
let explode str =
  let len = String.length str in
  let rec expl str i =
    if i > len - 1 then [] else
      str.[i]::(expl str (i+1)) in
  expl str 0

(* char list -> string *)
let implode clist =
  let len = List.length clist in
  let str = String.create len in
  let rec impl i = function
    | [] -> str
    | c :: l -> str.[i] <- c; impl (i+1) l in
  impl 0 clist

(* string -> string *)
let remove_all_dups str =
  let char_list = explode str in
  let s = Set.empty ~comparator:Char.comparator in
  let rec remove s no_dup_l = function
    | [] -> no_dup_l
    | c :: t ->
       let f = fun x -> x = c in
       let found = Set.exists s ~f:f in
       if found then
         remove s no_dup_l t
       else
         let s = Set.add s c in
         remove s (c :: no_dup_l) t in
  remove s [] char_list
  |> List.rev
  |> implode

let a = read_line();;
print_string (remove_all_dups a);;

If you take a look at the function remove_all_dups, there is a set that is used to keep tracks of the chars that were already seen. First I tried to use a map, but it was too much overkill and more complicated in my opinion. Sets are more specialized and ideal for that.

Thanks for reading!

Note: After reading some more, I could write a much simpler code to dedup the string, with no need to write implode or explode by hand, they are already available at Core.Std:

(* This would be the whole code for the
   program above, with the exception of IO *)
let dedup_string str =
  String.to_list str
  |> List.dedup
  |> String.of_char_list;;

Nevertheless, this doesn’t guarantee the order. Anyway, if order is important, like in this problem, I could change implode by String.of_char_list and explode by String.to_list in the program shown before, avoiding to use List.dedup.

Tags
comments powered by Disqus