:PROPERTIES:
:ID: cf967e5c-c8fd-4fd3-b333-e7c26925dca4
:mtime: 20231013021904 20231011021328
:ctime: 20231011021244
:END:
#+title: Ocaml Lists
#+filetags: :public:project:
* Lists in OCAML
Ocaml lists are implemented internally as linked lists.
Elements Ocaml lists must all have the same type.
Ocaml Lists must be finite.
* Syntax of OCAML Lists
#+BEGIN_SRC ocaml
[ 3 ; 5 ; 9 ] : int list
#+END_SRC
* Primitive Operaterations on OCAML Lists
** Concatenate/append Lists
#+BEGIN_SRC ocaml
[1 ; 2 ; 3] @ [ 4 ; 5] = [1 ; 2 ; 3 ; 4 ; 5]
-- time complexity is O(n)
-- space complexity is O(n)
let rec append = function
| ([] , ys) -> ys
| (hd :: tl , ys) -> hd :: append tl ys
#+END_SRC
** Reverse a List
#+BEGIN_SRC ocaml
List.rev [1 ; 2 ; 3] = [3 ; 2 ; 1]
-- time complexity is O(n^2)
-- space complexity is O(n)
let rec reverse = function
| [] -> []
| x :: xs -> reverse xs @ [x]
-- time complexity is O(n)
-- space complexity is O(1)
let rec rev_acc = function
| ([] , ys) = ys
| (x :: xs , ys) = rev_acc xs (x :: ys)
#+END_SRC
** Check if a list is empty
#+BEGIN_SRC ocaml
List.null [] = true
#+END_SRC
** Get the head/first element of a list
#+BEGIN_SRC ocaml
List.hd [ 1 ; 2 ; 3] = 1
#+END_SRC
** Get the tail/rest of a list
#+BEGIN_SRC ocaml
List.tl [ 1 ; 2 ; 3] = [2 ; 3]
#+END_SRC
** Get the length of a list
#+BEGIN_SRC ocaml
List.length [ 1 ; 2 ; 3] = 3
#+END_SRC
** Take the first $n$ elements of a list
#+BEGIN_SRC ocaml
-- space complexity is O(n)
let rec take i = function
| [] -> []
| x :: xs -> if i <= 0 then [] else x :: take (i - 1) xs
#+END_SRC
** drop the first $n$ elements of a list
Space complexity is $O(n)$.
#+BEGIN_SRC ocaml
-- space complexity is O(n)
let rec drop i = function
| [] -> []
| x :: xs -> if i <= 0 then x :: xs else drop (i - 1) xs
#+END_SRC
** Check if an element is a member of a list
#+BEGIN_SRC ocaml
let rec isMember x = function
| [] -> false
| y :: ys -> if x = y then true else isMember x ys
#+END_SRC
** Take the intersection of 2 lists
#+BEGIN_SRC ocaml
let rec listIntersection xs ys =
match xs , ys with
| [] , ys -> []
| x :: xs , ys -> if isMember x ys then x :: listIntersection xs ys else listIntersection xs ys
#+END_SRC
** Zip lists
Zip a pair of lists into a list of pairs.
#+BEGIN_SRC ocaml
let rec zip (xs :'a list) (ys : 'b list) : ('a * 'b) list =
match xs , ys with
| (x :: xs , y :: ys) -> (x , y) :: zip xs ys
| _ -> []
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
zip [1 ; 2 ; 3] [5 ; 6]
#+END_SRC
#+RESULTS:
| 1 | 5 |
| 2 | 6 |
** Unzip Lists
#+BEGIN_SRC ocaml
let conspair ((x , y) , (xs , ys)) = (x :: xs , y :: ys)
let rec unzip = function
| p :: xs -> conspair (p , unzip xs)
| [] -> ([], [])
#+END_SRC
#+RESULTS:
: <fun>
#+BEGIN_SRC ocaml :exports both
unzip [1 , "one" ; 3 , "three" ; 5 , "five"]
#+END_SRC
#+RESULTS:
| 1 | 3 | 5 |
| one | three | five |
** Linear search of list
* Inductive Definition of a List
All Ocaml lists are of the form
#+BEGIN_SRC ocaml
[] : 'a list (* The empty list *)
#+END_SRC
or
#+BEGIN_SRC ocaml
List.cons head tail : 'a -> 'a list -> 'a list (* a CONS cell *)
#+END_SRC
* Asymptotic Complexity of List
List.cons is O(1) space and O(1) time