기능적 언어에서 '패턴 일치'란 무엇입니까?

기능적 언어에서 '패턴 일치'란 무엇입니까?

---

함수형 프로그래밍에 대해 읽고 있는데 많은 기사에서 함수형 언어의 핵심 기능 중 하나로 패턴 일치 가 언급되어 있습니다.

누군가 Java / C ++ / JavaScript 개발자에게 무엇을 의미하는지 설명 할 수 있습니까?

---

패턴 일치를 이해하려면 다음 세 부분을 설명해야합니다.

1. 대수 데이터 유형.
2. 어떤 패턴 일치
3. 왜 대단해.

한마디로 대수 데이터 유형

ML과 같은 기능 언어를 사용하면 "비 연합"또는 "대수 데이터 형식"이라는 간단한 데이터 형식을 정의 할 수 있습니다. 이러한 데이터 구조는 간단한 컨테이너이며 재귀 적으로 정의 할 수 있습니다. 예를 들면 다음과 같습니다.

type 'a list =
    | Nil
    | Cons of 'a * 'a list

스택 형 데이터 구조를 정의합니다. 이 C #과 동등한 것으로 생각하십시오.

public abstract class List<T>
{
    public class Nil : List<T> { }
    public class Cons : List<T>
    {
        public readonly T Item1;
        public readonly List<T> Item2;
        public Cons(T item1, List<T> item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }
}

따라서 Cons및 Nil식별자는 간단한 of x * y * z * ...생성자 및 일부 데이터 유형을 정의하는 간단한 클래스를 정의합니다. 생성자에 대한 매개 변수는 이름이 없으며 위치 및 데이터 유형으로 식별됩니다.

다음 a list과 같이 클래스의 인스턴스를 만듭니다 .

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))

다음과 같습니다.

Stack<int> x = new Cons(1, new Cons(2, new Cons(3, new Cons(4, new Nil()))));

간단히 말해서 패턴 매칭

패턴 일치는 일종의 유형 테스트입니다. 위와 같은 스택 객체를 생성했다고 가정하면 다음과 같이 스택을 들여다보고 팝하는 메소드를 구현할 수 있습니다.

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

let pop s =
    match s with
    | Cons(hd, tl) -> tl
    | Nil -> failwith "Empty stack"

위의 방법은 다음과 같은 C #과 동일합니다 (구현되지는 않았지만).

public static T Peek<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return hd;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

public static Stack<T> Pop<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return tl;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

(거의 항상 ML 언어는 런타임 유형 테스트 또는 캐스트 없이 패턴 일치 를 구현 하므로 C # 코드는 다소 기만적입니다. 구현 세부 정보를 손으로 흔들며 적어주십시오.)

간단히 말해서 데이터 구조 분해

좋아, peek 방법으로 돌아가 봅시다.

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

트릭은 hd및 tl식별자가 변수 라는 것을 이해하고 있습니다 (errm ... 불변이기 때문에 실제로는 "변수"가 아니라 "값";)). 경우 s유형이있다 Cons, 우리는 생성자에서 그 값을 끌어가는 바인드 그들라는 이름의 변수로하고 hd와 tl.

패턴 일치는 데이터 구조를 내용 대신 모양으로 분해 할 수 있기 때문에 유용합니다 . 따라서 다음과 같이 이진 트리를 정의한다고 상상해보십시오.

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

다음과 같이 트리 회전 을 정의 할 수 있습니다 .

let rotateLeft = function
    | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
    | x -> x

let rotateRight = function
    | Node(Node(a, p, b), q, c) -> Node(a, p, Node(b, q, c))
    | x -> x

( let rotateRight = function생성자는의 구문 설탕입니다 let rotateRight s = match s with ....)

따라서 데이터 구조를 변수에 바인딩하는 것 외에도 드릴 다운 할 수 있습니다. node가 있다고 가정 해 봅시다 let x = Node(Nil, 1, Nil). 을 호출 하면 첫 번째 패턴에 대해 rotateLeft x테스트 x합니다. 첫 번째 패턴은 올바른 자식이 Nil대신 유형이 있기 때문에 일치하지 않습니다 Node. 다음 패턴으로 이동하여 x -> x입력과 일치하고 수정되지 않은 상태로 반환합니다.

비교를 위해 위의 메소드를 C #에서 다음과 같이 작성합니다.

