OCaml의 그래프에게 내가 서명 정점 일부 그래프를 볼 심지어 내 자신과 함께 온 정점 모듈

Question

감독 :

module type VERTEX = sig 
    type t 
    type label 

    val equal : t -> t -> bool 
    val create : label -> t 
    val label : t -> label 
end 

을하지만 모듈로 구현하는 방법을 완전히 아무 생각이 없다. 어떤 종류의 라벨을 부착해야합니까? 라벨을 기반으로 t를 만들려면 어떻게해야합니까? 그리고 t 레이블을 어떻게 얻습니까?

Answer 1

서명을 기반으로 모듈을 구현하는 것은 미니 퍼즐과 같습니다. 다음과 같이 분석 할 방법은 다음과 같습니다.

해당 서명을 읽을 때 첫 번째 발언은 해당 서명에값을 작성하는 방법이 없다는 것입니다. 따라서 우리의 구현은 조금 더 커야합니다. 아마도 type label = string을 지정하면됩니다.

지금, 우리는이 :

val create : label -> t 
val label : t -> label 

전단 사 함수 (유형은 "동등"입니다)입니다. 구현하는 가장 간단한 방법은 type t = label을 정의하는 것이므로 실제로는 하나의 유형이지만 모듈의 외부에서는 알지 못합니다.

나머지는 우리가 label = string 및 t = label 말했다

type t 
val equal: t -> t -> bool 

입니다. 따라서 t = string 및 equal은 문자열 같음입니다.

붐! 여기에 우리가 있습니다 : 동일한 파일에 정의하려는 경우

module String_vertex : VERTEX with type label = string = struct 
    type label = string 
    type t = string 

    let equal = String.equal 

    let create x = x 
    let label x = x 
end 

VERTEX with type label = string 부분은 단지이다.

(* string_vertex.ml *) 
type label = string 
type t = string 

let equal = String.equal 

let create x = x 
let label x = x 

및 F(String_vertex)으로 호출 할 수있는 VERTEX 소요 어떤 펑터 F : 그렇지 않으면, 당신은 뭔가를 할 수 있습니다. 내용이 include VERTEX with type label = string 인 string_vertex.mli을 만드는 것이 가장 좋습니다.

Answer 2

저는 Graphlib의 작성자입니다. 따라서이 질문이 내 마음에 직접 닿으므로 지나칠 수 없습니다. 솔직히, 나는이 질문을 수백만 번 오프라인으로 받았고 결코 좋은 대답을 줄 수 없었다.

실제 문제는 OCamlGraph 라이브러리의 그래프 인터페이스가 엉망입니다. 우리는 Graphlib을 수정하기위한 시도로 시작했습니다. 그러나 OCamlGraph는 Graph 알고리즘의 중요한 저장소이므로 OCamlGraph 인터페이스와 호환되도록 자신을 제한했습니다. 우리에게 가장 큰 문제점은 기본적으로 레이블 세트와 노드 세트 사이에 쌍점을 설정하는이 Vertex 인터페이스였습니다. 사람들은 일반적으로 이것을 이해하지 못합니다. 왜 레이블이 같고 꼭지점이 다른 두 가지 유형이 필요한 이유는 무엇입니까? 실제로

의 VERTEX 인터페이스의 간단한 구현이 경우 다음과 같은 모듈

module Int : VERTEX with type label = int = struct 
    type t = int 
    type label = int 
    let create x = x 
    let label x = x 
end 

, 우리는 참으로 라벨의 세트와 정점의 세트 사이 (신원 endofunctor를 통해) 사소한 전단 사 함수가 .

그러나, 깊은 모습은 전단 사 함수가 일대일 매핑으로 서명

val create : label -> t 
val label : t -> label 

은 정말 전단 사 함수 아니라는 것을 우리에게 보여줍니다. 유형 시스템에 의해 실제로 요구되거나 시행되는 것은 아닙니다. 예를 들어, create 함수는 을 t으로 투사 할 수 있습니다. 여기서 label은 정점 패밀리의 고유 한 요소입니다. 그에 상응하여, label 기능은 고유 한 레이블을 반환하고 다른 모든 것을 잊어 버리는 잊어 버리는 기능을합니다.

이 방법을 감안할 때, 우리는 다른 구현 할 수 있습니다 :

module Labeled = struct 
    type label = int 
    type t = { 
     label : label; 
     data : ""; 
    } 

    let create label = {label; data = ""} 
    let label n = n.label 
    let data n = n.data 
    let with_data n data = {n with data} 
    let compare x y = compare x.label y.label 
    end 

그 구현에서를, 우리는 노드의 ID로 라벨을 사용하고, 임의의 속성은 노드에 부착 할 수 있습니다. 이 해석에서, create 함수는 노드의 모든 세트를 equivalence classes의 세트로 분할하는데, 클래스의 모든 멤버는 동일한 신원을 공유한다. 즉, 이들은 상이한 시간 또는 공간에서 동일한 실제 엔티티를 나타낸다. 예 :

type color = Red | Yellow | Green 
module TrafficLight = struct 
    type label = int 
    type t = { 
    id : label; 
    color : color 
    } 

    let create id = {id; color=Red} 
    let label t = t.id 
    let compare x y = compare x.id y.id 
    let switch t color = {t with color} 
    let color t = t.color 
end 

이 모델에서는 신호등을 ID 번호로 나타냅니다. 색상 속성은 교통 신호등의 신원에 영향을 미치지 않습니다 (교통 신호등이 다른 색상으로 전환하면 함수형 프로그래밍 언어에서는 두 개의 다른 객체로 표시되지만 신호등은 여전히 ​​동일한 신호등입니다).

위의 표현의 주된 문제점은 모든 그래프 교과서에서 반대표 의미 인 불투명 한 속성으로 레이블이 사용된다는 것입니다. 교과서에서는 교통 신호등의 색상을 레이블로 참조합니다. 노드 자체는 int로 표현됩니다. 그렇기 때문에 OCamlGraph 인터페이스가 엉망진창이어서 Graphlib 인터페이스가 엉망이라고 말하고 있습니다. 따라서 교과서 모순에 빠지지 않으려면 레이블이없는 그래프를 사용해야합니다 (int은 아마 노드를 가장 잘 표현한 것입니다). 또한 노드에 속성을 연결해야하는 경우 배열,지도, 연관 목록 또는 기타 사전과 같은 외부 유한 맵을 사용할 수 있습니다. 그렇지 않으면 레이블이 레이블이 아니라 노드라는 점에 유의해야합니다. 이 모든으로

이의 그래프의 정점위한 더 나은 인터페이스를 지정할 수 있습니다 말했다 : 그것은 이름을 변경 동형 모듈이기 때문에,

module type VERTEX = sig 
    type id 
    type label 
    type t 

    val create : id -> t 
    val id : t -> id 
    val label : t -> label 
    val with_label : t -> label -> label 
end 

제안 된 인터페이스는 사용자 인터페이스와 호환을 (따라서 OCamlGraph 포함) (즉, label을 id으로 변경했습니다. 또한 효율적이지 않은 레이블이없는 노드를 만들 수 있습니다. 여기서는 id = t이며 외부 매핑에 의존하지 않고 노드에 임의의 정보를 첨부 할 수 있습니다.