Home Original page

Python from Wise Guy's Viewpoint

Stephen J. Bevan stephen at dino.dnsalias.com
Sat Oct 25 14:54:38 EDT 2003 
prunesquallor at comcast.net writes:
> (defun lookup (item table if-found if-missing)
>   (cond ((null table) (funcall if-missing))
>         ((eq item (entry-key (first-entry table)))
>          (funcall if-found (entry-value (first-entry table))))
>         (t (lookup item (remaining-entries table)
>                    if-found
>                    if-missing))))
> 
> (defun lookup-default (item local-table default-table if-found if-not-found)
>   (lookup item local-table 
>           if-found
>           (lambda () 
>             (lookup item default-table if-found if-not-found))))
> 
> (defun transform-list (list local-table default-table if-ok if-fail)
>   (if (null list)
>       (funcall if-ok '())
>       (lookup-default (car list) local-table default-table
>         (lambda (result)
>           (transform-list (cdr list) local-table default-table
>             (lambda (remainder)
>               (funcall if-ok (cons result remainder)))
>             if-fail))
>         (lambda () (funcall if-fail (car list))))))
> 
> I know that simple static type checkers will be lost with this.
> I do not know if the smarter ones will.

There are a few undefined functions in the above (entry-key,
first-entry, remaining-entries) which means it would not get past most
static type-checkers.  Assuming that typing programs that have
undefined functions wasn't part of the test, then using a simple
association list to represent the table it all type-checks under SML :-

  $ cat prune.sml
  fun lookup (item, table, ifFound, ifMissing) =
    case table of
      [] => ifMissing ()
    | (k,v)::r => 
        if item = k
        then ifFound v
        else lookup (item, r, ifFound, ifMissing)

  fun lookupDefault (item, localTable, defaultTable, ifFound, ifNotFound) =
    lookup (item, localTable, ifFound, 
             fn _ => lookup (item, defaultTable, ifFound, ifNotFound))

  fun transformList (list, localTable, defaultTable, ifOk, ifFail) =
    case list of
      [] => ifOk []
    | (h::t) => lookupDefault (h, localTable, defaultTable,
                                fn result =>
                                  transformList (t, localTable, defaultTable,
                                                  fn remainder =>
                                                    ifOk (result::remainder),
                                                  ifFail),
                                fn _ => ifFail t)
  $ ~/opt/smlnj-110.41/bin/sml 
  Standard ML of New Jersey v110.41 [FLINT v1.5], July 05, 2002
  - use "prune.sml";
  [opening prune.sml]
  prune.sml:5.15 Warning: calling polyEqual
  val lookup = fn : ''a * (''a * 'b) list * ('b -> 'c) * (unit -> 'c) -> 'c
  val lookupDefault = fn
    : ''a * (''a * 'b) list * (''a * 'b) list * ('b -> 'c) * (unit -> 'c) -> 'c
  val transformList = fn
    : ''a list * (''a * 'b) list * (''a * 'b) list * ('b list -> 'c)
      * (''a list -> 'c)
      -> 'c
  val it = () : unit
  -
More information about the Python-list mailing list