public abstract class Tree<T>
{
    public abstract U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc);

    public class Nil : Tree<T>
    {
        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nilFunc();
        }
    }

    public class Node : Tree<T>
    {
        readonly Tree<T> Left;
        readonly T Value;
        readonly Tree<T> Right;

        public Node(Tree<T> left, T value, Tree<T> right)
        {
            this.Left = left;
            this.Value = value;
            this.Right = right;
        }

        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nodeFunc(Left, Value, Right);
        }
    }

    public static Tree<T> RotateLeft(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => r.Match(
                () => t,
                (rl, rx, rr) => new Node(new Node(l, x, rl), rx, rr))));
    }

    public static Tree<T> RotateRight(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => l.Match(
                () => t,
                (ll, lx, lr) => new Node(ll, lx, new Node(lr, x, r))));
    }
}

진심으로.

패턴 매칭이 대단합니다

방문자 패턴을 사용하여 C #에서 패턴 일치 와 유사한 것을 구현할 수 있지만 복잡한 데이터 구조를 효과적으로 분해 할 수 없기 때문에 유연성이 떨어집니다. 또한 패턴 일치를 사용하는 경우 컴파일러에서 사례를 생략했는지 알려줍니다 . 얼마나 대단한가요?

패턴 일치없이 C # 또는 언어로 유사한 기능을 구현하는 방법을 생각해보십시오. 런타임에 테스트 테스트 및 캐스트없이 어떻게 할 것인지 생각하십시오. 확실히 어렵지 않고 번거롭고 부피가 큽니다. 그리고 모든 경우를 다룰 수 있는지 확인하는 컴파일러가 없습니다.

따라서 패턴 일치는 매우 편리하고 간결한 구문으로 데이터 구조를 분해하고 탐색하는 데 도움이되므로 컴파일러가 코드 의 논리 를 조금이라도 확인할 수 있습니다. 정말 이다 킬러 기능입니다.

---

짧은 대답 : 기능적 언어는 등호 를 대입 대신 동등성 주장 으로 취급하기 때문에 패턴 일치가 발생 합니다.

긴 대답 : 패턴 일치는 주어진 값의 "모양"을 기반으로하는 디스패치 형태입니다. 기능적 언어에서 사용자가 정의한 데이터 유형은 일반적으로 차별적 조합 또는 대수 데이터 유형입니다. 예를 들어 (연결된) 목록은 무엇입니까? List어떤 유형의 것들에 대한 링크 된 목록 은 a빈 목록 Nil이거나 ( s 목록)에 a Consed 유형의 일부 요소입니다 . Haskell (가장 익숙한 기능 언어)에서 다음과 같이 씁니다.List aa

data List a = Nil
            | Cons a (List a)

모든 차별 노조는 이런 방식으로 정의됩니다. 단일 유형에는 고정 된 수의 다른 방식이 있습니다. 제작자는 같은 Nil과 Cons여기에 생성자라고합니다. 이것은 타입의 값이 List a두 개의 다른 생성자로 생성 될 수 있음을 의미합니다 . 두 개의 다른 모양을 가질 수 있습니다. head리스트의 첫 번째 요소를 얻는 함수 를 작성하려고한다고 가정하자 . Haskell에서는 다음과 같이 작성합니다.

-- `head` is a function from a `List a` to an `a`.
head :: List a -> a
-- An empty list has no first item, so we raise an error.
head Nil        = error "empty list"
-- If we are given a `Cons`, we only want the first part; that's the list's head.
head (Cons h _) = h

때문에 List a값이 서로 다른 두 종류의 수 있습니다, 우리는 개별적으로 각각을 처리 할 필요가; 이것이 패턴 일치입니다. 에서 head x, 경우 x일치 패턴은 Nil, 우리는 첫 번째 경우를 실행; 패턴과 일치 Cons h _하면 두 번째를 실행합니다.

짧은 대답, 설명 : 나는이 행동에 대해 생각하는 가장 좋은 방법 중 하나는 등호에 대한 생각을 바꾸는 것입니다. 중괄호 언어에서 대체로 =할당 a = b은 "make ainto "를 의미 b합니다. 그러나 많은 기능적 언어에서 =평등의 주장을 나타냅니다 . 왼쪽 에있는 것은 오른쪽에있는 것과 같다고 let Cons a (Cons b Nil) = frob x 주장 합니다 . 또한 왼쪽에 사용 된 모든 변수가 표시됩니다. 이것은 또한 함수 인수에서 일어나는 일입니다. 우리는 첫 번째 인수가 다음과 같다고 주장하고, 그렇지 않으면 계속 확인합니다.Cons a (Cons b Nil)frob xNil

---

그것은 쓰는 대신에

