784e50fe72f6

Add `fixed-point`
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Thu, 03 Nov 2016 17:37:41 +0000
parents 1c26cbbe73b6
children 1c5dff36922b
branches/tags (none)
files DOCUMENTATION.markdown losh.lisp package.lisp

Changes

--- a/DOCUMENTATION.markdown	Thu Nov 03 17:25:45 2016 +0000
+++ b/DOCUMENTATION.markdown	Thu Nov 03 17:37:41 2016 +0000
@@ -266,6 +266,12 @@
 
   
 
+### `PRINT-HASH-TABLE` (function)
+
+    (PRINT-HASH-TABLE HASH-TABLE &OPTIONAL (STREAM T))
+
+Print a pretty representation of `hash-table` to `stream.`
+
 ### `PRINT-TABLE` (function)
 
     (PRINT-TABLE ROWS)
@@ -386,6 +392,22 @@
 
 Utilities for working with higher-order functions.
 
+### `FIXED-POINT` (function)
+
+    (FIXED-POINT FUNCTION DATA &KEY (TEST 'EQL) (LIMIT NIL))
+
+Find a fixed point of `function`, starting with `data`.
+
+  Successive runs of `function` will be compared with `test`.  Once `test`
+  returns true the last result will be returned.
+
+  `limit` can be an integer to limit the maximum number of iterations performed.
+
+  A second value is also returned: `t` if a fixed point was found or `nil` if
+  the iteration limit was reached.
+
+  
+
 ### `JUXT` (function)
 
     (JUXT &REST FUNCTIONS)
--- a/losh.lisp	Thu Nov 03 17:25:45 2016 +0000
+++ b/losh.lisp	Thu Nov 03 17:37:41 2016 +0000
@@ -264,6 +264,25 @@
   (lambda (&rest args)
     (if (null args) result (apply function args))))
 
+(defun fixed-point (function data &key (test 'eql) (limit nil))
+  "Find a fixed point of `function`, starting with `data`.
+
+  Successive runs of `function` will be compared with `test`.  Once `test`
+  returns true the last result will be returned.
+
+  `limit` can be an integer to limit the maximum number of iterations performed.
+
+  A second value is also returned: `t` if a fixed point was found or `nil` if
+  the iteration limit was reached.
+
+  "
+  (if (and limit (zerop limit))
+    (values data nil)
+    (let ((next (funcall function data)))
+      (if (funcall test data next)
+        (values next t)
+        (fixed-point function next :test test :limit (when limit (1- limit)))))))
+
 
 ;;;; Control Flow
 (defmacro recursively (bindings &body body)
--- a/package.lisp	Thu Nov 03 17:25:45 2016 +0000
+++ b/package.lisp	Thu Nov 03 17:37:41 2016 +0000
@@ -64,7 +64,8 @@
   (:documentation "Utilities for working with higher-order functions.")
   (:export
     #:juxt
-    #:nullary))
+    #:nullary
+    #:fixed-point))
 
 (defpackage #:losh.control-flow
   (:documentation "Utilities for managing control flow.")