I think it would desirable to add a 'where clause' to thematch module (it could
be implemented as a keyword argument:#:where (test).
Below are versions and an insertion sort algorithm
from<http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort>First a Qi
version, then an Erlang version, followed by a proposedRacket version with a
'where clause', a failed attempt at writinga Racket version with a predicate
clause, and finally a practical(at the present time) Racket version of the
algorithm.
I'm not an experienced programmer but I am intrigued by patternmatching and
have glanced at pattern matching capabilities ina variety of functional
languages.
I'd appreciate comments on whether this feature is considereddesirable/feasible
in Racket.
Qi version of insertion sort using 'where clause':
(define insert X [] -> [X] X [Y | Ys] -> [X Y | Ys] where (<= X Y) X
[Y | Ys] -> [Y | (insert X Ys)]) (define insertion-sort [] -> [] [X |
Xs] -> (insert X (insertion-sort Xs))) (insertion-sort [6 8 5 9 3 2 1 4 7])
Erlang version on same web page using 'when clause':
-module(sort).-export([insertion/1]). insertion(L) -> lists:foldl(fun insert/2,
[], L).
insert(X, []) -> [X];insert(X, L = [H | _]) when X =< H ->
[X | L];insert(X, [H | T]) -> [H | insert(X, T)].
> sort:insertion([5,3,9,4,1,6,8,2,7]).
Proposed Racket version (based on the Erlang example)uses #:where keyword:
(define/match (insert X lst) [{ X '() } (list X)] [{
X (cons H T) } #:where (<= X H) (list* X H T)] [{ X (cons H T) }
(cons H (insert X T))])
(define (insertion-sort lst) (foldl insert '() lst))
I don't think that a corresponding Racket predicate matchcan be written (I may
not have coded it correctly!)It's also messy:
(define/match (insert-b X lst) [{ X '() }
(list X)] [{ X (and (cons H T) (? (λ (H X) (<= X H)))) } (list* X H T)] [{ X
(cons H T) } (cons H (insert-b X T))])
(define (insertion-sort-b lst) (foldl insert-b '() lst))
(insertion-sort-b '(6 8 5 9 3 2 1 4 7))
Current working Racket version(modified slightly from the posted Racket
version)It's necessarily missing the third match pattern:
(define/match (insert-c X lst) [{ X '() } (list X)] [{ X (cons H T) }
(cond [(<= X H) (list* X H T)] [else (cons H
(insert-c X T))])])
(define (insertion-sort-c lst) (foldl insert-c '() lst))
(insertion-sort-c '(6 8 5 9 3 2 1 4 7))
_________________________
Racket Developers list:
http://lists.racket-lang.org/dev