double f(int x, int y) {
  if (y == 0) {
    if (x == 0)
      return NaN;
    else if (x > 0)
      return Infinity;
    else
      return -Infinity;
  } else
     return (double)x / y;
}

당신은 쓸 수 있습니다

f(0, 0) = NaN;
f(x, 0) | x > 0 = Infinity;
        | else  = -Infinity;
f(x, y) = (double)x / y;

---

C ++은 패턴 매칭도 지원합니다.

static const int PositiveInfinity = -1;
static const int NegativeInfinity = -2;
static const int NaN = -3;

template <int x, int y> struct Divide {
  enum { value = x / y };
};
template <bool x_gt_0> struct aux { enum { value = PositiveInfinity }; };
template <> struct aux<false> { enum { value = NegativeInfinity }; };
template <int x> struct Divide<x, 0> {
  enum { value = aux<(x>0)>::value };
};
template <> struct Divide<0, 0> {
  enum { value = NaN };
};

#include <cstdio>

int main () {
    printf("%d %d %d %d\n", Divide<7,2>::value, Divide<1,0>::value, Divide<0,0>::value, Divide<-1,0>::value);
    return 0;
};

---

패턴 매칭은 스테로이드에 오버로드 된 방법과 비슷합니다. 가장 간단한 경우는 Java에서 본 것과 거의 동일하며 인수는 이름이있는 유형 목록입니다. 호출 할 올바른 메소드는 전달 된 인수를 기반으로하며 해당 인수를 매개 변수 이름에 지정하는 것으로 두 배가됩니다.

패턴은 한 걸음 더 나아가서 전달 된 인수를 더욱 체계적으로 만들 수 있습니다. 또한 인수 값에 따라 가드를 사용하여 실제로 일치시킬 수도 있습니다. 시연하기 위해 JavaScript에 패턴 일치가있는 것처럼 가장합니다.

function foo(a,b,c){} //no pattern matching, just a list of arguments

function foo2([a],{prop1:d,prop2:e}, 35){} //invented pattern matching in JavaScript

foo2에서 a는 배열이 될 것으로 예상하고 두 개의 props (prop1, prop2)가있는 객체를 기대하면서 두 번째 인수를 분리하고 해당 속성 값을 변수 d 및 e에 할당 한 다음 세 번째 인수는 다음과 같습니다. 35.

JavaScript와 달리 패턴 일치 언어는 일반적으로 이름은 같지만 패턴이 다른 여러 함수를 허용합니다. 이런 식으로 메소드 오버로드와 같습니다. erlang에서 예를 들어 보겠습니다.

fibo(0) -> 0 ;
fibo(1) -> 1 ;
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .

당신의 눈을 약간 흐리게하고 당신은 이것을 자바 스크립트로 상상할 수 있습니다. 이 같은 것 :

function fibo(0){return 0;}
function fibo(1){return 1;}
function fibo(N) when N > 0 {return fibo(N-1) + fibo(N-2);}

fibo를 호출 할 때 사용하는 구현은 인수를 기반으로하지만 오버로드의 유일한 수단으로 Java가 유형으로 제한되는 경우 패턴 일치로 더 많은 작업을 수행 할 수 있습니다.

여기에 표시된 기능 오버로드 외에도 사례 설명 또는 구조적 어설 션 제거와 같은 다른 위치에 동일한 원칙을 적용 할 수 있습니다. JavaScript는 1.7에서도 이것을 가지고 있습니다.

---

Pattern matching allows you to match a value (or an object) against some patterns to select a branch of the code. From the C++ point of view, it may sound a bit similar to the switch statement. In functional languages, pattern matching can be used for matching on standard primitive values such as integers. However, it is more useful for composed types.

First, let's demonstrate pattern matching on primitive values (using extended pseudo-C++ switch):

switch(num) {
  case 1: 
    // runs this when num == 1
  case n when n > 10: 
    // runs this when num > 10
  case _: 
    // runs this for all other cases (underscore means 'match all')
}

The second use deals with functional data types such as tuples (which allow you to store multiple objects in a single value) and discriminated unions which allow you to create a type that can contain one of several options. This sounds a bit like enum except that each label can also carry some values. In a pseudo-C++ syntax:

enum Shape { 
  Rectangle of { int left, int top, int width, int height }
  Circle of { int x, int y, int radius }
}

A value of type Shape can now contain either Rectangle with all the coordinates or a Circle with the center and the radius. Pattern matching allows you to write a function for working with the Shape type:

switch(shape) { 
  case Rectangle(l, t, w, h): 
    // declares variables l, t, w, h and assigns properties
    // of the rectangle value to the new variables
  case Circle(x, y, r):
    // this branch is run for circles (properties are assigned to variables)
}

