Co to jest „dopasowywanie wzorców” w językach funkcjonalnych?

Czytam o programowaniu funkcjonalnym i zauważyłem, że dopasowywanie wzorców jest wymieniane w wielu artykułach jako jedna z podstawowych cech języków funkcyjnych.

Czy ktoś może wyjaśnić programistom Java / C ++ / JavaScript, co to oznacza?

Zrozumienie dopasowania wzorców wymaga wyjaśnienia trzech części:

1. Algebraiczne typy danych.
2. Co to jest dopasowanie wzorców
3. Dlaczego to jest niesamowite.

Algebraiczne typy danych w pigułce

Języki funkcyjne podobne do ML umożliwiają definiowanie prostych typów danych zwanych „rozłącznymi związkami” lub „algebraicznymi typami danych”. Te struktury danych są prostymi kontenerami i można je definiować rekurencyjnie. Na przykład:

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

definiuje strukturę danych podobną do stosu. Potraktuj to jako odpowiednik tego 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;
        }
    }
}

Tak więc identyfikatory Consi Nildefiniują prostą prostą klasę, w którejof x * y * z * ... definiuje konstruktor i niektóre typy danych. Parametry konstruktora są nienazwane, są identyfikowane przez pozycję i typ danych.

Tworzysz instancje swojej a listklasy jako takie:

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

Co jest tym samym, co:

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

Dopasowanie wzorców w pigułce

Dopasowywanie wzorców to rodzaj testowania typu. Powiedzmy, że utworzyliśmy obiekt stosu podobny do powyższego, możemy zaimplementować metody podglądania i zdejmowania stosu w następujący sposób:

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"

Powyższe metody są równoważne (chociaż nie są zaimplementowane jako takie) dla następującego języka 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();
}

(Prawie zawsze języki ML implementują dopasowywanie wzorców bez testów typu lub rzutowania w czasie wykonywania, więc kod C # jest nieco zwodniczy. Pomińmy szczegóły implementacji, machając ręką :))

Rozkład struktury danych w pigułce

Ok, wróćmy do metody podglądu:

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

Sztuczka polega na zrozumieniu, że identyfikatory hdi tlsą zmiennymi (errm ... ponieważ są niezmienne, tak naprawdę nie są „zmiennymi”, ale „wartościami”;)). Jeśli sma typ Cons, to wyciągniemy jego wartości z konstruktora i powiążemy je ze zmiennymi o nazwach hdi tl.

Dopasowywanie wzorców jest przydatne, ponieważ pozwala nam rozłożyć strukturę danych na podstawie jej kształtu zamiast zawartości . Wyobraź sobie więc, że zdefiniujemy drzewo binarne w następujący sposób:

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

Możemy zdefiniować niektóre obroty drzew w następujący sposób:

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 = functionKonstruktor to cukier składniowy let rotateRight s = match s with ...).

Więc oprócz powiązania struktury danych ze zmiennymi, możemy również przejść do niej. Powiedzmy, że mamy węzeł let x = Node(Nil, 1, Nil). Jeśli wywołasz rotateLeft x, sprawdzamy xpierwszy wzorzec, który nie pasuje, ponieważ właściwe dziecko ma typ Nilzamiast Node. Przeniesie się do następnego wzorca, x -> xktóry dopasuje dowolne dane wejściowe i zwróci je niezmodyfikowane.

Dla porównania napisalibyśmy powyższe metody w C # jako:

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))));
    }
}

Na poważnie.

Dopasowywanie wzorów jest niesamowite

Możesz zaimplementować coś podobnego do dopasowywania wzorców w C # przy użyciu wzorca gościa , ale nie jest on tak elastyczny, ponieważ nie można skutecznie rozłożyć złożonych struktur danych. Ponadto, jeśli używasz dopasowywania wzorców, kompilator poinformuje Cię, czy pominąłeś przypadek . Jakie to niesamowite?

Pomyśl o tym, jak zaimplementowałbyś podobną funkcjonalność w C # lub językach bez dopasowywania wzorców. Pomyśl, jak byś to zrobił bez testów i rzutów w czasie wykonywania. Z pewnością nie jest twardy , po prostu uciążliwy i nieporęczny. I nie musisz sprawdzać kompilatora, aby upewnić się, że uwzględniłeś każdy przypadek.

Tak więc dopasowanie wzorców pomaga dekomponować i nawigować po strukturach danych w bardzo wygodnej, zwartej składni, pozwala kompilatorowi przynajmniej trochę sprawdzić logikę kodu. To naprawdę jest cechą zabójca.

Krótka odpowiedź: Dopasowanie wzorców pojawia się, ponieważ języki funkcjonalne traktują znak równości jako potwierdzenie równoważności zamiast przypisania.

Długa odpowiedź: Dopasowywanie wzorców jest formą wysyłki opartą na „kształcie” podanej wartości. W języku funkcjonalnym typy danych, które definiujesz, to zwykle tak zwane związki rozłączne lub algebraiczne typy danych. Na przykład, co to jest lista (połączona)? Połączona lista Listrzeczy pewnego typu ajest albo pustą listąNil albo jakimś elementem a Conswpisanym na List a(listę elementów a). Piszemy to w języku Haskell (języku funkcjonalnym, który jest mi najbardziej znany)

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

