Apakah 'Pencocokan Pola' dalam bahasa fungsional?

Saya membaca tentang pemrograman fungsional dan saya perhatikan bahwa Pencocokan Pola disebutkan dalam banyak artikel sebagai salah satu fitur inti dari bahasa fungsional.

Dapatkah seseorang menjelaskan untuk pengembang Java / C ++ / JavaScript apa artinya?

Memahami pencocokan pola memerlukan penjelasan tiga bagian:

1. Tipe data aljabar.
2. Apa itu pencocokan pola
3. Kenapa ini luar biasa.

Singkatnya, tipe data aljabar

Bahasa fungsional mirip-ML memungkinkan Anda menentukan tipe data sederhana yang disebut "disjoint unions" atau "tipe data aljabar". Struktur data ini adalah wadah sederhana, dan dapat didefinisikan secara rekursif. Sebagai contoh:

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

mendefinisikan struktur data seperti stack. Anggap itu setara dengan C # ini:

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

Jadi, Consdan Nilpengidentifikasi mendefinisikan kelas sederhana, di mana of x * y * z * ...mendefinisikan konstruktor dan beberapa tipe data. Parameter ke konstruktor tidak disebutkan namanya, mereka diidentifikasi oleh posisi dan tipe data.

Anda membuat instance a listkelas Anda seperti itu:

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

Yang sama dengan:

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

Pencocokan pola singkatnya

Pencocokan pola adalah sejenis pengujian tipe. Jadi katakanlah kita membuat objek stack seperti yang di atas, kita dapat menerapkan metode untuk mengintip dan meletupkan stack sebagai berikut:

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"

Metode di atas setara (meskipun tidak diterapkan seperti itu) dengan C # berikut:

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

(Hampir selalu, bahasa ML menerapkan pencocokan pola tanpa menjalankan jenis-tes atau gips, sehingga kode C # agak menipu. Mari menyikat detail implementasi dengan beberapa lambaian tangan :))

Singkatnya, struktur data dekomposisi

Ok, mari kembali ke metode mengintip:

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

Kuncinya adalah memahami bahwa hddan tlpengidentifikasi adalah variabel (errm ... karena mereka tidak berubah, mereka tidak benar-benar "variabel", tetapi "nilai";)). Jika smemiliki tipe Cons, maka kita akan menarik nilainya keluar dari konstruktor dan mengikatnya ke variabel bernama hddan tl.

Pencocokan pola berguna karena memungkinkan kita menguraikan struktur data berdasarkan bentuknya, bukan kontennya . Jadi bayangkan jika kita mendefinisikan pohon biner sebagai berikut:

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

Kita dapat mendefinisikan beberapa rotasi pohon sebagai berikut:

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 = functionKonstruktornya adalah gula sintaksis untuk let rotateRight s = match s with ....)

Jadi selain mengikat struktur data ke variabel, kita juga bisa menelusuri ke dalamnya. Katakanlah kita memiliki simpul let x = Node(Nil, 1, Nil). Jika kami memanggil rotateLeft x, kami menguji xterhadap pola pertama, yang gagal mencocokkan karena anak yang tepat memiliki jenis, Nilbukan Node. Ini akan pindah ke pola berikutnya x -> x,, yang akan cocok dengan input apa pun dan mengembalikannya tanpa dimodifikasi.

Sebagai perbandingan, kami akan menulis metode di atas dalam C # sebagai:

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

Untuk yang serius.

Pencocokan pola mengagumkan

Anda dapat menerapkan sesuatu yang mirip dengan pencocokan pola dalam C # menggunakan pola pengunjung , tetapi tidak hampir fleksibel karena Anda tidak dapat secara efektif menguraikan struktur data yang kompleks. Selain itu, jika Anda menggunakan pencocokan pola, kompiler akan memberi tahu Anda jika Anda meninggalkan kasing . Seberapa hebat itu?

