F #의 장면 뒤에서 패턴 일치가 어떻게 작동합니까?

Question

필자는 F # (및 함수형 프로그래밍)에 완전히 익숙하지 않지만 샘플 코드에서 어디에서나 패턴 일치를 사용합니다. 예를 들어 패턴 매칭이 실제로 어떻게 작동하는지 궁금합니다. 예를 들어 다른 언어의 for 루프와 동일한 작업을하고 컬렉션의 각 항목에 일치하는 항목이 있는지 상상해보십시오. 이것은 아마도 정확하지 않을 것입니다. 실제로 장면 뒤에서 실제로 어떻게 작동합니까?

Answer 1

어떤 패턴 매칭을 의미 하느냐에 따라 매우 강력한 구조이며 모든 종류의 방식으로 사용될 수 있습니다. 그러나 패턴 매칭이리스트에서 어떻게 작동하는지 설명하려고합니다. 당신은 예를 들어 이러한 패턴을 작성할 수 있습니다

match l with 
| [1; 2; 3] -> // specific list of 3 elements 
| 1::rest -> // list starting with 1 followed by more elements 
| x::xs ->  // non-empty list with element 'x' followed by a list 
| [] ->   // empty list (no elements) 

은 F 번호 목록이 실제로 차별 이가지 경우를 포함하는 조합입니다 - 다른 요소 뒤에 첫 번째 요소 x와 목록을 나타내는 빈 목록 또는 x::xs을 나타내는 []. C#에서, 이것은 다음과 같이 표현 될 수 있습니다

// Represents any list 
abstract class List<T> { } 
// Case '[]' representing an empty list 
class EmptyList<T> : List<T> { } 
// Case 'x::xs' representing list with element followed by other list 
class ConsList<T> : List<T> { 
    public T Value { get; set; } 
    public List<T> Rest { get; set; } 
} 

패턴 위 (이 단순한를 만들기 위해 내가 사용 의사 코드) 다음에 컴파일 될 것이다 : 당신이 할 수

if (l is ConsList) && (l.Value == 1) && 
    (l.Rest is ConsList) && (l.Rest.Value == 2) && 
    (l.Rest.Rest is ConsList) && (l.Rest.Rest.Value == 3) && 
    (l.Rest.Rest.Rest is EmptyList) then 
    // specific list of 3 elements 
else if (l is ConsList) && (l.Value == 1) then 
    var rest = l.Rest; 
    // list starting with 1 followed by more elements 
else if (l is ConsList) then 
    var x = l.Value, xs = l.Rest; 
    // non-empty list with element 'x' followed by a list 
else if (l is EmptyList) then 
    // empty list (no elements) 

보세요, 루핑이 필요 없습니다. F #에서 목록을 처리 할 때 반복을 사용하여 반복을 구현하지만 전체 목록을 함께 구성하는 개별 요소 (ConsList)에 패턴 일치가 사용됩니다. 리스트에 일치

패턴 sepp2k하여 설명 판별 연합의 특정 경우이다. 패턴 매칭에 나타날 수있는 다른 구조가 있지만 본질적으로 모두는 일부 (복잡한) if 문을 사용하여 컴파일됩니다.

Answer 2

아니요, 반복되지 않습니다. 이

match x with 
| Foo a b -> a + b 
| Bar c -> c 

같은 패턴 일치가있는 경우이이 의사 코드 같은 아래로 컴파일 :

if (x is a Foo) 
    let a = (first element of x) in 
    let b = (second element of x) in 
    a+b 
else if (x is a Bar) 
    let c = (first element of x) in 
    c 

푸와 바 생성자 (즉, 유형 type FooBar = Foo int int | Bar int 같이 정의 대수 데이터 유형에서 인 경우) x is a Foo과 x is a Bar은 단순한 비교입니다. 그것들이 active pattern에 의해 정의되면, 연산은 그 패턴에 의해 정의됩니다.

Answer 3

패턴 일치는 실제로 어떻게 작동합니까? for 루프와 동일합니까?

그것은 약으로 멀리 for 루프에서 당신이 상상할 수과 같습니다 대신 반복의, 패턴 매치는 효율적인 자동 장치로 컴파일 입니다. 오토 마톤에는 두 가지 스타일이 있습니다. 하나는 "결정 트리"이고 "프랑스 스타일"입니다. 각 스타일은 다른 이점을 제공합니다. 의사 결정 트리는 최소값의 값을 검사하지만 순진한 구현에는 최악의 경우 지수 코드 공간이 필요할 수 있습니다. 프랑스 스타일은 시간과 공간의 절충점을 제공합니다. 둘 다 최적이지만 최적은 아닙니다.

그러나이 문제에 대한 절대적으로 결정적인 작업은 2008 ML 워크샵의 Luc Maranget의 우수한 논문 "Compiling Pattern Matching to Good Decisions Trees입니다. Luc의 논문은 기본적으로 두 세계의 장점을 얻는 방법을 보여줍니다. 아마추어가 좀 더 쉽게 접근 할 수있는 치료를 원하면 내 자신의 제안을 겸허하게 권합니다. When Do Match-Compilation Heuristics Matter?

패턴 일치 컴파일러를 작성하는 것은 쉽고 재미 있습니다!

Answer 4

F # 코드를 .exe로 컴파일하면 Reflector과 함께 보시면 F # 코드의 C# "equivalent"를 볼 수 있습니다.

저는이 방법을 사용하여 F # 예제를 꽤 많이 보았습니다.