const xs = [1, 2, 3];
const ys = xs;
console.log(xs); // [1, 2, 3]
ys[0] = 0;
console.log(xs); // [0, 2, 3]
module ImmutableArray = struct
let set (arr : 'a array) (pos : int) (value : 'a) =
if (pos >= 0) && (pos < (Array.length arr)) then
let copied = Array.copy arr in
Array.unsafe_set copied pos value;
Some copied
else
None
...
end
let x = [|1;2;3;4;5|] (* [1,2,3,4,5] *)
let y = ImmutableArray.set x 0 42 (* Some [42,2,3,4,5] *)
1
x0
2
3
4
5
6
7
8
9
1
x0
2
3
4
5
6
7
8
9
1
3
3
4
5
6
7
8
9
x1
1
x0
2
3
4
5
6
7
8
9
1
3
3
4
5
6
7
8
9
x1
x0
Object 1
Object 2
Object 2'
Object 3
...
...
x1
All manipulations are O(n)
1
x0
let x0 = [1]
1
2
x0
3
x1
3 :: 2 :: x0
let x0 = [1] in
let x1 =
1
2
x0
3
x1
4
x2
4 :: x1
let x2 =
let x0 = [1] in
let x1 = 3 :: 2 :: x0 in
1
2
x0
3
x1
4
x2
5
x3
5 :: x1
let x1 = 3 :: 2 :: x0 in
let x0 = [1] in
let x3 =
let x2 = 4 :: x1 in
type 'a myList =
| Nil
| Cons of 'a * 'a myList
let map (func: ('a -> 'b)) (list: 'a myList): 'b myList =
let rec helper xs acc =
match xs with
| Nil -> acc
| Cons (head, tail) -> helper tail (Cons (func head, acc))
in
helper list Nil
Pattern match on the inductive definition.
Eg:
["a"; "b"; "c"; "d"]
|> ([1; 2; 3; 4]
|> List.fold_left2 (fun acc x y -> (x, y) :: acc) [])
|> List.rev
vs
let zip xs ys
= List.fold_left2 (fun acc x y -> (x, y) :: acc) [] xs ys
|> List.rev;
zip ["a"; "b"; "c"; "d"] [1; 2; 3; 4]
O(1)
O(n)
Your lists are stacks. Using them as "random accessing sequence" is wrong!
List.nth lst 9
Don't do the following:
if List.length xs == 0 then
...
else
...
let rec reverse (xs : 'a list) : 'a list =
match xs with
| [] -> []
| head :: tail -> (reverse tail) @ [head]
Phil Bagwell
RRB-Trees: Efficient Immutable Vectors
https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
a | b | c | d | e | f | g | h | i | j |
---|
k | l | m | n | o | p | q | r | s | t |
---|
u | v | w |
---|
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s | t |
---|
u | v | w |
---|
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s | t |
---|
u | v | w |
---|
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s | t |
---|
u | v | w |
---|
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s | t |
---|
u | v | w |
---|
Implement a "Vector", "Dynamic Array"
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s | t |
---|
u | v | w |
---|
17 → 01 00 01
Vector.get 17
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s | t |
---|
u | v | w |
---|
Vector.get 17
17 → 01 00 01
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s | t |
---|
u | v | w |
---|
Vector.get 17
17 → 01 00 01
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | s | t |
---|
u | v | w |
---|
Vector.get 17
17 → 01 00 01
r
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | s | t |
---|
u | v | w |
---|
Vector.set 17 "R"
r
q | s | t |
---|
R
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | s | t |
---|
u | v | w |
---|
Vector.set 17 "R"
r
q | s | t |
---|
R
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | s | t |
---|
u | v | w |
---|
Vector.set 17 "R"
r
q | s | t |
---|
R
a | b | c | d |
---|
e | f | g | h |
---|
i | j | k | l |
---|
m | n | o | p |
---|
q | r | s |
---|
t | u |
---|
16 | 19 | 23 |
---|
2 | 4 |
---|
3 |
---|
v | w |
---|
O(log(n))
Implement "Unordered Set/Map", "Hash Set/Map", "Dictionary"
Tries were first described by René de la Briandais in 1959. The term trie was coined two years later by Edward Fredkin, who pronounces it /ˈtriː/ (as "tree"), after the middle syllable of retrieval. However, other authors pronounce it /ˈtraɪ/ (as "try"), in an attempt to distinguish it verbally from "tree".
Using hash values as indices
n
hash('n') → 01 00 01
m |
---|
l | e | k |
---|
f | a |
---|
g | c | b |
---|
o | h |
---|
j | i | d |
---|
O(log(n))
a | b | c | d |
---|
a | b | c |
---|
v1
v1'
You don't need to allocate what is not there
(defn vrange [n]
(loop [i 0 v []]
(if (< i n)
(recur (inc i) (conj v i))
v)))
(defn vrange2 [n]
(loop [i 0 v (transient [])]
(if (< i n)
(recur (inc i) (conj! v i))
(persistent! v))))
;; benchmarked (Java 1.8, Clojure 1.7)
(def v (vrange 1000000)) ;; 73.7 ms
(def v2 (vrange2 1000000)) ;; 19.7 ms
Chris Okasaki
Purely Functional Data Structures
https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504
Dr. Matthew Hammer
CSCI 4830-016 Principles of Functional Programming
http://matthewhammer.org/courses/pfp-s18/