Wszystkie związki rozłączne są definiowane w ten sposób: pojedynczy typ ma określoną liczbę różnych sposobów jego tworzenia; twórcy, jakNil i Constutaj, nazywani są konstruktorami. Oznacza to, że wartość typu List amogłaby zostać utworzona za pomocą dwóch różnych konstruktorów - mogłaby mieć dwa różne kształty. Załóżmy więc, że chcemy napisać headfunkcję, która pobierze pierwszy element listy. W Haskell napisalibyśmy to jako

-- `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

Od List a wartości mogą być dwóch różnych rodzajów, musimy traktować każdą z nich osobno; to jest dopasowanie wzorców. W head x, jeśli xpasuje do wzorca Nil, uruchamiamy pierwszy przypadek; jeśli pasuje do wzorca Cons h _, uruchamiamy drugi.

Krótka odpowiedź, wyjaśniona: Myślę, że jednym z najlepszych sposobów myślenia o tym zachowaniu jest zmiana sposobu myślenia o znaku równości. W językach z nawiasami klamrowymi, =ogólnie rzecz biorąc , oznacza przypisanie: a = boznacza „przekształcić aw b”. Jednak w wielu językach funkcjonalnych =oznacza stwierdzenie równości: let Cons a (Cons b Nil) = frob x stwierdza, że rzecz po lewej stronie Cons a (Cons b Nil)jest równoważna rzeczy po prawej stronie frob x; ponadto wszystkie zmienne użyte po lewej stronie stają się widoczne. To samo dzieje się z argumentami funkcji: zapewniamy, że pierwszy argument wygląda jak Nil, a jeśli nie, sprawdzamy dalej.

To znaczy, że zamiast pisać

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;
}

Możesz pisać

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

Hej, C ++ obsługuje również dopasowywanie wzorców.

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;
};

Dopasowywanie wzorców jest czymś w rodzaju przeciążonych metod stosowanych na sterydach. Najprostszy przypadek byłby z grubsza taki sam, jak ten, który widziałeś w java, argumenty to lista typów z nazwami. Prawidłowa metoda do wywołania jest oparta na przekazanych argumentach i podwaja się jako przypisanie tych argumentów do nazwy parametru.

Wzorce idą o krok dalej i mogą jeszcze bardziej zniszczyć przekazywane argumenty. Potencjalnie może również używać strażników do rzeczywistego dopasowania na podstawie wartości argumentu. Aby to zademonstrować, będę udawać, że JavaScript ma dopasowanie do wzorca.

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

W foo2 oczekuje, że a będzie tablicą, rozbija drugi argument, oczekując obiektu z dwoma właściwościami (prop1, prop2) i przypisuje wartości tych właściwości do zmiennych d i e, a następnie oczekuje, że trzeci argument będzie 35.

W przeciwieństwie do JavaScript, języki z dopasowywaniem wzorców zwykle dopuszczają wiele funkcji o tej samej nazwie, ale różnych wzorcach. W ten sposób jest to jak przeładowanie metody. Podam przykład w języku erlang:

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

Rozmyj trochę oczy i możesz to sobie wyobrazić w javascript. Może coś takiego:

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

Chodzi o to, że kiedy wywołujesz fibo, implementacja, której używa, jest oparta na argumentach, ale tam, gdzie Java jest ograniczona do typów jako jedynego sposobu na przeciążenie, dopasowanie wzorców może zdziałać więcej.

Oprócz przeciążania funkcji, jak pokazano tutaj, ta sama zasada może być zastosowana w innych miejscach, takich jak opisy przypadków lub oceny destrukturyzujące. JavaScript ma to nawet w wersji 1.7 .

Dopasowanie wzorców umożliwia dopasowanie wartości (lub obiektu) do niektórych wzorców w celu wybrania gałęzi kodu. Z punktu widzenia C ++ może to brzmieć trochę podobnie do switchstwierdzenia. W językach funkcjonalnych dopasowywanie wzorców może służyć do dopasowywania standardowych wartości pierwotnych, takich jak liczby całkowite. Jest to jednak bardziej przydatne w przypadku typów złożonych.

Najpierw pokażmy dopasowywanie wzorców na wartościach pierwotnych (używając rozszerzonego 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')
}

Drugie zastosowanie dotyczy funkcjonalnych typów danych, takich jak krotki (które umożliwiają przechowywanie wielu obiektów w jednej wartości) i rozłącznych związków, które pozwalają na utworzenie typu, który może zawierać jedną z kilku opcji. Brzmi to trochę jak enumz wyjątkiem tego, że każda etykieta może również zawierać pewne wartości. W składni pseudo-C ++:

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

Wartość typu Shapemoże teraz zawierać Rectanglewszystkie współrzędne lub a Circleze środkiem i promieniem. Dopasowanie wzorców pozwala napisać funkcję do pracy z Shapetypem:

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)
}

Wreszcie, możesz również użyć zagnieżdżonych wzorców, które łączą obie te funkcje. Na przykład, możesz użyć Circle(0, 0, radius)do dopasowania dla wszystkich kształtów, które mają środek w punkcie [0, 0] i mają dowolny promień (wartość promienia zostanie przypisana do nowej zmiennej radius).

Może to zabrzmieć trochę obco z punktu widzenia C ++, ale mam nadzieję, że moje pseudo-C ++ wyjaśni wyjaśnienie. Programowanie funkcjonalne opiera się na zupełnie innych koncepcjach, więc ma sens w języku funkcjonalnym!

Dopasowywanie wzorców polega na tym, że interpreter Twojego języka wybierze określoną funkcję na podstawie struktury i treści argumentów, które mu podajesz.

Jest to nie tylko funkcjonalna funkcja języka, ale jest dostępna dla wielu różnych języków.

Po raz pierwszy wpadłem na ten pomysł, kiedy nauczyłem się prologu, w którym jest to naprawdę kluczowe dla języka.

na przykład

last ([LastItem], LastItem).

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

Powyższy kod da ostatnią pozycję z listy. Argument wejściowy jest pierwszym, a wynikiem jest drugi.

Jeśli na liście jest tylko jedna pozycja, interpreter wybierze pierwszą wersję, a drugi argument zostanie ustawiony na równy pierwszej, tj. Do wyniku zostanie przypisana wartość.

Jeśli lista ma zarówno nagłówek, jak i koniec, tłumacz wybierze drugą wersję i będzie powtarzał, dopóki na liście nie zostanie tylko jedna pozycja.

Dla wielu osób wybór nowej koncepcji jest łatwiejszy, jeśli podano kilka łatwych przykładów, więc zaczynamy:

Powiedzmy, że masz listę trzech liczb całkowitych i chcesz dodać pierwszy i trzeci element. Bez dopasowania wzorców można to zrobić w ten sposób (przykłady w Haskell):

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

Teraz, chociaż jest to przykład zabawki, wyobraź sobie, że chcielibyśmy powiązać pierwszą i trzecią liczbę całkowitą ze zmiennymi i zsumować je:

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

To wyodrębnianie wartości ze struktury danych jest tym, co robi dopasowywanie wzorców. Zasadniczo "odzwierciedlasz" strukturę czegoś, dając zmienne do powiązania z interesującymi miejscami:

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

Gdy wywołasz tę funkcję z [1,2,3] jako argumentem, [1,2,3] zostanie ujednolicone z [pierwszy _, trzeci], wiążąc najpierw z 1, od trzeciego do 3 i odrzucając 2 ( _jest symbolem zastępczym rzeczy, na których nie zależy).

Teraz, jeśli chcesz dopasować tylko listy z 2 jako drugim elementem, możesz to zrobić w następujący sposób:

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

To zadziała tylko dla list z 2 jako drugim elementem, aw przeciwnym razie zgłosi wyjątek, ponieważ nie podano definicji addFirstAndThird dla niepasujących list.

Do tej pory używaliśmy dopasowania wzorców tylko do wiązania destrukturyzującego. Ponadto możesz podać wiele definicji tej samej funkcji, w przypadku gdy używana jest pierwsza definicja dopasowania, dlatego dopasowanie wzorca przypomina trochę „instrukcję przełączającą na stereoidach”:

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

addFirstAndThird z radością doda pierwszy i trzeci element list z 2 jako drugim elementem, aw przeciwnym razie „spadnie” i „zwróci” 0. Ta funkcja „podobna do przełącznika” może być używana nie tylko w definicjach funkcji, np .:

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

Co więcej, nie jest ograniczony do list, ale może być również używany z innymi typami, na przykład dopasowywaniem konstruktorów wartości Just i Nothing typu Maybe w celu „rozpakowania” wartości:

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

Jasne, to były zwykłe przykłady zabawek i nawet nie próbowałem podać formalnego ani wyczerpującego wyjaśnienia, ale powinny one wystarczyć, aby uchwycić podstawową koncepcję.

Powinieneś zacząć od strony Wikipedii, która daje całkiem dobre wyjaśnienie. Następnie przeczytaj odpowiedni rozdział w książce Haskell wikibook .

To jest fajna definicja z powyższego wikibooka:

Zatem dopasowywanie wzorców jest sposobem przypisywania nazw rzeczom (lub wiązania tych nazw z tymi rzeczami) i być może równoczesnym rozbiciem wyrażeń na podwyrażenia (tak jak zrobiliśmy z listą w definicji mapy).

Oto naprawdę krótki przykład, który pokazuje przydatność dopasowywania wzorców:

Powiedzmy, że chcesz posortować element na liście:

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

do (posortowałem „Nowy Jork”)

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

w bardziej imperatywnym języku napisałbyś:

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;
}

Zamiast tego w języku funkcjonalnym napisałbyś:

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

Jak widać, rozwiązanie z dopasowanym wzorcem ma mniej hałasu, możesz wyraźnie zobaczyć, jakie są różne przypadki i jak łatwo jest podróżować i usuwać strukturę naszej listy.

Napisałem na ten temat bardziej szczegółowy wpis na blogu tutaj .