wiki:Languages/Scheme

Version 9 (modified by schiptsov, 3 years ago) ( diff )

--

Scheme

Esoteric expressions

((lambda x x) (lambda x x))
(define id ((lambda (x) x) (lambda (x) x)))
((lambda xs xs))
(define list (lambda xs xs))
(define (atom? x) (not (pair? x)))

'() is a List but not a Pair

Lists

(define (list? xs)
  (cond ((null? xs) #t)
        ((and (pair? xs) (null? (cdr xs))) #t)
        (else #f)))
(define (list? xs)
  (or (null? xs) (and (pair? xs) (null? (cdr xs)))))

map

(define (map f xs)
  (if (null? xs)
      '()
      (cons (f (car xs))
            (map f (cdr xs)))))
(define (map f xs)
  (define (recur xs)
    (if (null? xs)
        '()
        (cons (f (car xs))
              (recur (cdr xs)))))
  (recur xs))
(define (map f xs)
  (letrec ((recur (lambda (xs)
                   (if (null? xs)
                       '()
                       (cons (f (car xs))
                             (recur (cdr xs)))))))
    (recur xs)))
(define (map f xs)
  (let recur ((ys xs))
    (if (null? ys)
        '()
        (cons (f (car ys))
              (recur (cdr ys))))))

foldl pattern, tail-recursive, O(2n)

(define (map f xs)
  (define (iter acc xs)
    (cond ((null? xs) (reverse acc))
          (else (iter (cons (f (car xs)) acc) (cdr xs)))))
  (iter '() xs))

folds

(define (foldr f z xs)
  (if (null? xs)
      z
      (f (car xs) (foldr f z (cdr xs)))))
(define (map f xs)
  (foldr (lambda (x xs) (cons (f x) xs)) '() xs))
(define (foldl f acc xs)
  (if (null? xs)
      acc
      (foldl f (f acc (car xs)) (cdr xs))))
(define (reverse xs)
  (foldl (flip cons) '() xs))
(define map (lambda (f xs)
              (reverse (foldl (lambda (xs x) (cons (f x) xs)) '() xs))))

partially

(define partially (lambda (f . as)
                    (lambda xs
                      (apply f (append as xs)))))
(define copy (partially foldr cons '()))
(define reverse (partially foldl (flip cons) '()))
(define length (partially foldl (lambda (acc x) (+ 1 acc)) 0))
(define sum (partially foldl + 0))

macros

(define-syntax when
  (syntax-rules ()
                ((when condition form ...)
                 (if condition
                   (begin form ...)))))
(define-syntax unless
  (syntax-rules ()
                ((unless condition form ...)
                 (if (not condition)
                   (begin form ...)))))
(define-syntax assert
  (syntax-rules ()
                ((assert condition . extra)
                 (unless condition
                   (error "Assertion failed:" 'condition . extra)))))

check-expect

(define-syntax check-expect
  (syntax-rules ()
                ((_ check expect)
                 (let ((checked check)
                       (expected expect))
                   (if (not (equal? checked expect))
                     (begin
                       (display "expression: ")
                       (write (quote check))
                       (newline)
                       (display "received:   ")
                       (write checked)
                       (newline)
                       (display "expected:   ")
                       (write expected)
                       (newline))
                     (if #f #t))))))

Newton's method


see also Standard ML

Note: See TracWiki for help on using the wiki.