Map

(key, value) data structure @OCaml

Map is a functional datastructure (balanced binary tree) implementing finite maps over a totally-ordered domain, called a "key".

The map types and operations appear in three places:

| Map      | polymorphic map operations                                      |
| Map.Poly | maps that use polymorphic comparison to order keys              |
| Key.Map  | maps with a fixed key type that use [Key.compare] to order keys |

Python 과 Java 같은 다른 언어에서는 dictionary 와 비슷.

Dijkstra algorithm 을 이용하여 short path in weighted graph 길찾기 프로그램을 만들던 중
단순하게 list 를 이용해서 풀고 있었으나 gpt 가 map 을 제안해줘서 functor 를 기억해내고 새로 적용함.

list ->
기본적으로 모든 리스트 요소를 돌고, 확인하기 때문에 O(n)
List.fold_left는 매번 List.mem을 사용해 중복을 확인,
List.mem은 선형 탐색을 수행하므로 시간 복잡도는 O(n^2) 까지 갈 수도 있음

Map ->
이진 검색 트리 기반으로 동작하며, 키 검색과 삽입
destination을 추출하는 데 O(k) (간선의 수).
중복 제거는 최종적으로 한 번만 수행.
big o-notation 은 O(logn) 으로 가능

reference
https://ocaml.janestreet.com/ocaml-core/109.20.00/doc/core/Map.html

https://blog.janestreet.com/generic-mapping-and-folding-in-ocaml/

https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html