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 = 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"]
