Higher-Order String Functions
January 26, 2016
string-map returns a newly-allocated string:
(define (string-map proc str)
(let* ((len (string-length str))
(out (make-string len)))
(do ((i 0 (+ i 1)))
((= i len) out)
(string-set! out i
(proc (string-ref str i))))))
For example, here is a simple Caesar cipher:
(define (shift c n)
(cond ((char-upper-case? c)
(integer->char (+ (modulo (+ (char->integer c) -65 n) 26) 65)))
((char-lower-case? c)
(integer->char (+ (modulo (+ (char->integer c) -97 n) 26) 97)))
(else c)))
(define (caesar n str) (string-map (lambda (c) (shift c n)) str))
> (caesar 3 "PROGRAMMING praxis") "SURJUDPPLQJ sudalv" > (caesar -3 "SURJUDPPLQJ sudalv") "PROGRAMMING praxis"
string-for-each is simpler than string-map because it doesn’t need a temporary string:
(define (string-for-each proc str)
(do ((i 0 (+ i 1)))
((= i (string-length str)))
(proc (string-ref str i))))
And here’s a simple example:
> (string-for-each
(lambda (c) (display (char->integer c)) (newline))
"PRAXIS")
80
82
65
88
73
83
The two string-fold functions are the most interesting:
(define (string-fold proc base str)
(let loop ((base base) (i 0))
(if (= i (string-length str)) base
(loop (proc (string-ref str i) base) (+ i 1)))))
(define (string-fold-right proc base str)
(let loop ((base base) (i (- (string-length str) 1)))
(if (negative? i) base
(loop (proc (string-ref str i) base) (- i 1)))))
The folds can be used for many tasks:
> (string-fold cons '() "PRAXIS") ; reverse string->list
(#\S #\I #\X #\A #\R #\P)
> (string-fold (lambda (c count) ; count lower-case chars
(if (char-lower-case? c)
(+ count 1)
count))
0 "Programming Praxis")
15
> (string-fold (lambda (c junk) ; string for-each
(display (char->integer c)) (newline))
0 "PRAXIS")
80
82
65
88
73
83
> (list->string ; double characters
(string-fold-right (lambda (c base)
(cons c (cons c base)))
'() "PRAXIS"))
"PPRRAAXXIISS"
You can run the program at http://ideone.com/4iMCaC.
#include <algorithm> #include <cctype> #include <iostream> #include <iterator> #include <numeric> #include <sstream> #include <string> //#define USE_STD_ALGO 1 //#define RANGED_FOR_BACKWARDS 1 std::string string_map(char (*proc)(char), const std::string& input) { std::string output; #ifdef USE_STD_ALGO //The standard C++ map function, transform, can operate directly on strings. std::transform(input.begin(), input.end(), std::back_inserter(output), proc); #else //The new ranged-for syntax is less verbose. for (auto c: input) output.push_back(proc(c)); #endif return output; } template<typename Proc> void string_for_each(Proc proc, std::string& input) { #ifdef USE_STD_ALGO //The standard C++ for_each function works directly on strings. std::for_each(input.begin(), input.end(), proc); #else //Again, however, the ranged-for syntax is less verbose. for (auto& c: input) proc(c); #endif //With STL2 ranges, the std::for_each version will become: // std::for_each(input, proc); //So, ranged-for will lose the concision advantage. } template<typename Proc, typename Base> Base string_fold(Proc proc, Base base, const std::string& input) { #ifdef USE_STD_ALGO //The standard C++ fold function, accumulate, works directly on strings. base = std::accumulate(input.begin(), input.end(), base, proc); #else //Again, the ranged-for is less verbose. for (auto c: input) base = proc(base, c); #endif return base; } template<typename Proc, typename Base> Base string_fold_right(Proc proc, Base base, const std::string& input) { #ifdef USE_STD_ALGO //With the standard algorithms, iterating backwards is as easy as using //rbegin and rend in place of begin and end. base = std::accumulate(input.rbegin(), input.rend(), base, proc); #elif !defined(RANGED_FOR_BACKWARDS) //Another limitation of ranged-for: No easy way to iterate backwards. //So, we do it the old-fashioned way. for (auto i = input.rbegin(); i != input.rend(); ++i) base = proc(base, *i); #else //Or, we can use a helper struct to get ranged-for to work. struct { const std::string& input; auto begin() { return input.rbegin(); } auto end() { return input.rend(); } } helper = { input }; for (auto c: helper) base = proc(base, c); #endif return base; } char rot13(char c) { //C++ gives you very few guarantees about char. //It may be signed or unsigned. //Letters might not be continguous. //I know my platform uses ASCII (or UTF-8) and a signed char. //So this is platform specific code. unsigned char uc = c; if (std::isalpha(uc)) { unsigned char z = std::isupper(uc)? 'Z': 'z'; uc += 13; if (uc > z) uc -= 26; } return uc; } int main() { { //To test string_map, we use it to rot13 a string. std::string input("Hello, world!"); std::string output = string_map(rot13, input); #ifndef NDEBUG std::cout << input << " -> " << output << '\n'; #endif std::cout << "string_map test: " << ((output == "Uryyb, jbeyq!")? "PASSED": "FAILED") << '\n'; } { //To test string_for_each, we pass it a closure that simply accumulates //the characters via a string stream. We expect the output of the //string stream to match the input. std::string input("Hello, world!"); std::ostringstream oss; string_for_each([&oss](char c){ oss << c; }, input); #ifndef NDEBUG std::cout << input << " -> " << oss.str() << '\n'; #endif std::cout << "string_for_each test: " << ((input == oss.str())? "PASSED": "FAILED") << '\n'; } { //To test string_fold, we use integer addition for the procedure, zero //for the base, and "2<" for the string. We expect 110 as a result. //'2' == 50; '<' == 60; '2' + '<' = 110. //This depends on char being ASCII (or UTF-8). std::string input("<2"); int sum = string_fold(std::plus<int>(), 0, input); #ifndef NDEBUG std::cout << sum << '\n'; #endif std::cout << "string_fold test: " << ((110 == sum)? "PASSED": "FAILED") << '\n'; } { //To test string_fold_right, in the proc we append the character to the //base. The resulting string should be the reverse of the input. std::string input("Hello, world!"); std::string output = string_fold_right( [](std::string base, char c) { return base + c; }, std::string(), input); #ifndef NDEBUG std::cout << output << '\n'; #endif std::cout << "string_fold_right test: " << ((output == "!dlrow ,olleH")? "PASSED": "FAILED") << '\n'; } }My scheme version. I probably should’ve used make-string.
#lang r5rs ;;; The simplest way (though perhaps not efficient) to implement these ;;; functions is to convert the string to a list and use the list functions. ;(define (string-map proc str) ; (list->string (map proc (string->list str)))) ; ;(define (string-for-each proc str) ; (for-each proc (string->list str))) ; ;(define (string-fold proc base str) ; (fold-left proc base (string->list str))) ; ;(define (string-fold-right proc base str) ; (fold-right proc base (string->list str))) ;;; But we'll use the string functions to implement them instead... ;; Implement fold first, since it can be used for map and for-each. (define (string-fold proc base str) (let ((len (string-length str))) (let loop ((accumulator base) (i 0)) (if (< i len) (loop (proc accumulator (string-ref str i)) (+ i 1)) accumulator)))) (define (string-fold-right proc base str) (let ((len (string-length str))) (let loop ((accumulator base) (i (- len 1))) (if (>= i 0) (loop (proc accumulator (string-ref str i)) (- i 1)) accumulator)))) (define (string-map proc str) (string-fold (lambda (accumulator character) (string-append accumulator (string (proc character)))) "" str)) (define (string-for-each proc str) (string-fold (lambda (accumulator character) (proc character)) #f str)) ;; A rot13 function for test below. (define (rot13 character) (if (char-alphabetic? character) (let ((i (+ 13 (char->integer character))) (z (char->integer (if (char-upper-case? character) #\Z #\z)))) (integer->char (if (> i z) (- i 26) i))) character)) ;;; Tests! ;;; Since string-map and string-for-each use string-fold, ;;; we don't test string-fold directly. (display (string-map rot13 "Hello, world!")) (newline) (string-for-each display "Hello, world!") (newline) (display (string-fold-right (lambda (accumulator character) (string-append accumulator (string character))) "" "Hello, world!")) (newline)Well this is one useless exercise in Common Lisp: in Common Lisp, strings are vectors, and vectors are sequences, so all the vectors and the sequence operations apply to strings. map, map-into, reduce, reverse, length, equal, etc… So the solution of this problem in CL, is null, apart perhaps from the renaming (which is dumb, and caused the problem in scheme in the first place; use generic functions!):