miércoles, 17 de abril de 2019

From HtDP to Racket. Racket (3): for, match, sequences

In the next step we will apply for and match instead of higher order functions over lists and cond. This is optional, the code in the previous version is perfectly valid Racket code. But many Racketeers tend to prefer for for iteration and match over conditionals.

Iteration with for along with sequences (in-list, in-range, and the like) is in principle more efficient, more concise and adds great flexibility given the abundance of pre-defined constructs. For many programmers it is also more readable.

Regarding match its expressiveness is unparalleled. Once you meet it, you can't live without it.

For those reasons the use of for is encouraged in the The Racket Style Guide and pattern matching is so powerful that you must know it. They are even introduced as an Intermezzo in HtDP/2e.

For more information about for see Iterations and Comprehensions [The Racket Guide] and Iterations and Comprehensions [The Racket Reference]. For details about match see Pattern Matching [The Racket Guide] and Pattern Matching [The Racket Reference]

The new version with for a match looks as shown below.

Don't forget to take a look at the Racket documentation for all the new constructs introduced:

  • in-list
  • in-cycle
  • in-range
  • in-value
  • for/list
  • for*/list
  • for/sum
  • match

By the way, with for and match the functions provided by racket/list are no longer used, so the require of that module has been deleted.


; ----------------------------------------------------------
; isbn-racket.v3.rkt
; - for
; - match
; ----------------------------------------------------------

#lang racket/base

(require (only-in racket/match
                  match))

(require (only-in racket/list
                  empty?
                  first
                  range))
(require (only-in racket/string
                  string-normalize-spaces 
                  string-replace
                  string-split))

(module+ test
  (require rackunit)
  (require (only-in racket/file
                    file->string)))

; ----------------------------------------------------------
; Data Types

; An ISBN is one of:
; - ISBN-13
; - ISBN-10

; An ISBN-String is one of:
; - ISBN-13-String
; - ISBN-10-String

; An ISBN-13 is an valid ISBN-13-String
; An ISBN-10 is an valid ISBN-10-String
; where valid means that the numbers in that string
; fullfil a certain mathematical computation. (See
; ISBN User Manual for information about this computation)
(define isbn-13-ex "9781593274917")
(define isbn-10-ex "0262062186")

; An ISBN-13-String is a String consisting of 13 digits,
; where a digit is one of '0', '1', ..., '9'.
(define isbn-13-str-ex "1234567890123")

; An ISBN-10-String is a String consisting of 9 digits,
; and a last letter that can be a digit or 'X'.
(define isbn-10-str-ex-1 "1234567890")
(define isbn-10-str-ex-2 "123456789X")

; An ISBN-Format is one of:
; - 'isbn-13
; - 'isbn-10

; ----------------------------------------------------------
; Patterns and Regexes
; [See ISBN International User Manual 7e. Sect. 5]

; - Pattern Components
(define pat-isbn-sep "[ -]")
(define pat-isbn-id "ISBN(-1[03])?:? ")
(define pat-isbn-13-id "(?:ISBN(?:-13)?:? )?")
(define pat-isbn-10-id "(?:ISBN(?:-10)?:? )?")
(define pat-isbn-prefix "97[89][ -]")
(define pat-isbn-registration "\\d{1,5}[ -]")
(define pat-isbn-registrant "\\d{1,7}[ -]")
(define pat-isbn-publication "\\d{1,6}[ -]")
(define pat-isbn-13-check "\\d")
(define pat-isbn-10-check "[X\\d]")

; - Look ahead to ISBN groups
(define pat-isbn-13-look-ahead
  (string-append "(?=" pat-isbn-prefix pat-isbn-registration ")"))

(define pat-isbn-10-look-ahead
  (string-append "(?=" pat-isbn-registration ")")) 

; - Main patterns
(define pat-isbn-13/groups
  (string-append pat-isbn-13-id
                 pat-isbn-13-look-ahead
                 pat-isbn-prefix
                 pat-isbn-registration
                 pat-isbn-registrant
                 pat-isbn-publication
                 pat-isbn-13-check))

(define pat-isbn-10/groups
  (string-append pat-isbn-10-id
                 pat-isbn-10-look-ahead
                 pat-isbn-registration
                 pat-isbn-registrant
                 pat-isbn-publication
                 pat-isbn-10-check))

(define pat-isbn-13/prefix
  (string-append pat-isbn-13-id pat-isbn-prefix "\\d{10}"))

(define pat-isbn-13-norm "\\d{13}")

(define pat-isbn-10-norm "\\d{9}[X\\d]")

