From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Blake Shaw Newsgroups: gmane.lisp.guile.devel Subject: [PATCH v1 1/6] docs/match: add pattern matching examples Date: Fri, 27 Jan 2023 01:57:56 +0700 Message-ID: <20230126185801.19064-1-blake@reproduciblemedia.com> Mime-Version: 1.0 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="23608"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Blake Shaw To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Fri Jan 27 02:44:18 2023 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pLDmr-0005rg-6o for guile-devel@m.gmane-mx.org; Fri, 27 Jan 2023 02:44:17 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pLDmN-0004Wm-UT; Thu, 26 Jan 2023 20:43:47 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pL7SC-0008Rk-1r for guile-devel@gnu.org; Thu, 26 Jan 2023 13:58:32 -0500 Original-Received: from out2.migadu.com ([2001:41d0:2:aacc::]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pL7S9-0007HP-1w for guile-devel@gnu.org; Thu, 26 Jan 2023 13:58:31 -0500 X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=reproduciblemedia.com; s=key1; t=1674759505; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding; bh=I6GUh1FDCparMuN9ExcbEGTlxKtRoWgTZ6KiPdHkql0=; b=oZdDQ65/+LiJ7vgzxonM4Ktb6APWnbJVoX8DNXSug1m91QAz0/jIwe5A2sWAN8V9kG1bYZ 42ZX1qeWjIFkSLhHA/MxM1xiiKX6O7xsltdU/AGkRRvfcjE2qMhkHCt4Il0VfoivEYjMgg /5Yh33ESC2CKullnJmdWg7MlfpfQjP0= X-Migadu-Flow: FLOW_OUT Received-SPF: pass client-ip=2001:41d0:2:aacc::; envelope-from=blake@reproduciblemedia.com; helo=out2.migadu.com X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Mailman-Approved-At: Thu, 26 Jan 2023 20:43:44 -0500 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.lisp.guile.devel:21641 Archived-At: Hello all, This commit introduces a set of (long overdue) examples to the documentation on pattern matching discussed in the Guix Days presentation which can be found here: https://xana.lepiller.eu/guix-days-2022/guix-days-2022-documentation.mp4 As discussed in the Guix Days presentation, and agreed upon during the corresponding brainstorming session, I'm introducing a set of examples that intend to demonstrate the basics of the Shinn/Wright pattern matcher, as well as touch on some of its subtleties. Most paragraphs will be broken up into smaller peices with examples interspersed throughout, according to the refactoring strategy of "graduated expression" presented in my talk. The goal is to express the pedagogical aim of examples naturally through graduality, reducing "wordiness" primarily by with examples rather than reducing what has already been written. My apologies for taking so long to get to work on this! This summer I was confronted with a unanticipated event that subsequently turned my life upside down, causing my contributions to be low. I hope to be increasing my contributions from here on, and fulfilling my obligations concerning the documentation. Best, Blake --- doc/ref/match.texi | 138 ++++++++++++++++++++++++++++++++------------- 1 file changed, 99 insertions(+), 39 deletions(-) diff --git a/doc/ref/match.texi b/doc/ref/match.texi index f5ea43118..105150886 100644 --- a/doc/ref/match.texi +++ b/doc/ref/match.texi @@ -24,52 +24,66 @@ written by Alex Shinn, and compatible with Andrew K. Wright's pattern matcher found in many Scheme implementations. @cindex pattern variable -A pattern matcher can match an object against several patterns and -extract the elements that make it up. Patterns can represent any Scheme -object: lists, strings, symbols, records, etc. They can optionally contain -@dfn{pattern variables}. When a matching pattern is found, an -expression associated with the pattern is evaluated, optionally with all -pattern variables bound to the corresponding elements of the object: +A pattern matcher does precisely what the name implies: it matches +some arbitrary pattern, and returns some result accordingly. @example -(let ((l '(hello (world)))) - (match l ;; <- the input object - (('hello (who)) ;; <- the pattern - who))) ;; <- the expression evaluated upon matching -@result{} world +(define (english-base-ten->number name) + (match name + ('zero 0) + ('one 1) + ('two 2) + ('three 3) + ('four 4) + ('five 5) + ('six 6) + ('seven 7) + ('eight 8) + ('nine 9))) + +(english-base-ten->number 'six) +@result{} 6 + +(apply + (map english-base-ten->number '(one two three four))) +@result{} 10 @end example -In this example, list @var{l} matches the pattern @code{('hello (who))}, -because it is a two-element list whose first element is the symbol -@code{hello} and whose second element is a one-element list. Here -@var{who} is a pattern variable. @code{match}, the pattern matcher, -locally binds @var{who} to the value contained in this one-element -list---i.e., the symbol @code{world}. An error would be raised if -@var{l} did not match the pattern. - -The same object can be matched against a simpler pattern: +Pattern matchers may contain @dfn{pattern variables}, local bindings +to all elements that match a pattern. @example -(let ((l '(hello (world)))) - (match l - ((x y) - (values x y)))) -@result{} hello -@result{} (world) +(let re ((ns '(one two three four ten)) + (total 0)) + (match ns + ((e) (+ total (english-base-ten->number e))) + ((e . es) + (re es (+ total (english-base-ten->number e)))))) +@result{} 20 @end example -Here pattern @code{(x y)} matches any two-element list, regardless of -the types of these elements. Pattern variables @var{x} and @var{y} are -bound to, respectively, the first and second element of @var{l}. - -Patterns can be composed, and nested. For instance, @code{...} +In this example, the list @var{ns} matches the pattern +@code{(e . es)}, where the pattern variable @var{e} corresponds +to the `car` of @var{ns} and the pattern variable @var{es} +corresponds to the `cdr` of @var{ns}. + +A tail call @code{re} is then initiated and we `cdr` down the +list by recurring on the tail @var{es}, applying our matcher +@code{english-base-ten->number} to each element of @var{ns} until +only a single element @code{(e)} remains, causing the @var{total} +to be computed. In modern Scheme programming it is common to use +@code{match} in place of the more verbose but familiar combination +of @code{cond}, @code{car} and @code{cdr}, so it's important to +understand how these idioms translate. + +Patterns can be composed and nested. For instance, @code{...} (ellipsis) means that the previous pattern may be matched zero or more times in a list: @example -(match lst - (((heads tails ...) ...) - heads)) +(match '(((a b c) e f g) 1 2 3) + (((head ...) tails ...) + `(,@tails ,head))) +@result{} (1 2 3 ((a b c) e f g)) @end example @noindent @@ -79,6 +93,52 @@ lst)}. However, it performs additional checks to make sure that @var{lst} and the lists therein are proper lists, as prescribed by the pattern, raising an error if they are not. +A pattern matcher can match an object against several patterns and +extract the elements that make it up. + +@example +(let ((m '((a . b) (c . d) (e . f)))) + (match m + (((left . right) ...) left))) +@result{} (a c e) +@end example + +@example +(let ((m '((1 . (a . b)) (2 . (c . d)) (3 . (e . f))))) + (match m + (((key . (left . right)) ...) + (fold-right acons '() key right )))) +@result{} ((1 . b) (2 . d) (3 . f)) +@end example + +Patterns can represent any Scheme object: lists, strings, symbols, +records, etc. + +@example +(let re ((m #(a "b" c "d" e "f" g))) + (match m + ((or (e) #(e)) e) + ((or #(e1 e2 es ...) + (e1 e2 es ...)) + (cons (cons e1 e2) + (re es))))) +@result{} ((a . "b") (c . "d") (e . "f") . g) +@end example + +When a matching pattern is found, an expression associated with the +pattern is evaluated, optionally with all pattern variables bound to +the corresponding elements of the object. + +@example +(let re ((m '(a b c d e f g h i))) + (match m + ((e) e) + ((e1 e2 es ...) + (acons e1 e2 + (re es))))) +@result{} ((a . b) (c . d) (e . f) (g . h) . i) +@end example + Compared to hand-written code, pattern matching noticeably improves clarity and conciseness---no need to resort to series of @code{car} and @code{cdr} calls when matching lists, for instance. It also improves @@ -229,11 +289,11 @@ expressions. @end deffn @example -((match-lambda - (('hello (who)) - who)) - '(hello (world))) -@result{} world +(define flatten-singletons + (match-lambda (((s) ...) s))) + +(flatten-singletons '((x) (y) (z))) +@result{} (x y z) @end example @deffn {Scheme Syntax} match-lambda* clause1 clause2 @dots{} -- 2.39.1