According to SICP, high-order function gives us the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. It's very useful while you're trying to refactor you code.

There're several built-in classical high-order functions in most modern languages, like map, reduce, filter, accumulator... Frequently, we use them for solving most problems.

But it doesn't mean you can't find or invent new one. Actually, you may be inspired during programming and find a new pattern which could be abstracted to use high-order functions.

This article introduced a new high-order function for certain cases. I wrote it in Scheme, but you can rewrite it in any languages supported first-class function.

Uroboros

It's easy to find such a pattern in some cases: the input data needs to be handled repeatedly, each round the result would be the input of next round, *BUT* we need to pass two arguments to the kernel function. This is similar to pipeline pattern, but different. Because pipeline pattern pass only one argument amount rounds.

To make this clearer, let's try a simple example.

Considering a GCD(Great Common Divisor) function:

(define (my-gcd x y)
  (if (zero? y)
      x
      (my-gcd y (modulo x y))))

You may found a rule that my-gcd was called repeatedly, and each time the arguments are related to the last round. Actually, the kernel function my-gcd generates the input arguments for next round. This situation appears in most tail-call procedures.

So let me introduce a new pattern named urob stands for Uroboros. It's a snake eating itself. I can't say this metaphor is very proper, but I hope it can active your imagination.

(define (urob func init val pred)
 (if (pred val)
     init
     (call-with-values (lambda () (func init val))
       (lambda (x y) (urob func x y pred)))))

Very simple huh?

The pred would predicate if the recursive calling should be end. And func is the kernel function. Let's try it for GCD:

(define (my-gcd2 x y)
 (urob (lambda (a b) (values b (modulo a b)))
       x y zero?))

Someone may shout.

I'll explain it in the end. Now let's try more complex case:

A delimiter lexer

A delimiter lexer is easy to understand. You specifiy a delimiters list, and the lexer will tokenize the input string:

;; (lexer str delimiters)
(lexer "hello.x+(bye)"  ".+()")
;; ==> ("hello" "." "x" "+" "(" "bye" ")")

It's not hard to implement such a lexer with loop:

(define (lexer str delimiters)
 (define cs (->char-set delimiters))
 (define-syntax-rule (-> w r)
  (if (null? w)
      r
      (cons (list->string (reverse! w)) r)))
 (let lp((lst (string->list str)) (ret '()) (word '()))
  (cond
   ((null? lst) (reverse! ret))
   (else
    (if (char-set-contains? cs (car lst))
        (lp (cdr lst) (cons (string (car lst)) (-> word ret)) '())
        (lp (cdr lst) ret (cons (car lst) word)))))))

But I'm going to show you a uroboros version:

(use-modules (ice-9 rdelim) (rnrs))

(define (lexer str delimiters)
 (define (-> c) (if (eof-object? c) '() (list (string c))))
 (define (tokenizer lst str)
  (call-with-input-string str
   (lambda (port)
    (let* ((token (read-delimited delimiters port 'peek))
           (delim (-> (read-char port)))  
           (rest (get-string-all port)))
         (values (if (string-null? token) `(,@lst ,@delim) `(,@lst ,token ,@delim))
                 rest)))))
  (urob tokenizer '() str string-null?))

So what?

Choosing a proper high-order function could help you to break you code into more maintainable independent functions, and reuse the code largely. Although understanding the classical high-order functions is important in functional programming, you can even invent your own during the practicing.

I always thought, if design pattern is so significant for OOP, maybe high-order function has equal status in FP. Maybe both.

Who knows...