Higher-Order String Functions
January 26, 2016
Scheme provides the higher-order functions map, for-each and fold that operate on lists. In today’s exercise we will write versions of those functions that operate on strings:
(string-map proc str)appliesprocto each character instr, replacing the character with the output ofproc.proctakes a single character and returns a single character.
(string-for-each proc str)appliesprocto each character instr; the function is executed only for its side-effects.proctakes a single character and returns nothing.
(string-fold proc base str)calls function(proc base c)on each character ofstr, working left to right, accumulating the result inbaseas it goes.proctakes abaseof any type, and a character, and returns a value of the same type asbase.(string-fold-right proc base str)is the same, except that it works from right to left.
Your task is to implement these four functions in the language of your choice. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
#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!):