소개
바쁜 철도 네트워크를 위한 열차 운행 일정 시스템을 개발하는 프로젝트를 진행하고 있어요.
이 운행 일정 시스템에서 쓸 열차 노선의 프로토타입을 만들어 달라는 요청을 받았어요.
각 노선은 특정 열차가 정차하는 역들의 순서로 구성되어 있어요.
지침
여러분의 팀은 시간표에 있는 각 기차 노선을 표현하는 데 이중 연결 리스트를 사용하기로 했어요.
기차 노선을 따라 있는 각 역은 연결 리스트의 노드로 표현돼요.
역의 도착 시간과 출발 시간은 신경 쓰지 않아도 돼요.
각 역은 그냥 숫자로 표현돼요.
노선은 확장할 수 있어요. 노선의 처음이나 끝에 역을 추가하면 돼요.
노선의 처음이나 끝에서 역을 제거하면 노선을 줄일 수도 있어요.
가끔 역이 폐쇄되기도 하는데, 이때는 그 역이 노선의 처음이나 끝에 있지 않더라도 노선에서 제거해야 해요.
노선의 크기는 기차가 얼마나 멀리 가는지가 아니라 몇 개의 역에 정차하는지로 측정해요.
연결 리스트는 컴퓨터 과학의 기본적인 자료 구조로, 다른 자료 구조를 구현할 때 자주 사용돼요.
이름에서 알 수 있듯이, 연결 리스트는 서로 연결된 노드들의 리스트예요.
각 노드가 이웃한 노드 하나 또는 여러 개와 연결된 "노드"들의 리스트예요.
단일 연결 리스트에서는 각 노드가 자신의 뒤에 오는 노드에만 연결돼요.
이중 연결 리스트에서는 각 노드가 자신의 앞에 오는 노드와 뒤에 오는 노드 모두에 연결돼요.
연결 리스트를 더 깊이 파고들고 싶다면, 멋진 그림으로 설명해 주는 이 글을 확인해 봐요.
상태를 가진 자료 구조
Lean과 같은 함수형 언어에서는 대부분의 값이 설계상 불변이에요.
그래서 값을 갱신할 때는 보통 새로운 값을 만들어요.
예전 값과 새로운 값이 함께 존재하고, 둘 다 참조해서 사용할 수 있어요.
그런데 상태를 가진 값이 필요하거나, 어쩌면 꼭 있어야 하는 상황도 많아요.
상태를 가진 값은 새 값을 만드는 대신 예전 값을 _대체_하는 변경을 통해 갱신돼요.
변경이 일어나고 나면 갱신된 값만 접근할 수 있어요.
변경은 언어가 보장하는 몇 가지 규칙을 깨뜨릴 수 있다는 점에 주의해야 해요.
순수 함수는 같은 입력에 대해 항상 같은 결과를 반환해야 하지만, 입력이 시간에 따라 바뀔 수 있다면 같은 인자로 호출해도 다른 결과를 반환할 수 있어요.
마찬가지로, 결과를 반환하는 것 외에 외부에 변화를 일으키거나 매개변수 외의 다른 곳에서 값을 읽어 오는 함수라면, 같은 함수를 두 번 호출했을 때 결과가 서로 다를 수 있고, 때로는 예측할 수 없기도 해요.
이런 상태를 다루기 위해 Lean은 다른 함수형 언어들처럼, 부수 효과를 일으키는 함수를 순수 함수와 구별되는 특별한 구조로 감싸도록 해요.
이런 구조를 _모나드_라고 해요.
모든 상태를 가진 값은 부수 효과를 일으키는 어떤 모나드 안에 들어 있지만, 그렇다고 모든 모나드가 변경 가능한 상태를 나타내는 것은 아니라는 점이 중요해요.
"순수한" 모나드의 대표적인 예로는 Option, Except, Id가 있어요.
이 연습 문제에서는 LinkedList라는 상태를 가진 자료 구조를 정의해요.
이 자료 구조의 인스턴스는 변경을 통해 갱신돼요.
이를 지원하기 위해 모든 함수는 ST 모나드 안에 감싸여 있어요.
이 모나드에서는 변경 가능한 상태가 유일한 부수 효과이고, 변경 가능한 참조는 밖으로 빠져나올 수 없어요.
더 자세한 내용은 참고 자료에서 확인할 수 있어요.
출처
고전적인 컴퓨터 과학 주제