Finally, you can also use nested patterns that combine both of the features. For example, you could use Circle(0, 0, radius) to match for all shapes that have the center in the point [0, 0] and have any radius (the value of the radius will be assigned to the new variable radius).

This may sound a bit unfamiliar from the C++ point of view, but I hope that my pseudo-C++ make the explanation clear. Functional programming is based on quite different concepts, so it makes better sense in a functional language!

---

Pattern matching is where the interpreter for your language will pick a particular function based on the structure and content of the arguments you give it.

It is not only a functional language feature but is available for many different languages.

The first time I came across the idea was when I learned prolog where it is really central to the language.

e.g.

last([LastItem], LastItem).

last([Head|Tail], LastItem) :- last(Tail, LastItem).

The above code will give the last item of a list. The input arg is the first and the result is the second.

If there is only one item in the list the interpreter will pick the first version and the second argument will be set to equal the first i.e. a value will be assigned to the result.

If the list has both a head and a tail the interpreter will pick the second version and recurse until it there is only one item left in the list.

---

You should start with the Wikipedia page that gives a pretty good explanation. Then, read the relevant chapter of the Haskell wikibook.

This is a nice definition from the above wikibook:

So pattern matching is a way of assigning names to things (or binding those names to those things), and possibly breaking down expressions into subexpressions at the same time (as we did with the list in the definition of map).

---

For many people, picking up a new concept is easier if some easy examples are provided, so here we go:

Let's say you have a list of three integers, and wanted to add the first and the third element. Without pattern matching, you could do it like this (examples in Haskell):

Prelude> let is = [1,2,3]
Prelude> head is + is !! 2
4

Now, although this is a toy example, imagine we would like to bind the first and third integer to variables and sum them:

addFirstAndThird is =
    let first = head is
        third = is !! 3
    in first + third

This extraction of values from a data structure is what pattern matching does. You basically "mirror" the structure of something, giving variables to bind for the places of interest:

addFirstAndThird [first,_,third] = first + third

When you call this function with [1,2,3] as its argument, [1,2,3] will be unified with [first,_,third], binding first to 1, third to 3 and discarding 2 (_ is a placeholder for things you don't care about).

Now, if you only wanted to match lists with 2 as the second element, you can do it like this:

addFirstAndThird [first,2,third] = first + third

This will only work for lists with 2 as their second element and throw an exception otherwise, because no definition for addFirstAndThird is given for non-matching lists.

Until now, we used pattern matching only for destructuring binding. Above that, you can give multiple definitions of the same function, where the first matching definition is used, thus, pattern matching is a little like "a switch statement on stereoids":

addFirstAndThird [first,2,third] = first + third
addFirstAndThird _ = 0

addFirstAndThird will happily add the first and third element of lists with 2 as their second element, and otherwise "fall through" and "return" 0. This "switch-like" functionality can not only be used in function definitions, e.g.:

Prelude> case [1,3,3] of [a,2,c] -> a+c; _ -> 0
0
Prelude> case [1,2,3] of [a,2,c] -> a+c; _ -> 0
4

Further, it is not restricted to lists, but can be used with other types as well, for example matching the Just and Nothing value constructors of the Maybe type in order to "unwrap" the value:

Prelude> case (Just 1) of (Just x) -> succ x; Nothing -> 0
2
Prelude> case Nothing of (Just x) -> succ x; Nothing -> 0
0

Sure, those were mere toy examples, and I did not even try to give a formal or exhaustive explanation, but they should suffice to grasp the basic concept.

---

Here is a really short example that shows pattern matching usefulness:

Let's say you want to sort up an element in a list:

["Venice","Paris","New York","Amsterdam"] 

to (I've sorted up "New York")

["Venice","New York","Paris","Amsterdam"] 

in an more imperative language you would write:

function up(city, cities){  
    for(var i = 0; i < cities.length; i++){
        if(cities[i] === city && i > 0){
            var prev = cities[i-1];
            cities[i-1] = city;
            cities[i] = prev;
        }
    }
    return cities;
}

In a functional language you would instead write:

let up list value =  
    match list with
        | [] -> []
        | previous::current::tail when current = value ->  current::previous::tail
        | current::tail -> current::(up tail value)

As you can see the pattern matched solution has less noise, you can clearly see what are the different cases and how easy it's to travel and de-structure our list.

I've written a more detailed blog post about it here.

참고URL : https://stackoverflow.com/questions/2502354/what-is-pattern-matching-in-functional-languages