Pikirkan tentang bagaimana Anda akan menerapkan fungsionalitas serupa dalam C # atau bahasa tanpa pencocokan pola. Pikirkan tentang bagaimana Anda akan melakukannya tanpa tes-tes dan gips saat runtime. Ini tentu tidak sulit , hanya rumit dan tebal. Dan Anda tidak memiliki pemeriksa memeriksa untuk memastikan Anda telah menutupi setiap kasus.

Jadi pencocokan pola membantu Anda menguraikan dan menavigasi struktur data dalam sintaksis yang sangat nyaman dan ringkas, memungkinkan kompiler untuk memeriksa logika kode Anda, setidaknya sedikit. Ini benar - benar fitur pembunuh.

Jawaban singkat: Pencocokan pola muncul karena bahasa fungsional memperlakukan tanda sama dengan sebagai pernyataan kesetaraan alih-alih penugasan.

Jawaban panjang: Pencocokan pola adalah bentuk pengiriman berdasarkan pada "bentuk" dari nilai yang diberikannya. Dalam bahasa fungsional, tipe data yang Anda tetapkan biasanya apa yang dikenal sebagai serikat terdiskriminasi atau tipe data aljabar. Misalnya, apa itu daftar (ditautkan)? Daftar yang ditautkan Listhal-hal dari beberapa jenis aadalah daftar kosong Nilatau beberapa elemen jenis a Consed ke List a(daftar as). Di Haskell (bahasa fungsional yang paling saya kenal), kami menulis ini

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

Semua serikat yang didiskriminasi didefinisikan dengan cara ini: satu tipe memiliki sejumlah cara berbeda untuk membuatnya; pencipta, seperti Nildan di Conssini, disebut konstruktor. Ini berarti bahwa nilai dari tipe tersebut List adapat dibuat dengan dua konstruktor yang berbeda — ia dapat memiliki dua bentuk yang berbeda. Jadi misalkan kita ingin menulis headfungsi untuk mendapatkan elemen pertama dari daftar. Di Haskell, kami akan menulis ini sebagai

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

Karena List anilai dapat dari dua jenis yang berbeda, kita perlu menangani masing-masing secara terpisah; ini adalah pencocokan pola. Di head x, jika xcocok dengan polanya Nil, maka kita menjalankan case pertama; jika cocok dengan pola Cons h _, kita jalankan yang kedua.

Jawaban singkat, menjelaskan: Saya pikir salah satu cara terbaik untuk berpikir tentang perilaku ini adalah dengan mengubah cara Anda berpikir tentang tanda sama dengan. Dalam bahasa kurung kurung, pada umumnya, =menunjukkan penugasan: a = bberarti "membuat amenjadi b." Dalam banyak bahasa fungsional, bagaimanapun, =menunjukkan pernyataan kesetaraan: let Cons a (Cons b Nil) = frob x menegaskan bahwa hal di sebelah kiri, Cons a (Cons b Nil)setara dengan hal di sebelah kanan frob x; selain itu, semua variabel yang digunakan di sebelah kiri menjadi terlihat. Ini juga yang terjadi dengan argumen fungsi: kami menyatakan bahwa argumen pertama terlihat Nil, dan jika tidak, kami terus memeriksa.

Artinya bukan menulis

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

Kamu bisa menulis

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

Hei, C ++ juga mendukung pencocokan pola.

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

Pencocokan pola adalah semacam metode overload pada steroid. Kasus paling sederhana akan sama kira-kira sama dengan apa yang Anda lihat di java, argumen adalah daftar tipe dengan nama. Metode yang benar untuk panggilan didasarkan pada argumen yang diteruskan, dan berfungsi ganda sebagai penugasan argumen tersebut ke nama parameter.

Pola hanya selangkah lebih maju, dan dapat merusak argumen yang diteruskan lebih jauh. Itu juga bisa berpotensi menggunakan penjaga untuk benar-benar cocok berdasarkan nilai argumen. Untuk menunjukkan, saya akan berpura-pura seperti JavaScript yang cocok dengan pola.

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