(define pat-isbn-13
  (string-append pat-isbn-13-norm "|"
                 pat-isbn-13/prefix "|"
                 pat-isbn-13/groups))

(define pat-isbn-10
  (string-append pat-isbn-10-norm "|"
                 pat-isbn-10/groups))

(define pat-isbn
  (string-append pat-isbn-13 "|"
                 pat-isbn-10))

; - Regexes
(define re-isbn-id (regexp pat-isbn-id))
(define re-isbn-sep (regexp pat-isbn-sep))
(define re-isbn-13 (pregexp pat-isbn-13))
(define re-isbn-10 (pregexp pat-isbn-10))
(define re-isbn-13-norm (pregexp pat-isbn-13-norm))
(define re-isbn-10-norm (pregexp pat-isbn-10-norm))
(define re-isbn (pregexp pat-isbn))

; ----------------------------------------------------------
; Predicates

(module+ test
  (check-true (isbn? "9781593274917"))
  (check-true (isbn? "0262062186"))
  (check-false (isbn? #f))
  
  (check-true (isbn-13? "9781593274917"))
  (check-false (isbn-13? "0262062186"))
  (check-false (isbn-13? ""))
  
  (check-false (isbn-10? "9781593274917"))
  (check-true (isbn-10? "0262062186"))
  (check-false (isbn-10? 1))
  
  (check-true (isbn-string? "9781593274912"))
  (check-true (isbn-string? "026206218X"))
  (check-false (isbn-string? "97815932749122")) ;too long
  (check-false (isbn-string? "978159327491"))   ;too short
  (check-false (isbn-string? "0262062189X"))    ;too long
  (check-false (isbn-string? "026206218"))      ;too short
  (check-false (isbn-string? "0-262-06218-6"))
  
  (check-true (isbn-13-string? "9781593274912"))
  (check-false (isbn-13-string? "97815932749122")) ;too long
  (check-false (isbn-13-string? "978159327491"))   ;too short
  (check-false (isbn-13-string? #f))
  
  (check-true (isbn-10-string? "026206218X"))
  (check-false (isbn-10-string? "0262062189X")) ;too long
  (check-false (isbn-10-string? "026206218"))   ;too short
  (check-false (isbn-10-string? #f))
  
  (check-true (isbn-format? 'isbn-13))
  (check-true (isbn-format? 'isbn-10))
  (check-false (isbn-format? "isbn-10")))
  
(define (isbn? v)
  (or (isbn-13? v) (isbn-10? v)))

(define (isbn-13? v)
  (and (isbn-13-string? v) (isbn-13-valid? v)))

(define (isbn-10? v)
  (and (isbn-10-string? v) (isbn-10-valid? v)))

(define (isbn-string? v)
  (or (isbn-13-string? v) (isbn-10-string? v)))

(define (isbn-13-string? v)
  (and (string? v) (regexp-match-exact? re-isbn-13-norm v)))

(define (isbn-10-string? v)
  (and (string? v) (regexp-match-exact? re-isbn-10-norm v)))

(define (isbn-format? v)
  (or (equal? v 'isbn-13) (equal? v 'isbn-10)))

; ----------------------------------------------------------
; ISBN Validation

; ISBN-13-String -> Boolean
; is the given isbn-13 string a valid isbn-13

(module+ test
  (check-true (isbn-13-valid? "9781593274917"))
  (check-true (isbn-13-valid? "9780201896831"))
  (check-false (isbn-13-valid? "9781593274912"))
  (check-false (isbn-13-valid? "9780201896834")))

(define (isbn-13-valid? isbn-str)
  (isbn-checksumf (in-list (isbn-string->numbers isbn-str))
                  (in-cycle '(1 3))
                  10))

; ISBN-10-String -> Boolean
; is the given isbn-10 string a valid isbn-10

(module+ test
  (check-true (isbn-10-valid? "0262062186"))
  (check-true (isbn-10-valid? "026256114X"))
  (check-false (isbn-10-valid? "026206218X"))
  (check-false (isbn-10-valid? "0262561141")))

(define (isbn-10-valid? isbn-str)
  (isbn-checksumf (in-list (isbn-string->numbers isbn-str))
                  (in-range 10 0 -1)
                  11))

; [Sequence-of N] [Sequence-of N] N -> Boolean
; abstract checksum algorithm for isbn validation

(module+ test
  (check-true (isbn-checksumf '(9 7 8 1 5 9 3 2 7 4 9 1 7)
                              '(1 3 1 3 1 3 1 3 1 3 1 3 1)
                              10))
  (check-false (isbn-checksumf '(0 2 6 2 0 6 2 1 8 10)
                               (in-range 10 0 -1)
                               11)))

(define (isbn-checksumf multiplicands multipliers mod)
  (define sum
    (for/sum [(x multiplicands)
              (y multipliers)]
      (* x y)))
  (zero? (modulo sum mod)))

; ISBN-String -> [List-of N]
; translates str into the numbers their isbn letters represent

(module+ test
  (check-equal? (isbn-string->numbers "026256114X")
                '(0 2 6 2 5 6 1 1 4 10)))

(define (isbn-string->numbers str)
  (for/list ([char (in-string str)])
    (match char
      [#\X 10]
      [_ (string->number (string char))])))

; ----------------------------------------------------------
; ISBN Extraction

; String -> [List-of ISBN]
; extracts all isbns from str

(module+ test
  (check-equal? (isbn-find/list "") '())
  (check-equal? (isbn-find/list "none") '())
  (check-equal?
   (isbn-find/list (file->string "test-isbn-examples"))
   (list
    ;isbn normalized
    "0262062186" "026256114X" "1593274912"
    "9781593274917" "0201896834" "9780201896831"
    ;isbn w/ several id's a sep's
    "0262062186" "026256114X" "0262062186" "0201896834"
    "9780201896831" "026256114X" "9780201896831")))

(define (isbn-find/list str)
  (for*/list ([line (in-list (string-split str "\n"))]
              [candidate (in-list (isbn-match* line))]
              [isbn-str (in-value (isbn-normalize candidate))]
              #:when (isbn? isbn-str))
    isbn-str))

; String ISBN-Format -> [Maybe ISBN]
; extracts the first isbn of given format from str, if any

(module+ test
  (check-false (isbn-find "" 'isbn-13))
  (check-false (isbn-find "" 'isbn-10))
  (check-false (isbn-find "0262062186" 'isbn-13))
  (check-false (isbn-find "9781593274917" 'isbn-10))
  (check-equal? (isbn-find (file->string "test-isbn-examples")
                           'isbn-13)
                "9781593274917")
  (check-equal? (isbn-find (file->string "test-isbn-examples")
                           'isbn-10)
                "0262062186"))

(define (isbn-find str format)
  (define p?
    (match format
      ['isbn-13 isbn-13?]
      ['isbn-10 isbn-10?]))
  (for*/or ([line (in-list (string-split str "\n"))]
            [candidate (in-list (isbn-match* line))]
            [isbn-str (in-value (isbn-normalize candidate))]
            #:when (p? isbn-str))
    isbn-str))

; ----------------------------------------------------------
; Helpers

; String -> [List-of String]
; matches substrings in the given string looking like isbn tags

(module+ test
  (check-equal? (isbn-match* "") '())
  (check-equal? (isbn-match* "abc\nd") '())
  (check-equal?
   (isbn-match* (file->string "test-isbn-examples"))
   (list
    ;isbn normalized (all matched)
    "0262062186" "026256114X" "1593274912"
    "9781593274917" "0201896834" "9780201896831"
    ;isbn w/ several id's and sep's (all matched)
    "ISBN 0-262-06218-6"
    "ISBN: 0 262 56114 X"
    "ISBN-10 0 262 06218-6"
    "ISBN-10: 0-201-89683-4"
    "ISBN-13: 978-0-201-89683-1"
    "ISBN-10: 0 262 56114 X"
    "ISBN-13: 978-0201896831"
    ;not isbn strings (usually impossible in real-world)
    "026206218X" "0262561141" "9780201896834" ;partially matched
    ;isbn strings, but isbn invalid (all matched)
    "026206218X" "0262561141" "1593274913"
    "9781593274912" "0201896833" "9780201896834")))

(define (isbn-match* str)
  (regexp-match* re-isbn (string-normalize-spaces str)))

; String -> String
; removes the isbn-id and, then, the isbn separators from str

(module+ test
  (check-equal? (isbn-normalize "123-45 67") "1234567")
  (check-equal? (isbn-normalize "ISBN 123") "123")
  (check-equal? (isbn-normalize "ISBN: 123") "123")
  (check-equal? (isbn-normalize "ISBN-10 123") "123")
  (check-equal? (isbn-normalize "ISBN-10: 123") "123")
  (check-equal? (isbn-normalize "ISBN-13 123") "123")
  (check-equal? (isbn-normalize "ISBN-13: 123") "123")
  (check-equal? (isbn-normalize "ISBN-14: hi") "ISBN14:hi"))

(define (isbn-normalize str)
  (string-replace
   (string-replace str re-isbn-id "") re-isbn-sep ""))

Next article in the series: Racket: provide, contracts

No hay comentarios:

Publicar un comentario