Skip to main content
Code Review

Return to Answer

added 2484 characters in body
Source Link
Chris
Chris
  • 1.7k
  • 1
  • 3
  • 21
let main () =
  let first_repeat seq =
    let module Int_set = Set.Make (Int) in  
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_set.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
    in
    aux seq Int_set.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = sum + x in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat

While this is longer, we have decomposed the problem into simpler sub-problems, and the part that puts it all together is shorter and more expressive:

  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat

One more thing

We can use first class modules to make find_repeat more generically useful. It's not useful in this case because accum_seq requires an int Seq.t, but if we wanted to use it for other types of sequences it might be.

let main () =
  let first_repeat (type a) (module T : Set.OrderedType with type t = a) seq =
    let module S = Set.Make (T) in
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_setS.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_setS.add x history)
    in
    aux seq Int_setS.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = xsum + sumx in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat (module Int)

With an additional module signature we could make accum_seq more generically applicable. Also breaking the functions out of main.

module type Addable = sig
  type t
  val zero : t
  val add : t -> t -> t
end

let first_repeat (type a) (module T : Set.OrderedType with type t = a) seq =
  let module S = Set.Make (T) in
  let rec aux seq history =
    match seq () with   
    | Seq.Nil -> failwith "Shouldn't be encountered"
    | Seq.Cons (x, _) when S.mem x history -> x   
    | Seq.Cons (x, seq) -> aux seq (S.add x history)
  in
  aux seq S.empty

let accum_seq (type a) (module T : Addable with type t = a) seq =
  let rec aux seq sum () =
    match seq () with
    | Seq.Nil as s -> s
    | Seq.Cons (x, seq) -> 
      let sum = T.add sum x in 
      Seq.Cons (sum, aux seq sum)
  in
  aux seq T.zero

let main () =
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq (module Int)
  |> first_repeat (module Int)

As a quick demonstration:

# let module S = struct
    type t = string
    let zero = ""
    let add = (^)
  end in
  ["hello"; " "; "world"]
  |> List.to_seq
  |> accum_seq (module S)
  |> List.of_seq;;
- : string list = ["hello"; "hello "; "hello world"]

let main () =
  let module Int_set = Set.Make (Int) in
  let first_repeat seq =
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_set.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
    in
    aux seq Int_set.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = x + sum in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat

let main () =
  let first_repeat seq =
    let module Int_set = Set.Make (Int) in  
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_set.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
    in
    aux seq Int_set.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = sum + x in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat

While this is longer, we have decomposed the problem into simpler sub-problems, and the part that puts it all together is shorter and more expressive:

  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat

One more thing

We can use first class modules to make find_repeat more generically useful. It's not useful in this case because accum_seq requires an int Seq.t, but if we wanted to use it for other types of sequences it might be.

let main () =
  let first_repeat (type a) (module T : Set.OrderedType with type t = a) seq =
    let module S = Set.Make (T) in
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when S.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (S.add x history)
    in
    aux seq S.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = sum + x in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat (module Int)

With an additional module signature we could make accum_seq more generically applicable. Also breaking the functions out of main.

module type Addable = sig
  type t
  val zero : t
  val add : t -> t -> t
end

let first_repeat (type a) (module T : Set.OrderedType with type t = a) seq =
  let module S = Set.Make (T) in
  let rec aux seq history =
    match seq () with   
    | Seq.Nil -> failwith "Shouldn't be encountered"
    | Seq.Cons (x, _) when S.mem x history -> x   
    | Seq.Cons (x, seq) -> aux seq (S.add x history)
  in
  aux seq S.empty

let accum_seq (type a) (module T : Addable with type t = a) seq =
  let rec aux seq sum () =
    match seq () with
    | Seq.Nil as s -> s
    | Seq.Cons (x, seq) -> 
      let sum = T.add sum x in 
      Seq.Cons (sum, aux seq sum)
  in
  aux seq T.zero

let main () =
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq (module Int)
  |> first_repeat (module Int)

As a quick demonstration:

# let module S = struct
    type t = string
    let zero = ""
    let add = (^)
  end in
  ["hello"; " "; "world"]
  |> List.to_seq
  |> accum_seq (module S)
  |> List.of_seq;;
- : string list = ["hello"; "hello "; "hello world"]
deleted 2 characters in body
Source Link
Chris
Chris
  • 1.7k
  • 1
  • 3
  • 21
let main () =
  let first_repeat seq =
    let module Int_set = Set.Make (Int) in
  let first_repeat seq =
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_set.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
    in
    aux seq Int_set.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = x + sum in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat

let main () =
  let first_repeat seq =
    let module Int_set = Set.Make (Int) in
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_set.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
    in
    aux seq Int_set.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = x + sum in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat

let main () =
  let module Int_set = Set.Make (Int) in
  let first_repeat seq =
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_set.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
    in
    aux seq Int_set.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = x + sum in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat
Source Link
Chris
Chris
  • 1.7k
  • 1
  • 3
  • 21

As noted, you can refactor your slow code to utilize structural equality (=) rather than physical equality (==) and pattern-matching. It's still slow, but it's more idiomatic.

let main () =
  let rec my_slow_code lst history =
    match lst with
    | [] -> my_slow_code input history
    | x::xs ->
      let y = List.hd history in   
      let current = x + y in
      if List.mem current history then current
      else my_slow_code xs (current :: history)   
  in
  my_slow_code input [0]

If you use a set for history rather than a list, then adding is O(log n) rather than O(1), but lookup is also O(log n) rather than O(n).

let main () =
  let module Int_set = Set.Make (Int) in
  let rec aux lst prev history =
    match lst with
    | [] -> aux input prev history
    | x::xs ->
      let current = x + prev in
      if Int_set.mem current history then current
      else aux xs current (Int_set.add current history)   
  in
  aux input 0 (Int_set.singleton 0)

As Int_set isn't required outside of main it can be locally scoped.

Breaking it down

We know the input list can repeat forever. This suggests we want to convert the list to a sequence and then cycle it.

If we then have something with keeps a rolling accumulation of a sequence, and a function which finds the first repeat in a sequence, we can string it together to get the overall solution.

let main () =
  let first_repeat seq =
    let module Int_set = Set.Make (Int) in
    let rec aux seq history =
      match seq () with   
      | Seq.Nil -> failwith "Shouldn't be encountered"
      | Seq.Cons (x, _) when Int_set.mem x history -> x   
      | Seq.Cons (x, seq) -> aux seq (Int_set.add x history)
    in
    aux seq Int_set.empty
  in
  let accum_seq seq =
    let rec aux seq sum () =
      match seq () with
      | Seq.Nil as s -> s
      | Seq.Cons (x, seq) -> 
        let sum = x + sum in 
        Seq.Cons (sum, aux seq sum)
    in
    aux seq 0
  in
  input 
  |> List.to_seq 
  |> Seq.cycle 
  |> accum_seq 
  |> first_repeat