Dalam foo2, ia mengharapkan a menjadi array, ia memecah argumen kedua, mengharapkan sebuah objek dengan dua alat peraga (prop1, prop2) dan memberikan nilai-nilai dari properti tersebut ke variabel d dan e, dan kemudian mengharapkan argumen ketiga menjadi 35.

Tidak seperti dalam JavaScript, bahasa dengan pencocokan pola biasanya memungkinkan beberapa fungsi dengan nama yang sama, tetapi pola yang berbeda. Dengan cara ini seperti metode overloading. Saya akan memberi contoh di erlang:

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

Kaburkan sedikit mata Anda dan Anda bisa membayangkan ini dalam javascript. Sesuatu seperti ini mungkin:

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

Intinya adalah bahwa ketika Anda memanggil fibo, implementasi yang digunakan didasarkan pada argumen, tetapi di mana Java terbatas pada tipe sebagai satu-satunya cara overloading, pencocokan pola dapat melakukan lebih banyak.

Di luar fungsi yang berlebihan seperti yang ditunjukkan di sini, prinsip yang sama dapat diterapkan di tempat lain, seperti pernyataan kasus atau penghancuran perjanjian. JavaScript bahkan memiliki ini dalam 1.7 .

Pencocokan pola memungkinkan Anda untuk mencocokkan nilai (atau objek) dengan beberapa pola untuk memilih cabang kode. Dari sudut pandang C ++, mungkin terdengar sedikit mirip dengan switchpernyataan. Dalam bahasa fungsional, pencocokan pola dapat digunakan untuk mencocokkan pada nilai-nilai primitif standar seperti bilangan bulat. Namun, ini lebih berguna untuk tipe yang dikomposisikan.

Pertama, mari kita tunjukkan pencocokan pola pada nilai-nilai primitif (menggunakan 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')
}

Penggunaan kedua berkaitan dengan tipe data fungsional seperti tupel (yang memungkinkan Anda untuk menyimpan beberapa objek dalam nilai tunggal) dan serikat terdiskriminasi yang memungkinkan Anda untuk membuat tipe yang dapat berisi salah satu dari beberapa opsi. Ini terdengar agak seperti enumkecuali bahwa setiap label juga dapat membawa beberapa nilai. Dalam sintaks pseudo-C ++:

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

Nilai tipe Shapesekarang dapat berisi Rectanglesemua koordinat atau a Circledengan pusat dan jari-jari. Pencocokan pola memungkinkan Anda menulis fungsi untuk bekerja dengan Shapejenis:

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

Terakhir, Anda juga dapat menggunakan pola bersarang yang menggabungkan kedua fitur. Misalnya, Anda bisa menggunakan Circle(0, 0, radius)untuk mencocokkan semua bentuk yang memiliki pusat di titik [0, 0] dan memiliki jari-jari apa pun (nilai jari-jari akan ditetapkan ke variabel baru radius).

Ini mungkin terdengar agak asing dari sudut pandang C ++, tapi saya harap pseudo-C ++ saya membuat penjelasannya menjadi jelas. Pemrograman fungsional didasarkan pada konsep yang sangat berbeda, sehingga lebih masuk akal dalam bahasa fungsional!

Pencocokan pola adalah tempat juru bahasa untuk bahasa Anda akan memilih fungsi tertentu berdasarkan pada struktur dan konten argumen yang Anda berikan.

Ini bukan hanya fitur bahasa fungsional tetapi tersedia untuk banyak bahasa berbeda.

Pertama kali saya menemukan ide adalah ketika saya belajar prolog di mana itu benar-benar pusat bahasa.

misalnya

last ([LastItem], LastItem).

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

Kode di atas akan memberikan item terakhir dari daftar. Input arg adalah yang pertama dan hasilnya adalah yang kedua.

Jika hanya ada satu item dalam daftar interpreter akan memilih versi pertama dan argumen kedua akan disetel sama dengan yang pertama yaitu nilai akan ditugaskan untuk hasilnya.

