173 lines
5.2 KiB
OCaml
Executable File
173 lines
5.2 KiB
OCaml
Executable File
open General
|
|
|
|
|
|
let empty : 'a list = []
|
|
|
|
let rec length_helper (list : 'a list) (length : int) =
|
|
match list with
|
|
| [] -> length
|
|
| _ :: xs -> length_helper xs Int.(length + 1)
|
|
|
|
let length (list : 'a list) = length_helper list 0
|
|
|
|
let head (ls : 'a list) : 'a option =
|
|
match ls with
|
|
| x :: xs -> Some x
|
|
| [] -> None
|
|
|
|
let tail (ls : 'a list) : 'a list =
|
|
match ls with
|
|
| x :: xs -> xs
|
|
| [] -> []
|
|
|
|
let rec reverse_helper (ls : 'a list) (acc : 'a list) : 'a list =
|
|
match ls with
|
|
| x :: xs -> reverse_helper xs (x :: acc)
|
|
| [] -> acc
|
|
|
|
let reverse (ls : 'a list) : 'a list =
|
|
reverse_helper ls []
|
|
|
|
let rec append_tr_helper (ls1_rev : 'a list) (ls2 : 'a list) : 'a list =
|
|
match ls1_rev with
|
|
| [] -> ls2
|
|
| x :: xs ->
|
|
append_tr_helper xs (x :: ls2)
|
|
|
|
let append_tr (ls1 : 'a list) (ls2 : 'a list) : 'a list =
|
|
append_tr_helper (reverse ls1) ls2
|
|
|
|
let ( @ ) = append_tr
|
|
|
|
let rec map (f : 'a -> 'b) (ls : 'a list) : 'b list =
|
|
match ls with
|
|
| x :: xs -> f x :: map f xs
|
|
| [] -> []
|
|
|
|
let rec map_rev_tr_helper (f : 'a -> 'b) (ls : 'a list) (acc : 'b list) : 'b list =
|
|
match ls with
|
|
| x :: xs -> map_rev_tr_helper f xs (f x :: acc)
|
|
| [] -> acc
|
|
|
|
let map_rev_tr (f : 'a -> 'b) (ls : 'a list) : 'b list =
|
|
map_rev_tr_helper f ls []
|
|
|
|
let rec map_tr_helper (f : 'a -> 'b) (ls : 'a list) (acc : 'b list) : 'b list =
|
|
match ls with
|
|
| x :: xs -> map_tr_helper f xs (f x :: acc)
|
|
| [] -> reverse acc
|
|
|
|
let rec map_tr (f : 'a -> 'b) (ls : 'a list) : 'b list =
|
|
map_tr_helper f ls []
|
|
|
|
let rec foldl (f : 's -> 'a -> 's) (init : 's) (ls : 'a list) : 's =
|
|
match ls with
|
|
| x :: xs -> xs |> foldl f (f init x)
|
|
| [] -> init
|
|
|
|
let rec foldr (f : 's -> 'a -> 's) (init : 's) (ls : 'a list) : 's =
|
|
foldl f init (reverse ls)
|
|
|
|
let rec zip2_rev_tr_helper (ls1 : 'a list) (ls2 : 'b list) (acc : ('a * 'b) list) : ('a * 'b) list result =
|
|
|
|
let first_head = head ls1 in
|
|
let second_head = head ls2 in
|
|
|
|
if first_head = None & second_head = None then
|
|
Success acc
|
|
else if (first_head = None & second_head <> None) or (first_head <> None & second_head = None) then
|
|
Error "The two lists must be of the same length."
|
|
else
|
|
let a = match first_head with | Some x -> x | None -> Fatal.failwith "if this exception is raised there is an error in the implementation of the function that called it" in
|
|
let b = match second_head with | Some x -> x | None -> Fatal.failwith "if this exception is raised there is an error in the implementation of the function that called it" in
|
|
|
|
zip2_rev_tr_helper (tail ls1) (tail ls2) ((a, b) :: acc)
|
|
|
|
let rec zip2_rev_tr (ls1 : 'a list) (ls2 : 'b list) : ('a * 'b) list result =
|
|
zip2_rev_tr_helper ls1 ls2 []
|
|
|
|
let zip2_tr (ls1 : 'a list) (ls2 : 'b list) : ('a * 'b) list result =
|
|
match zip2_rev_tr ls1 ls2 with
|
|
| Success x -> Success (reverse x)
|
|
| Error message -> Error message
|
|
|
|
let rec unzip2_rev_tr_helper (ls : ('a * 'b) list) (acc1 : 'a list) (acc2 : 'b list) : ('a list) * ('b list) =
|
|
match ls with
|
|
| (first, second) :: xs -> unzip2_rev_tr_helper xs (first :: acc1) (second :: acc2)
|
|
| [] -> (acc1, acc2)
|
|
|
|
let unzip2_rev_tr (ls : ('a * 'b) list) : ('a list) * ('b list) =
|
|
unzip2_rev_tr_helper ls [] []
|
|
|
|
let rec pairwise_helper (ls : 'a list) (h : 'a) (acc : ('a * 'a) list) : ('a * 'a) list =
|
|
match ls with
|
|
| a :: (b :: tail) ->
|
|
let remaining = b :: tail in
|
|
let new_acc = ((a, b) :: acc) in
|
|
pairwise_helper remaining h new_acc
|
|
| [a] -> (a, h) :: acc
|
|
| _ -> acc
|
|
|
|
let pairwise (ls : 'a list) : ('a * 'a) list =
|
|
match ls with
|
|
| [] -> []
|
|
| [_] -> []
|
|
| x :: xs ->
|
|
pairwise_helper ls x []
|
|
|
|
let rec contains (a : 'a) (ls : 'a list) : bool =
|
|
match ls with
|
|
| x :: xs -> if x = a then true else contains a xs
|
|
| [] -> false
|
|
|
|
let singleton (a : 'a) : 'a list =
|
|
a :: []
|
|
|
|
let rec filter_rev_tr_helper (f : 'a -> bool) (ls : 'a list) (acc : 'a list) : 'a list =
|
|
match ls with
|
|
| x :: xs ->
|
|
if f x then
|
|
filter_rev_tr_helper f xs (x :: acc)
|
|
else
|
|
filter_rev_tr_helper f xs acc
|
|
| [] -> acc
|
|
|
|
let filter_rev_tr (f : 'a -> bool) (ls : 'a list) : 'a list =
|
|
filter_rev_tr_helper f ls []
|
|
|
|
let rec find_helper (f : 'a -> bool) (ls : 'a list) (index : int) : ('a * int) option =
|
|
match ls with
|
|
| x :: xs -> if f x then Some (x, index) else find_helper f xs Int.(1 + index)
|
|
| [] -> None
|
|
|
|
let find (f : 'a -> bool) (ls : 'a list) : ('a * int) option =
|
|
find_helper f ls 0
|
|
|
|
let rec initialize_helper (f : int -> 'a) (length : int) (index : int) (acc : 'a list) : 'a list =
|
|
if length = index then
|
|
acc
|
|
else
|
|
initialize_helper f length Int.(index + 1) ((f index) :: acc)
|
|
|
|
let initialize (f : int -> 'a) (length : int) : 'a list =
|
|
initialize_helper f length 0 []
|
|
|
|
|
|
|
|
|
|
|
|
external unsafe_get: 'a array -> int -> 'a = "%array_unsafe_get"
|
|
external array_length : 'a array -> int = "%array_length"
|
|
|
|
let rec of_array_helper arr i res =
|
|
let open Int in
|
|
if i < 0 then
|
|
res
|
|
else
|
|
of_array_helper arr (i - 1) (unsafe_get arr i :: res)
|
|
|
|
|
|
let of_array arr =
|
|
let open Int in
|
|
of_array_helper arr (array_length arr - 1) []
|
|
|