A playful implementation of square root in Guile, with a Haskell flavor

sqrt.scm

#| An obfuscated Haskell-style solution to exercise 1.7 from SICP in Guile.
 |
 | The basis of this solution is the idea: the numerical method for square root
 | does not inherently have any notion of what is means for the solution to be
 | "good enough"; that is an _orthogonal_ concern. The inherent idea, in its
 | purest form, is a limit of the algorithm considered as a function of the
 | number of iterations. Therefore, it would be pleasing in our implementation
 | to divorce the idea of what "good enough" means from our expression of the
 | algorithm. But this requires an infinite data structure, because if we do not
 | have an infinite data structure, we must from the first think about when to
 | stop!
 |
 | Secondly, how do we know if we are close, without knowing what the answer is?
 | Assuming a monotonic behavior of the square root approximation w.r.t.
 | iterations (which this algorithm exhibits) then without actually knowing the
 | _precise_ answer, the derivative of our algorithm considered as a function of
 | the number of iterations will tell us how much closer each iteration is
 | getting us. We then have a way of knowing when we are close, because if our
 | monotonic function is not changing much, we are by definition close.
 |
 | For our infinite data structure, we will use Haskell-style lists, a.k.a.
 | streams: that is, either a delayed '(), or a delayed cons cell. Thus, the
 | empty stream is
 |
 |   (delay '())
 |
 | A stream that corresponds to (list 'foo 'bar 'baz) is
 |
 |  (delay (: 'foo (delay (: 'bar (delay (: 'baz (delay '())))))))
 |
 | and so on.
 |#
(import (ice-9 match)) ;; pattern matching is implemented in a library in Guile

#| Syntactic sugar/obfuscation |#
(define : cons)
(define :¹ car)
(define :² cdr)
(define :² cdr)
(define =? eq?)

#| Second/cdr-biased functor map for cons cells |#
(define (:-map 𝑓 ¹-²) (: (:¹ ¹-²) (𝑓 (:² ¹-²))))

#| Anamorphism for streams. Conceptual type signature:
 | unfold :: (b -> Maybe (a, b)) -> b -> Stream a
 |#
(define (↑ 𝑓 𝑥)
  (delay (match (𝑓 𝑥)
           (#f '())
           ((𝑥 . 𝑥') (: 𝑥 (↑ 𝑓 𝑥'))))))

#| Functor map for a stream |#
(define (∞-map 𝑓 𝑥𝑥)
  (delay (match (force 𝑥𝑥)
    (() '())
    ((𝑥 . 𝑥𝑥') (: (𝑓 𝑥) (∞-map 𝑓 𝑥𝑥'))))))

#| Drop a given number of elements from the beginning of stream |#
(define (↓ i 𝑥𝑥)
  (if (=? i 0)
      𝑥𝑥
      (↓ (- i 1) (:² (force 𝑥𝑥)))))

#| Pluck out an element from a stream, if you can find one that matches the
 | predicate.
 |#
(define (? ?' 𝑥𝑥)
  (match (force 𝑥𝑥)
    ((𝑥 . 𝑥𝑥') (if (?' 𝑥) 𝑥 (? ?' 𝑥𝑥')))))

#| Zip two streams into one, ending when either ends, if either does |#
(define (=>- 𝑥𝑥 𝑦𝑦)
  (delay (match (: (force 𝑥𝑥) (force 𝑦𝑦))
    ((() . _) '())
    ((_ . ()) '())
    (((𝑥 . 𝑥𝑥') . (𝑦 . 𝑦𝑦')) (: (: 𝑥 𝑦) (=>- 𝑥𝑥' 𝑦𝑦'))))))

#| Average (mean) of two numbers |#
(define (avg 𝑥 𝑦) (/ (+ 𝑥 𝑦) 2))

#| One iteration of the square-root approximation method |#
(define (√≈ ≈ 𝑥) (avg ≈ (/ 𝑥 ≈)))

#| Comonad duplicate for cons cells |#
(define (:-dup 𝑥) (: (:¹ 𝑥) 𝑥))

#| Apply a cons cell to a function |#
(define (ap-: 𝑓) (λ (𝑥-𝑦) (𝑓 (:¹ 𝑥-𝑦) (:² 𝑥-𝑦))))

#| √≈ adapted for use with ↑ |#
(define (↑√≈ ≈ 𝑥) (:-dup (: (√≈ ≈ 𝑥) 𝑥)))

#| The square root algorithm considered as a function of iterations as the
 | number of iterations approaches infinity, encoded as an infinite stream of
 | approximations.
 |#
(define (∞√≈ 𝑥) (↑ (ap-: ↑√≈) (: 1.0 𝑥)))

#| Function composition operator |#
(define (∘ 𝑓 𝓰) (λ (𝑥) (𝑓 (𝓰 𝑥))))

#| S-combinator from SKI calculus |#
(define (𝐒 𝑓 𝓰 𝑥) (𝑓 𝑥 (𝓰 𝑥)))

#| The idea of being good enough, in the abstract, is being close to some
 | tolerance. What this tolerance is, and what we are comparing it to, we don't
 | specify here. Booyeah orthogonality.
 |#
(define (±? ±) (λ (𝑥) (> ± (abs 𝑥))))

#| Take a derivative, in the sense of derivative calculus, of a function
 | represented as a stream.
 |#
(define (∂ 𝑓) (∞-map (ap-: -) (=>- (↓ 1 𝑓) 𝑓)))

#| Find an approximation for the square root of 𝑥 when the our answer starts to
 | change less than the given tolerance. Example:
 | > (√ 0.0000000001 2)
 | 1.4142135623746899
 |#
(define (√ ± 𝑥) (:¹ (? (∘ (±? ±) :²) (𝐒 =>- ∂ (∞√≈ 𝑥)))))