Jika daftar memiliki kepala dan ekor, penafsir akan memilih versi kedua dan berulang sampai hanya ada satu item yang tersisa dalam daftar.

Bagi banyak orang, mengambil konsep baru lebih mudah jika beberapa contoh mudah diberikan, jadi di sini kita mulai:

Katakanlah Anda memiliki daftar tiga bilangan bulat, dan ingin menambahkan elemen pertama dan ketiga. Tanpa pencocokan pola, Anda bisa melakukannya seperti ini (contoh di Haskell):

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

Sekarang, meskipun ini adalah contoh mainan, bayangkan kami ingin mengikat integer pertama dan ketiga ke variabel dan menjumlahkannya:

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

Ekstraksi nilai-nilai dari struktur data inilah yang dilakukan pencocokan pola. Anda pada dasarnya "mencerminkan" struktur sesuatu, memberikan variabel untuk mengikat tempat-tempat menarik:

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

Ketika Anda memanggil fungsi ini dengan [1,2,3] sebagai argumennya, [1,2,3] akan disatukan dengan [pertama _,, ketiga], mengikat pertama ke 1, ketiga ke 3 dan membuang 2 ( _adalah placeholder untuk hal-hal yang tidak Anda pedulikan).

Sekarang, jika Anda hanya ingin mencocokkan daftar dengan 2 sebagai elemen kedua, Anda dapat melakukannya seperti ini:

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

Ini hanya akan berfungsi untuk daftar dengan 2 sebagai elemen kedua dan memberikan pengecualian, karena tidak ada definisi untuk addFirstAndThird yang diberikan untuk daftar yang tidak cocok.

Sampai sekarang, kami menggunakan pencocokan pola hanya untuk pengikatan yang merusak. Di atas itu, Anda dapat memberikan beberapa definisi fungsi yang sama, di mana definisi pencocokan pertama digunakan, dengan demikian, pencocokan pola sedikit seperti "pernyataan switch pada stereoids":

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

addFirstAndThird akan dengan senang hati menambahkan elemen pertama dan ketiga dari daftar dengan 2 sebagai elemen kedua mereka, dan jika tidak, "gagal" dan "kembali" 0. Fungsionalitas "seperti switch" ini tidak hanya dapat digunakan dalam definisi fungsi, misalnya:

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

Lebih lanjut, ini tidak terbatas pada daftar, tetapi dapat digunakan dengan tipe lain juga, misalnya mencocokkan konstruktor nilai Just and Nothing dari tipe Maybe untuk "membuka" nilai:

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

Tentu, itu hanya contoh mainan, dan saya bahkan tidak mencoba memberikan penjelasan formal atau lengkap, tetapi mereka harus cukup memahami konsep dasar.

Anda harus mulai dengan halaman Wikipedia yang memberikan penjelasan yang cukup bagus. Kemudian, baca bab wikibook Haskell yang relevan .

Ini adalah definisi yang bagus dari wikibook di atas:

Jadi pencocokan pola adalah cara menugaskan nama untuk sesuatu (atau mengikat nama-nama itu untuk hal-hal itu), dan mungkin memecah ekspresi menjadi subekspresi pada saat yang sama (seperti yang kami lakukan dengan daftar dalam definisi peta).

Berikut adalah contoh yang sangat singkat yang menunjukkan kegunaan pencocokan pola:

Katakanlah Anda ingin mengurutkan elemen dalam daftar:

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

ke (Saya sudah beres "New York")

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

dalam bahasa yang lebih penting Anda akan menulis:

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

Dalam bahasa fungsional Anda malah menulis:

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

Karena Anda dapat melihat solusi yang cocok dengan pola memiliki lebih sedikit noise, Anda dapat dengan jelas melihat kasus-kasus yang berbeda dan betapa mudahnya melakukan perjalanan dan mengubah struktur daftar kami.

Saya telah menulis posting blog yang lebih rinci tentang hal ini di sini .